Как работает сортировка в ленивых последовательностях?

Предполагая, что я работаю с ленивой последовательностью и своего рода бесконечной последовательностью, я пытаюсь написать что-то вроде (псевдокода):

Sequence([1,2,3,...])
   .sortDescending()
   .take(10);

В этом сценарии я сначала сортирую, а затем беру 10 элемента. Как функция сортировки будет работать в бесконечной последовательности?

Примером может служить последовательность Котлина: https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/sorted.html


lazy-evaluation lazy-sequences
person Afshin Mehrabani    schedule 18.02.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Метод sortDescending преобразует соответствующую последовательность в MutableList, который сортируется, а затем преобразуется обратно в новую последовательность. Ниже показана внутренняя функция sortedWith:

/**
 * Returns a sequence that yields elements of this sequence sorted according to the specified [comparator].
 * The operation is _intermediate_ and _stateful_.
 */
public fun <T> Sequence<T>.sortedWith(comparator: Comparator<in T>): Sequence<T> {
    return object : Sequence<T> {
        override fun iterator(): Iterator<T> {
            val sortedList = [email protected]()
            sortedList.sortWith(comparator)
            return sortedList.iterator()
        }
    }
}

Итак, когда у вас есть бесконечная последовательность, например:

generateSequence(1) {
    it * 2
}

и вы вызываете изображенную функцию в этой последовательности (а также функцию terminate, например forEach { println(it) }), все элементы в какой-то момент будут добавлены в список, что, скорее всего, не удастся из-за бесконечного цикла:

java.lang.OutOfMemoryError: Java heap space

Вероятно, вы захотите отсортировать фиксированное количество элементов, например, здесь:

generateSequence(1) {
    it * 2
}.take(10)
 .sortedDescending()
 .forEach { println(it) }
person s1m0nw1    schedule 18.02.2018