#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!