Hi!
I was playing with extension functions and tried to do binarySearch function on lists. And I realized that there is an extension function already that is builtin in Kotlin. However, it is very slow: -
public fun <T: Comparable> List<T?>.binarySearch(element: T?, fromIndex: Int = 0, toIndex: Int = size): Int {
rangeCheck(size, fromIndex, toIndex)var low = fromIndex var high = toIndex - 1 while (low <= high) { val mid = (low + high).ushr(1) // safe from overflows val midVal = get(mid) val cmp = compareValues(midVal, element) if (cmp < 0) low = mid + 1 else if (cmp > 0) high = mid - 1 else return mid // key found } return -(low + 1) // key not found
}
I have edited the function and removed the function call (compareValues) and the replacement function is way faster
test_buildin_binary_search 8s35m
test_binary_search 584ms
^based on my test I will attach it down.
the new one: - (EDITED to match the same semantics of the original)
fun rangeCheck(size: Int, fromIndex: Int, toIndex: Int) {
when {
fromIndex > toIndex -> throw IllegalArgumentException("fromIndex ($fromIndex) is greater than toIndex ($toIndex).")
fromIndex < 0 -> throw IndexOutOfBoundsException("fromIndex ($fromIndex) is less than zero.")
toIndex > size -> throw IndexOutOfBoundsException("toIndex ($toIndex) is greater than size ($size).")
}
}
fun <T : Comparable<T>> binarySearch(list: List<T?>, element: T?, fromIndex: Int = 0, toIndex: Int = list.size): Int {
rangeCheck(list.size, fromIndex, toIndex)
var low = fromIndex
var high = toIndex - 1
while (low <= high) {
val mid = (low + high).ushr(1) // safe from overflows
val midVal = list.get(mid)
val cmp = element?.compareTo(midVal as T) as Int
if (cmp < 0)
low = mid + 1
else if (cmp > 0)
high = mid - 1
else
return mid // key found
}
return -(low + 1) // key not found
}
It is not an extension function so far. But I believe that the inside function call is the reason of making it slow.
Q1. why compareValues is not an inline function? maybe due to design decisions? where it is not always a good idea to inline it?
Q2. Is there a keyword that gives the programmer the freedom to inline function “f1” for example where f1 is not inline function?
I mean why there is no keyword like “inlineit” and it is used as: -
fun f1() {
println("something")
}
fun main() {
inlineit f1() // line 1
f1() // line 2
}
Where in this case f1() will be inlined only when we use the keyword inlineit in front of its name, in above code f1() in line 1 is inlined but in line 2 is not.
The junit test: -
class BinarySearchTests() {
private val max = 10_000_000
private val times = 10_000_000
private val largNumbers = (0..max).toList()
private val r = Random(System.currentTimeMillis())
@Test
fun test_binary_search() {
var found = false
repeat(times) {
val item = r.nextInt(max)
val r = binarySearch(largNumbers, item)
if (r != null) found = true
}
assert(found)
}
@Test
fun test_buildin_binary_search() {
var found = false
repeat(times) {
val item = r.nextInt(max)
val r = largNumbers.binarySearch(item)
if (r != -1) found = true
}
assert(found)
}
}
Thank you