可遍历 => Java 迭代器

Question

我有一个可遍历，我想将其制成java迭代器。我的问题是我希望一切都懒惰地完成。如果我在可遍历上执行。

我确定我在这里缺少一些简单的东西...

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

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

Answer 1

您无法懒惰地从可穿越的迭代器中获得迭代器的原因是您本质上不能。Traverable定义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演员（等）将起作用）

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。对于一般代码而言，这显然是一个可怕的想法。

所以你有。遍历一般并不懒惰，没有很好的方法可以使它懒惰而不会造成极大的损害。

Answer 2

据我所知，我遇到了这个问题，当您定义的所有内容是foreach时，没有人特别感兴趣地更容易获得Iterator。

但是，正如您所指出的，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!"))
  }
}

另一种选择是定义Iterable而不是Traversable，然后直接获得iterator方法。您能否再解释您的Traversable在您的真实用例中正在做什么？