排序如何在惰性序列中工作？

Question

假设我正在处理惰性序列和某种无限序列，那么我尝试编写类似（伪代码）的内容：

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

在这种情况下，我先排序，然后取 10 个元素。排序函数如何对无限序列执行？

例如 Kotlin 序列：https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/sorted.html

Answer 1

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 = this@sortedWith.toMutableList()
            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) }

排序如何在惰性序列中工作？

How does sorting work in lazy sequences?

lazy-evaluation

lazy-sequences