Как эффективно получить N самых низких значений из коллекции (Top N) в Котлине?

Question

Как эффективно получить N самых низких значений из коллекции (Top N) в Kotlin?

Есть ли другой способ, кроме collectionOrSequence.sortedby{it.value}.take(n)?

Предположим, у меня есть коллекция с +100500 элементов и мне нужно найти 10 самых низких.Боюсь, что sortedby создаст новую временную коллекцию, которая в дальнейшем займет всего 10 предметов.

Answer 1

Если вы работаете на JVM, вы можете использовать Guava's Comparators.least(int, Comparator), который использует более эффективный алгоритм, чем любое из этих предложений, принимая O (n + k log k) времени и O(k) память для поиска наименьших k элементов в коллекции размера n, в отличие от алгоритма Запла (O (nk log k)) или алгоритма Лиора (O (nk)).

Answer 2

Вы можете сохранить список из n самых маленьких элементов и просто обновить его по требованию, например,

fun <T : Comparable<T>> top(n: Int, collection: Iterable<T>): List<T> {
    return collection.fold(ArrayList<T>()) { topList, candidate ->
        if (topList.size < n || candidate < topList.last()) {
            // ideally insert at the right place
            topList.add(candidate)
            topList.sort()
            // trim to size
            if (topList.size > n)
                topList.removeAt(n)
        }
        topList
    }
}

Таким образом, вы можете сравнить текущий элемент вашего списка только один раз с самым большим элементом из верхнего nэлементы, которые обычно бывают быстрее, чем сортировка всего списка https://pl.kotl.in/SyQPtDTcQ

Answer 3

Я предлагаю реализовать свой собственный метод сортировки, основанный на типичном алгоритме быстрой сортировки (в порядке убывания и взять первые N элементов), если коллекция имеет 1k + значений, распределенных случайным образом.

Answer 4

Вам есть о чем беспокоиться.

• collectionOrSequence.sortedby{it.value} запускает java.util.Arrays.sort, что запустит timSort (или mergeSort по запросу).
• timSort отлично, но обычно заканчивается n * log (n) операциями, что намного больше, чем O (n) копирования массива.
• Каждая из операций O (n * log.n) будетзапустите функцию (лямбда, которую вы указали, {it.value}) -> дополнительные значимые издержки.
• Наконец, java.util.Arrays.sort преобразует коллекцию в массив и обратно в список - 2 дополнительных преобразования (которые выхотел бы избежать, но это вторично)

Эффективный способ сделать это, вероятно, это:

1. map значения для сравнения в список: O (n) преобразования (один раз на элемент), а не O (n * log.n) или более.
2. Перебор списка (или массива), созданного для сбора наименьших элементов N за один проход
   • Сохраните список из N наименьших найденных элементов и их указатель в исходном списке.Если оно маленькое (например, 10 элементов) - mutableList хорошо подходит.
   • Сохраняйте переменную, содержащую максимальное значение для списка малых элементов.
   • При переборе исходной коллекции,сравните текущий элемент в исходном списке с максимальным значением списка малых значений.Если меньше его - замените его в «маленьком списке» и найдите в нем обновленное максимальное значение.
3. Используйте индексы из «маленького списка», чтобы извлечь 10 самых маленьких элементовисходный список.

Это позволит вам перейти от O (n * log.n) к O (n).

Конечно, если время критично - этовсегда лучше всего тестировать конкретный случай.

Если на первом этапе вам удалось извлечь примитивы для сравнения (например, int или long) - это было бы еще эффективнее.