Having fun with basic structs, and was looking into intersect 2 ordered IntArray together. I know I ...

# getting-started

[Andrea Giuliano]

Having fun with basic structs, and was looking into intersect 2 ordered IntArray together. I know I can do something like first.intersect(second.toList()).toIntArray() but this is not really O(n). It takes more time than just using standard comparison one by one (using the property that the 2 IntArrays are ordered). I wonder if there is something elegant to solve this in Kotlin? An ugly way to do this fast would be with something like

private fun intersection(a: IntArray, b: IntArray): IntArray {
        val c = IntArray(min(a.size, b.size))
        if (c.isEmpty()) {
            return c
        }
        var i = 0
        var j = 0
        var k = 0
        while (i < a.size && j < b.size) {
            val aa = a[i]
            val bb = b[j]
            val comparison = aa - bb
            if (comparison == 0) {
                c[k++] = aa
                i++
                j++
            } else if (comparison < 0) {
                i++
            } else {
                j++
            }
        }
        return c.copyOf(k)
    }

[nanodeath]

fundamentally this is the intersection of two sorted arrays/collections...if that helps you search for anything

[Andrea Giuliano]

it is indesd. I did search yeah, nothing that can help me take advantage of the int position

[nanodeath]

I think given this kind of thing is performance-sensitive, anything fancier would probably be slower...I guess my main concern is is there any way we can avoid the copy. maybe take (data: IntArray, size: Int) -> Unit as a third argument and pass c, k directly to that. though admittedly that'd look a little weird.

[nanodeath]

I'd also probably swap out the if for a when.

[nanodeath]

and use aa.compareTo(bb)

[nanodeath]

...actually I'm not sure why you can't just check aa < bb directly

[ephemient]

minor note: min() is not in kotlin stdlib, minOf() is

[ephemient]

you shouldn't use - for comparison, it can overflow and give the wrong result, e.g.

Int.MIN_VALUE - Int.MAX_VALUE > 0

[nanodeath]

compareTo ftw

[ephemient]

I'd probably write something generic like this but if you're sticking with IntArray for performance then I'm not sure there's much else you can do

Untitled

[nanodeath]

hm. does Array implement Iterable?

[nanodeath]

I guess you could always say Arrays.asList

[ephemient]

that would incur boxing overhead which doesn't exist with IntArray

[Andrea Giuliano]

thanks folks!