https://kotlinlang.org logo
#getting-started
Title
# getting-started
a

Andrea Giuliano

10/14/2020, 8:31 AM
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
Copy code
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)
    }
n

nanodeath

10/14/2020, 4:34 PM
fundamentally this is the intersection of two sorted arrays/collections...if that helps you search for anything
a

Andrea Giuliano

10/14/2020, 4:37 PM
it is indesd. I did search yeah, nothing that can help me take advantage of the int position
n

nanodeath

10/14/2020, 4:38 PM
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.
I'd also probably swap out the if for a when.
and use
aa.compareTo(bb)
...actually I'm not sure why you can't just check
aa < bb
directly
e

ephemient

10/14/2020, 8:21 PM
minor note:
min()
is not in kotlin stdlib,
minOf()
is
you shouldn't use
-
for comparison, it can overflow and give the wrong result, e.g.
Copy code
Int.MIN_VALUE - Int.MAX_VALUE > 0
👆 2
👍 1
n

nanodeath

10/14/2020, 8:23 PM
compareTo
ftw
e

ephemient

10/14/2020, 8:38 PM
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
👍 1
n

nanodeath

10/14/2020, 8:45 PM
hm. does Array implement Iterable?
I guess you could always say Arrays.asList
e

ephemient

10/14/2020, 9:37 PM
that would incur boxing overhead which doesn't exist with IntArray
a

Andrea Giuliano

10/16/2020, 9:32 AM
thanks folks!