KotlinのbinarySearch()とcontains()について

はじめに

この記事では、KotlinのCollectionのbinarySearch()、contains()について紹介します。これらは両方とも、配列内の要素を見つけることができます。

binarySearch()

binarySearch()は指定した要素のインデックスを返します。binarySearch()を利用するためには、次の条件を満たす必要があります。それは配列を昇順に並べ替える必要があるということです。もし、等しい複数の要素が配列に含まれている場合は、どの要素が返却されるか保証されません。また、O(log n)の時間計算量をもつ効率的なアルゴリズムの一つです。実装内容は次の通りです。

Collections.kt

public fun <T : Comparable<T>> 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
}

実際にbinarySearch()を利用してみると、配列内に存在する要素であれば当該インデックスが返ってくることがわかります。

fun main() {
    val list = (1..1_000_000).sorted()
    println(list.binarySearch(10_000)) // 9999
    println(list.binarySearch(-10_000)) // -1
    println(list.binarySearch(0)) // -1
    println(list.binarySearch(1_000_001)) // -1000001
}

contains()

contains()は配列内に要素が見つかった場合にtrueを返します。内部的には、indexOf()を使用して要素が配列内にあるかどうかを判定します。indexOf()は配列全体を繰り返し、各要素をequals()と比較します。これは、必要に応じて全ての配列の要素を反復処理するため、O(n)の時間計算量になります。そのため、ここで特定の要素を見つけるために費やす時間は、配列内にある項目の数によって異なります。実装内容は次の通りです。

libraries/stdlib/common/src/generated/_Collections.kt

public operator fun <@kotlin.internal.OnlyInputTypes T> Iterable<T>.contains(element: T): Boolean {
    if (this is Collection)
        return contains(element)
    return indexOf(element) >= 0
}

public fun <@kotlin.internal.OnlyInputTypes T> Iterable<T>.indexOf(element: T): Int {
    if (this is List) return this.indexOf(element)
    var index = 0
    for (item in this) {
        checkIndexOverflow(index)
        if (element == item)
            return index
        index++
    }
    return -1
}

また、指定された配列のすべての要素が対象の配列に含まれているかどうかを確認する関数にcontainsAll()があります。これはO(n^2)の時間計算量となります。

AbstractCollection.java

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

実際にcontains()を利用してみると、配列内に存在する要素であればtrueが返ってくることがわかります。

fun main() {
    val list = (1..1_000_000)
    println(list.contains(10_000)) // true
    println(list.contains(-10_000)) // false
    println(list.contains(0)) // false
    println(list.contains(1_000_001)) // false
}

ベンチマークツール

ベンチマークについてはデータに依存するため、ベンチマークのツールについてのみ紹介とさせてもらいます。Kotlinのマルチプラットフォームのベンチマークツールにkotlinx.benchmarkがあります。benchmarkのGradleタスクを実行するとベンチマークが実行されます。サンプルコードは次の通りです。

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
@Timeout(time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 2)
class TestBenchmark {
    var data = emptyList<Int>()

    @Setup
    fun setUp() {
        data = (1..1_000_000).sorted()
    }

    @Benchmark
    fun binarySearch() {
        data.binarySearch(10_000)
    }

    @Benchmark
    fun contains() {
        data.contains(10_000)
    }
}

最後に

ここまでbinarySearch()、contains()について簡単に紹介しました。contains()は従来の線形探索を利用しているのに対して、binarySearch()はバイナリサーチを利用しています。そのためbinarySearch()は大きなサイズの配列に対して有効です。