2

理解のためにScalaの無限ストリームに対してネストされた反復を実行したい場合がありますが、ループの終了条件を指定するのは少し難しい場合があります。このようなことをするためのより良い方法はありますか？

私が念頭に置いているユースケースは、反復している無限のストリームのそれぞれから必要な要素の数を前もって必ずしも知らない場合です（ただし、明らかに、無限の数にはならないことはわかっています）。各ストリームの終了条件は、for式の他の要素の値に複雑な方法で依存する可能性があると想定します。

最初の考えは、 for式のifフィルター句としてストリーム終了条件を書き込もうとすることですが、最初の無限ストリームの反復を短絡する方法がないため、ネストされた無限ストリームをループするときに問題が発生します。これは最終的にOutOfMemoryErrorにつながります。式がmaptomap、flatMap、withFilterメソッドを呼び出す方法を考えると、これが当てはまる理由を理解しています-私の質問は、この種のことを行うためのより良いイディオムがあるかどうかです（おそらく理解にはまったく関係しません）。

今説明した問題を説明するためにやや不自然な例を示すために、次の（非常に単純な）コードを検討して、番号1と2のすべてのペアを生成します。

val pairs = for {
  i <- Stream.from(1) 
  if i < 3 
  j <- Stream.from(1) 
  if j < 3
} 
yield (i, j)

pairs.take(2).toList 
// result: List[(Int, Int)] = List((1,1), (1,2)) 

pairs.take(4).toList
// 'hoped for' result: List[(Int, Int)] = List((1,1), (1,2), (2,1), (2,2))
// actual result:
//  java.lang.OutOfMemoryError: Java heap space
//      at scala.collection.immutable.Stream$.from(Stream.scala:1105)

明らかに、この単純な例では、次のように、 ifフィルターを元のストリームのtakeWhileメソッド呼び出しに移動することで、問題を簡単に回避できます。

val pairs = for {
  i <- Stream.from(1).takeWhile(_ < 3) 
  j <- Stream.from(1).takeWhile(_ < 3) 
}    
yield (i, j)

しかし、質問の目的のために、ストリームの終了条件をストリーム式自体に簡単に移動できない、より複雑なユースケースを想像してみてください。

4

2 に答える 2

3

1つの可能性は、次のように、この場合は異なる方法でStream処理する独自のクラスにラップすることです。filtertakeWhile

import scala.collection._
import scala.collection.generic._

class MyStream[+A]( val underlying: Stream[A] ) {
  def flatMap[B, That](f: (A) => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = underlying.flatMap(f);

  def map[B, That](f: (A) ⇒ B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = underlying.map(f);

  def filter(p: A => Boolean): Stream[A] = underlying.takeWhile(p);
  //                                       ^^^^^^^^^^^^^^^^^^^^^^^^
}

object MyStream extends App {
  val pairs = for {
    i <- new MyStream(Stream.from(1))
    if i < 3
    j <- new MyStream(Stream.from(1))
    if j < 3
  } yield (i, j);

  print(pairs.toList);
}

これは印刷しList((1,1), (1,2), (2,1), (2,2))ます。

于 2012-12-25T16:32:30.887 に答える
1

私はPetrの提案を採用して、より一般的に使用できる解決策を考え出しました。これは、理解のためにifフィルターの配置に制限を課さないという点です（ただし、構文上のオーバーヘッドは少し多くなります）。

アイデアは、基礎となるストリームをラッパーオブジェクトで囲むことです。ラッパーオブジェクトは、メソッドとメソッドを変更せずに委任しますflatMapがmap、filter最初takeWhileに、述語を使用して基礎となるストリームに呼び出しを適用します。!isTruncatedここisTruncatedで、はラッパーオブジェクトに属するフィールドです。truncate任意の時点でラッパーオブジェクトを呼び出すと、isTruncatedフラグが反転し、ストリームでのさらなる反復が効果的に終了します。これは、基になるストリームの呼び出しが遅延評価されるという事実に大きく依存しているtakeWhileため、反復の後の段階で実行されるコードがその動作に影響を与える可能性があります。

|| s.truncate欠点は、フィルター式（sラップされたストリームへの参照）に追加することにより、反復の途中で切り捨てられるようにするストリームへの参照を保持する必要があることです。resetまた、繰り返しの反復が毎回同じように動作することがわかっている場合を除き、ストリームの新しい反復の前に必ずラッパーオブジェクトを呼び出す（または新しいラッパーオブジェクトを使用する）必要があります。

import scala.collection._
import scala.collection.generic._

class TruncatableStream[A]( private val underlying: Stream[A]) {
  private var isTruncated = false;

  private var active = underlying.takeWhile(a => !isTruncated)

  def flatMap[B, That](f: (A) => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = active.flatMap(f);

  def map[B, That](f: (A) => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = active.map(f);

  def filter(p: A => Boolean): Stream[A] = active.filter(p);

  def truncate() = {
    isTruncated = true
    false
  }

  def reset() = {
    isTruncated = false
    active = underlying.takeWhile(a => !isTruncated)
  }
}

val s1 = new TruncatableStream(Stream.from(1))
val s2 = new TruncatableStream(Stream.from(1))

val pairs = for {
  i <- s1

  // reset the nested iteration at the start of each outer iteration loop 
  // (not strictly required here as the repeat iterations are all identical)
  // alternatively, could just write: s2 = new TruncatableStream(Stream.from(1))  
  _ = _s2.reset()      

  j <- s2
  if i < 3 || s1.truncate
  if j < 3 || s2.truncate
} 
yield (i, j)

pairs.take(2).toList  // res1: List[(Int, Int)] = List((1,1), (1,2))
pairs.take(4).toList  // res2: List[(Int, Int)] = List((1,1), (1,2), (2,1), (2,2))

これは間違いなく改善される可能性がありますが、問題に対する合理的な解決策のようです。

于 2012-12-26T17:31:08.747 に答える