8

Traversableがあり、JavaIteratorにしたい。私の問題は、すべてを怠惰にやりたいということです。トラバーサブルで.toIteratorを実行すると、結果が熱心に生成され、リストにコピーされ、リスト上のイテレータが返されます。

私はここで簡単な何かが欠けていると確信しています...

これが私が何を意味するかを示す小さなテストケースです：

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停止することなくすべてを実行します。そこに怠惰はありません。

したがって、怠惰にするための2つのオプションがあり、どちらもひどいものです。

まず、毎回全体を繰り返すことができます。(ここでは 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")
  }
}

これは、一般的なコードでは明らかにひどい考えです。

もう 1 つの方法は、スレッドを使用して、進行中の foreach のトラバーサルをブロックすることです。そうです、要素アクセスごとにスレッド間通信を行う必要があります。それがどのように機能するか見てみましょう。Scala は Akka スタイルのアクターへの切り替えの最中なので、ここでは Java スレッドを使用します (ただし、古いアクター、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!"))
  }
}

別の方法Iterableとして、 a の代わりにan を定義すると、メソッドを直接Traversable取得できます。実際のユースケースでiterator何をしているのか、もう少し説明していただけますか?Traversable

于 2012-11-02T10:59:01.643 に答える