Traversable => Java Iterator

Question

我有一个Traversable,我想把它变成一个Java Iterator.我的问题是我希望一切都懒得完成.如果我在遍历上执行.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

Answer 1

你不能懒得从一个遍历得到一个迭代器的原因是你本质上不能.Traversable定义foreach并foreach贯穿所有内容而不会停止.那里没有懒惰.

所以你有两种选择,既可怕,也可以让它变得懒惰.

首先,您可以每次迭代整个事物.(我将使用Scala Iterator,但Java Iterator基本相同.)

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
  }
}

如果您碰巧有效的索引切片,这将是可以的.如果没有,每个"next"将在迭代器的长度上花费时间线性,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一般不会变得懒惰,并且没有很好的方法可以让它变得懒惰而不会极大地影响性能.

Answer 2

我以前遇到过这个问题，据我所知，没有人对Iterator在您定义的所有内容时更容易获得 an 特别感兴趣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在实际用例中所做的事情吗？