8

我有一个 Traversable，我想把它变成一个 Java 迭代器。我的问题是我希望一切都懒惰地完成。如果我在可遍历对象上执行 .toIterator，它会急切地生成结果，将其复制到 List 中，然后返回 List 上的迭代器。

我确定我在这里遗漏了一些简单的东西......

这是一个小测试用例，说明了我的意思：

class Test extends Traversable[String] {
      def foreach[U](f : (String) => U) {
         f("1")
         f("2")
         f("3")
         throw new RuntimeException("Not lazy!")
     }
}

val a = new Test
val iter = a.toIterator
4

2 回答 2

5

您不能从可遍历对象中懒惰地获取迭代器的原因是您本质上不能。Traversable 定义了foreach, 并且foreach不间断地遍历所有内容。那里没有懒惰。

所以你有两个选择，都很糟糕，让它变得懒惰。

首先，您可以每次都遍历整个内容。（我打算使用 Scala 迭代器，但 Java 迭代器基本相同。）

class Terrible[A](t: Traversable[A]) extends Iterator[A] {
  private var i = 0
  def hasNext = i < t.size   // This could be O(n)!
  def next: A = {
    val a = t.slice(i,i+1).head  // Also could be O(n)!
    i += 1
    a
  }
}

如果你碰巧有高效的索引切片，这没问题。如果不是，每个“下一个”将花费迭代器长度的线性O(n^2)时间，用于遍历它的时间。但这也不一定是懒惰的；如果您坚持必须是您必须O(n^2)在所有情况下强制执行并执行

class Terrible[A](t: Traversable[A]) extends Iterator[A] {
  private var i = 0
  def hasNext: Boolean = {
    var j = 0
    t.foreach { a =>
      j += 1
      if (j>i) return true
    }
    false
  }
  def next: A = { 
    var j = 0
    t.foreach{ a => 
      j += 1
      if (j>i) { i += 1; return a }
    }
    throw new NoSuchElementException("Terribly empty")
  }
}

对于通用代码来说，这显然是一个糟糕的主意。

另一种方法是使用线程并阻止 foreach 的遍历。没错，您必须对每个元素访问进行线程间通信！让我们看看它是如何工作的——我将在这里使用 Java 线程，因为 Scala 正在转换到 Akka 风格的演员（尽管任何旧演员或 Akka 演员或 Scalaz 演员或 Lift 演员或（等）将起作用）

class Horrible[A](t: Traversable[A]) extends Iterator[A] {
  private val item = new java.util.concurrent.SynchronousQueue[Option[A]]()
  private class Loader extends Thread {
    override def run() { t.foreach{ a => item.put(Some(a)) }; item.put(None) }
  }
  private val loader = new Loader
  loader.start
  private var got: Option[A] = null
  def hasNext: Boolean = {
    if (got==null) { got = item.poll; hasNext }
    else got.isDefined
  }
  def next = {
    if (got==null) got = item.poll
    val ans = got.get
    got = null
    ans
  }
}

这避免了O(n^2)灾难，但会占用一个线程并且逐个元素的访问速度极慢。我在我的机器上每秒获得大约 200 万次访问，而典型的可遍历则超过 100M。对于通用代码来说，这显然是一个可怕的想法。

所以你有它。一般来说，Traversable 并不懒惰，没有什么好的方法可以让它变得懒惰而不极大地影响性能。

于 2012-11-02T18:39:24.277 回答
1

我之前遇到过这个问题，据我所知，没有人对让你更容易获得Iterator当你定义的所有内容是foreach.

但正如您所指出的，toStream这是问题所在，因此您可以覆盖它：

class Test extends Traversable[String] {
  def foreach[U](f: (String) => U) {
    f("1")
    f("2")
    f("3")
    throw new RuntimeException("Not lazy!")
  }
  override def toStream: Stream[String] = {
    "1" #::
    "2" #::
    "3" #::
    Stream[String](throw new RuntimeException("Not lazy!"))
  }
}

另一种选择是定义 anIterable而不是 a Traversable，然后您将iterator直接获得该方法。您能否再解释一下您Traversable在实际用例中所做的事情？

于 2012-11-02T10:59:01.643 回答