Фильтровать, вычитать или группировать по - что является наиболее эффективным? (Котлин)

Question

Например, у нас есть список, который мы хотим разделить на две части с определенным предикатом.

Во-первых, мы можем использовать filter и filterNot.

val trueList = list.filter(predicate)
val falseList = list.filterNot(predicate)

Во-вторых, мы можем использовать filter и subtract:

val trueList = list.filter(predicate)
val falseList = list.subtract(trueList)

В-третьих, мы можем использовать groupBy:

val groupBy = list.groupBy(predicate)
val trueList = groupBy[true]
val falseList = groupBy[false]

Какой самый эффективный, самый быстрый способ? И можем ли мы сделать это с некоторыми другими функциями?

Думаю, второй вариант с subtract - худший, я прав?

Answer 1

Итак, я попытался понять, какой вариант самый быстрый: filter, subtract, groupBy или partition (спасибо Марко Топольник за подсказку). И я использовал measureTimeMillis, чтобы узнать истекшее время каждого варианта:

private fun checkTime(list: List<Int>, predicate: (Int) -> Boolean) {
    var sum = 0L
    repeat(times) { sum += checkPartition(list, predicate) }
    println("partition: ${sum/times}")

    sum = 0L
    repeat(times) { sum += checkFilter(list, predicate) }
    println("filter: ${sum/times}")

    sum = 0L
    repeat(times) { sum += checkSubtract(list, predicate) }
    println("subtract: ${sum/times}")

    sum = 0L
    repeat(times) { sum += checkGroupBy(list, predicate) }
    println("group by: ${sum/times}")
}


private fun checkGroupBy(list: List<Int>, predicate: (Int) -> Boolean): Long {
    return measureTimeMillis {
        val groupBy = list.groupBy(predicate)
        val falseList = groupBy[false]
        val trueList = groupBy[true]
    }
}

private fun checkSubtract(list: List<Int>, predicate: (Int) -> Boolean): Long {
    return measureTimeMillis {
        val trueList = list.filter(predicate)
        val falseList = list.subtract(trueList)
    }
}

private fun checkFilter(list: List<Int>, predicate: (Int) -> Boolean): Long {
    return measureTimeMillis {
        val trueList = list.filter(predicate)
        val falseList = list.filterNot(predicate)
    }
}

private fun checkPartition(list: List<Int>, predicate: (Int) -> Boolean): Long {
    return measureTimeMillis {
        val pair = list.partition(predicate)
        val trueList = pair.first
        val falseList = pair.second
    }
}

Я проверял это с 10-кратным повторением, и этот предикат:

val predicate = { it: Int -> it % 2 == 0 }

И со списками с другим размером:

var list = (1..1_000_000).toList()
checkTime(list, predicate)

раздел: 16 фильтр: 21 вычесть: 81 сгруппировать по: 18

list = (1..2_000_000).toList()
checkTime(list, predicate)

раздел: 30 фильтр: 42 вычесть: 241 сгруппировать по: 36

list = (1..3_000_000).toList()
checkTime(list, predicate)

раздел: 35 фильтр: 59 вычесть: 233 сгруппировать по: 63

Итак, раздел - действительно хороший вариант для разделения списка на две части.

Скажите, пожалуйста, если я сделал что-то не так.