Scala中的惰性迭代器是什么？

Question

我读到在Haskell中,当对迭代器进行排序时，只有在返回所评估的值数量的迭代器时才会评估qsort的尽可能多部分。(也就是说它是惰性的，即一旦完成第一个枢轴的LHS并且可以在"next"调用上提供一个值，它就可以提供那个值而不继续进行枢轴除非再次调用next).

例如, 在Haskell中，head（qsort list）是O(n)。 它只是在列表中找到最小值，并且在未访问qsort列表的其余结果的情况下不会对列表的其余部分进行排序。

是否有办法在Scala中实现这一点？我想在集合上使用sortWith，但仅排序所需的内容，这样我就可以mySeq.sortWith(<).take(3)，而不需要完成排序操作。

我想了解其他排序函数（如sortBy）是否可以以惰性方式使用，如何确保惰性以及查找关于Scala中排序何时或不惰性评估的其他文档。

更新/编辑: 我理想地希望通过标准排序函数（如sortWith）来实现这一点。 我不想为了获得惰性评估而实现自己的版本快速排序。 这不应该内置于标准库中吗，至少对于支持惰性的集合（如Stream）？

- nairbv

---

看起来我的问题有点重复：https://dev59.com/0E3Sa4cB1Zd3GeqPuVeI#zWgFoYgBc1ULPQZFpChg ...但我真正想要理解的是库内置功能，而不是我自己能实现什么。 - nairbv

Answer 1

我曾使用过Scala的优先队列实现来解决这种部分排序问题：

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)，获取前k个元素的成本为O(k log n)。

不幸的是，PriorityQueue无法按优先级顺序迭代，但编写一个调用dequeue方法的迭代器并不太难。

- Travis Brown

---

Iterator.tabulate(q.size)(_ => q.dequeue) - incrop

@incrop：没错，或者用 k 代替 q.size 如果你不需要全部。 - Travis Brown

@incrop，你可能想要使用Iterator.fill(k)(q.dequeue)，因为你没有使用tabulate提供的索引。 - dhg

Answer 2

举个例子，我创建了一个懒惰快速排序的实现，它创建了一个懒惰树结构（而不是生成结果列表）。这个结构可以在O(n)时间内请求任何第i个元素或k个元素的切片。再次请求相同的元素（或附近的元素）只需要O(log n)，因为上一步建立的树结构被重用。遍历所有元素需要O(n log n)的时间。（假设我们选择了合理的枢轴。）

关键在于子树不会立即构建，而是延迟进行懒惰计算。因此，当仅请求单个元素时，根节点在O(n)中计算，然后计算其子节点之一在O(n/2)中等等，直到找到所需的元素，花费O(n + n/2 + n/4 ...) = O(n)。当树完全评估时，选择任何元素都需要O(log n)，就像任何平衡树一样。

请注意，build的实现非常低效。我希望它尽可能简单易懂。重要的是它具有适当的渐进界限。

import collection.immutable.Traversable

object LazyQSort {
  /**
   * Represents a value that is evaluated at most once.
   */
  final protected class Thunk[+A](init: => A) extends Function0[A] {
    override lazy val apply: A = init;
  }

  implicit protected def toThunk[A](v: => A): Thunk[A] = new Thunk(v);
  implicit protected def fromThunk[A](t: Thunk[A]): A = t.apply;

  // -----------------------------------------------------------------

  /**
   * A lazy binary tree that keeps a list of sorted elements.
   * Subtrees are created lazily using `Thunk`s, so only
   * the necessary part of the whole tree is created for
   * each operation.
   *
   * Most notably, accessing any i-th element using `apply`
   * takes O(n) time and traversing all the elements
   * takes O(n * log n) time.
   */
  sealed abstract class Tree[+A]
    extends Function1[Int,A] with Traversable[A]
  {
    override def apply(i: Int) = findNth(this, i);

    override def head: A = apply(0);
    override def last: A = apply(size - 1);
    def max: A = last;
    def min: A = head;
    override def slice(from: Int, until: Int): Traversable[A] =
      LazyQSort.slice(this, from, until);
    // We could implement more Traversable's methods here ...
  }
  final protected case class Node[+A](
      pivot: A, leftSize: Int, override val size: Int,
      left: Thunk[Tree[A]], right: Thunk[Tree[A]]
    ) extends Tree[A]
  {
    override def foreach[U](f: A => U): Unit = {
      left.foreach(f);
      f(pivot);
      right.foreach(f);
    }
    override def isEmpty: Boolean = false;
  }
  final protected case object Leaf extends Tree[Nothing] {
    override def foreach[U](f: Nothing => U): Unit = {}
    override def size: Int = 0;
    override def isEmpty: Boolean = true;
  }

