我已经读过在haskell中,在对迭代器进行排序时,它仅评估所需数量的qsort,以返回对生成的迭代器实际评估的值的数量(即,它是惰性的,即一旦完成LHS,并返回一个值,它可以在调用迭代器上的“next”时提供一个值,除非再次调用next,否则不会继续进行旋转。

例如,在haskell中,head(qsort list)为O(n)。它只会在列表中找到最小值,并且不会对列表的其余部分进行排序,除非访问了qsort list的其余结果。

有没有办法在Scala中做到这一点?我想在集合上使用sortWith,但仅按需要排序,这样我就可以mySeq.sortWith(
我想知道是否可以以惰性方式使用其他排序函数(例如sortBy),以及如何确保惰性,以及如何找到有关何时对Scala中的排序进行延迟评估的其他文档。

更新/编辑:我理想中是在寻找使用诸如sortWith之类的标准排序功能来做到这一点的方法。我宁愿不必为了获得懒惰的评估而实现自己的版本的quicksort。这是否应该内置到标准库中,至少对于诸如Stream这样支持惰性的集合而言?

最佳答案

我使用了Scala的priority queue implementation解决了这种部分排序问题:

import scala.collection.mutable.PriorityQueue

val q = PriorityQueue(1289, 12, 123, 894, 1)(Ordering.Int.reverse)

现在我们可以调用dequeue:
scala> q.dequeue
res0: Int = 1

scala> q.dequeue
res1: Int = 12

scala> q.dequeue
res2: Int = 123

建立队列需要O(n),而采用第一个O(k log n)元素则需要k

不幸的是PriorityQueue没有按优先级顺序进行迭代,但是编写调用dequeue的迭代器并不难。

关于scala - Scala中的各种懒惰迭代器?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12639320/

10-12 00:42
查看更多