14

私は Scala に非常に慣れていないので、私の無知を許してください! 最大値に制限された整数のペアを反復しようとしています。たとえば、最大値が 5 の場合、反復は次のように返されます。

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

これをストリームとして末尾再帰的に返すことにしました。

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

tailrec 注釈がないと、コードは機能します。

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4))

しかし、これは私には十分ではありません。コンパイラは、_pairs の最後の行が _pairs を返していないことを正しく指摘しています。

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position
    else (i, j) #:: _pairs(i, j + 1, maximum)
                ^

だから、私はいくつかの質問があります：

  • 上記の実装に直接対処すると、どのように末尾再帰的に Stream[(Int, Int)] を返すのでしょうか?
  • 一歩下がって、整数の制限されたシーケンスを反復処理する最もメモリ効率の良い方法は何ですか? Range は IndexedSeq を拡張するため、Range を反復処理したくありません。また、シーケンス全体をメモリ内に存在させたくありません。それとも私が間違っていますか？Range.view を繰り返し処理すると、それがメモリに入らないようにできますか?

Python (!) では、私が欲しいのは次のとおりです。

In [6]: def _pairs(maximum):
   ...:     for i in xrange(maximum+1):
   ...:         for j in xrange(maximum+1):
   ...:             yield (i, j)
   ...:             

In [7]: p = _pairs(5)

In [8]: [p.next() for i in xrange(11)]
Out[8]: 
[(0, 0),
 (0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (0, 5),
 (1, 0),
 (1, 1),
 (1, 2),
 (1, 3),
 (1, 4)]

ご協力いただきありがとうございます！参考文献や API ドキュメントなどを読む必要があると思われる場合は、教えてください。私は学びたいと思っているからです。

4

2 に答える 2

28

これは末尾再帰ではありません

ストリームの代わりにリストを作成していたとしましょう:

def foo(n: Int): List[Int] =
  if (n == 0)
    0 :: Nil
  else
    n :: foo(n - 1)

この再帰の一般的なケースでfoo(n - 1)は、関数が返された後、返されたリストで何かを行う必要があります。リストの先頭に別の項目を連結する必要があります。したがって、再帰の後にリストに対して何かを行う必要があるため、関数を末尾再帰にすることはできません。

末尾再帰がないと、 の値が大きくなるとn、スタック スペースが不足します。

通常のリストソリューション

ListBuffer通常の解決策は、a を 2 番目のパラメーターとして渡し、それを埋めることです。

def foo(n: Int) = {
  def fooInternal(n: Int, list: ListBuffer[Int]) = {
    if (n == 0) 
      list.toList
    else {
      list += n
      fooInternal(n - 1, list)
    }
  }
  fooInternal(n, new ListBuffer[Int]())
}

あなたがやっていることは「末尾再帰 modulo cons 」として知られています。これは、 LISP Prolog コンパイラが末尾再帰 modulo cons パターンを見たときに自動的に実行する最適化です。これは非常に一般的であるためです。Scala のコンパイラはこれを自動的に最適化しません。

ストリームは末尾再帰を必要としません

ストリームは、スタック スペースが不足するのを避けるために末尾再帰を必要としません。これは、ストリームが巧妙なトリックを使用して、再帰呼び出しがfooコードに現れるポイントで実行されないようにするためです。関数呼び出しはサンクでラップされ、実際にストリームから値を取得しようとした時点でのみ呼び出されます。一度にアクティブになるのは の1 つの呼び出しだけfooです。再帰的ではありません。

ここ Stackoverflow でオペレーターがどのように#::機能するかを説明する以前の回答を書きました。次の再帰ストリーム関数を呼び出すと、次のようになります。(数学的な意味では再帰的ですが、通常期待されるように、関数呼び出し内から関数呼び出しを行うわけではありません。)

def foo(n: Int): Stream[Int] =
  if (n == 0)
    0 #:: Nil
  else
    n #:: foo(n - 1)

を呼び出すとfoo(10)、1 つの要素が既に計算されたストリームが返されます。末尾は、foo(9)次にストリームから要素が必要になったときに呼び出されるサンクです。foo(9)は現在呼び出されていません。むしろ、呼び出しはlazy valストリーム内にバインドされており、foo(10)すぐに戻ります。最終的にストリーム内の 2 番目の値が必要になったときに、foo(9)が呼び出され、1 つの要素を計算し、ストリームの末尾を を呼び出すサンクに設定しますfoo(8)。foo(9)を呼び出さずにすぐに戻りますfoo(8)。等々...

これにより、メモリを使い果たすことなく、無限のストリームを作成できます。次に例を示します。

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1)

(このストリームでどの操作を呼び出すかに注意してください。 aforEachまたは aを実行しようとするとmap、ヒープ全体がいっぱいになりますtakeが、ストリームの任意のプレフィックスを操作するには、を使用するのが良い方法です。)

全体的にシンプルなソリューション

再帰とストリームを扱う代わりに、Scala のforループを使用してみませんか?

def pairs(maximum:Int) =
  for (i <- 0 to maximum;
       j <- 0 to maximum)
    yield (i, j)

これにより、メモリ内のコレクション全体が実体化され、 が返されますIndexedSeq[(Int, Int)]。

特に Stream が必要な場合は、最初の範囲をStream.

def pairs(maximum:Int) =
  for (i <- 0 to maximum toStream;
       j <- 0 to maximum)
    yield (i, j)

これは を返しますStream[(Int, Int)]。シーケンスの特定のポイントにアクセスすると、それはメモリに実体化され、その要素の前のストリーム内の任意のポイントへの参照が残っている限り保持されます。

両方の範囲をビューに変換することで、メモリ使用量をさらに改善できます。

def pairs(maximum:Int) =
  for (i <- 0 to maximum view;
       j <- 0 to maximum view)
    yield (i, j)

SeqView[(Int, Int),Seq[_]]これは、必要になるたびに各要素を計算する を返し、事前計算された結果を保存しません。

同じ方法でイテレータ (1 回しかトラバースできない) を取得することもできます。

def pairs(maximum:Int) =
  for (i <- 0 to maximum iterator;
       j <- 0 to maximum iterator)
    yield (i, j)

それは を返しますIterator[(Int, Int)]。

于 2012-05-09T23:26:03.530 に答える
2

イテレータの方が適しているのではないでしょうか?

class PairIterator (max: Int) extends Iterator [(Int, Int)] {
  var count = -1
  def hasNext = count <= max * max 
  def next () = { count += 1; (count / max, count % max) }
}

val pi = new PairIterator (5)
pi.take (7).toList
于 2012-05-10T01:06:59.753 に答える