  // -----------------------------------------------------------------

  /**
   * Finds i-th element of the tree.
   */
  @annotation.tailrec
  protected def findNth[A](tree: Tree[A], n: Int): A =
    tree match {
      case Leaf => throw new ArrayIndexOutOfBoundsException(n);
      case Node(pivot, lsize, _, l, r)
                => if (n == lsize) pivot
                   else if (n < lsize) findNth(l, n)
                   else findNth(r, n - lsize - 1);
    }

  /**
   * Cuts a given subinterval from the data.
   */
  def slice[A](tree: Tree[A], from: Int, until: Int): Traversable[A] =
    tree match {
      case Leaf => Leaf
      case Node(pivot, lsize, size, l, r) => {
        lazy val sl = slice(l, from, until);
        lazy val sr = slice(r, from - lsize - 1, until - lsize - 1);
        if ((until <= 0) || (from >= size)) Leaf // empty
        if (until <= lsize) sl
        else if (from > lsize) sr
        else sl ++ Seq(pivot) ++ sr
      }
  }

  // -----------------------------------------------------------------

  /**
   * Builds a tree from a given sequence of data.
   */
  def build[A](data: Seq[A])(implicit ord: Ordering[A]): Tree[A] =
    if (data.isEmpty) Leaf
    else {
      // selecting a pivot is traditionally a complex matter,
      // for simplicity we take the middle element here
      val pivotIdx = data.size / 2;
      val pivot = data(pivotIdx);
      // this is far from perfect, but still linear
      val (l, r) = data.patch(pivotIdx, Seq.empty, 1).partition(ord.lteq(_, pivot));
      Node(pivot, l.size, data.size, { build(l) }, { build(r) });
    }
}

// ###################################################################

/**
 * Tests some operations and prints results to stdout.
 */
object LazyQSortTest extends App {
  import util.Random
  import LazyQSort._

  def trace[A](name: String, comp: => A): A = {
    val start = System.currentTimeMillis();
    val r: A = comp;
    val end = System.currentTimeMillis();
    println("-- " + name + " took " + (end - start) + "ms");
    return r;
  }

  {
    val n = 1000000;
    val rnd = Random.shuffle(0 until n);
    val tree = build(rnd);
    trace("1st element", println(tree.head));
    // Second element is much faster since most of the required
    // structure is already built
    trace("2nd element", println(tree(1)));
    trace("Last element", println(tree.last));
    trace("Median element", println(tree(n / 2)));
    trace("Median + 1 element", println(tree(n / 2 + 1)));
    trace("Some slice", for(i <- tree.slice(n/2, n/2+30)) println(i));
    trace("Traversing all elements", for(i <- tree) i);
    trace("Traversing all elements again", for(i <- tree) i);
  }
}

输出将会是类似这样的内容

0
-- 1st element took 268ms
1
-- 2nd element took 0ms
999999
-- Last element took 39ms
500000
-- Median element took 122ms
500001
-- Median + 1 element took 0ms
500000
  ...
500029
-- Slice took 6ms
-- Traversing all elements took 7904ms
-- Traversing all elements again took 191ms

- Petr

Answer 3

你可以使用一个 Stream 来构建类似的东西。这里有一个简单的例子，肯定可以做得更好，但它作为一个例子是有效的，我想。

def extractMin(xs: List[Int]) = {
  def extractMin(xs: List[Int], min: Int, rest: List[Int]): (Int,List[Int]) = xs match {
    case Nil => (min, rest)
    case head :: tail if head > min => extractMin(tail, min, head :: rest)
    case head :: tail => extractMin(tail, head, min :: rest)
  }

  if(xs.isEmpty) throw new NoSuchElementException("List is empty")
  else extractMin(xs.tail, xs.head, Nil)
}

def lazySort(xs: List[Int]): Stream[Int] = xs match {
  case Nil => Stream.empty
  case _ =>
    val (min, rest) = extractMin(xs)
    min #:: lazySort(rest)
}

- drexin