12

メモリ使用量を一定に保つために、結果をメモ化せずに、一度に1つの要素で作業できる、無限の非厳密な系列x 1、x 2、x3 ...が必要です。特異性のために、それが一連​​の整数（たとえば、自然数、奇数、素数）であるとしましょう。ただし、この質問は、より一般的なデータ型に当てはまる場合があります。

無限リストを操作する最も簡単な方法は、ScalaのStreamオブジェクトを使用することです。一般的なイディオムは、を返し、演算子をStream使用して系列に項を追加し、それ自体を再帰的に呼び出す関数を作成することです。#::たとえば、次の例では、開始値と後続関数が指定された整数の無限ストリームが生成されます。

  def infiniteList(n: Int, f: Int => Int): Stream[Int] = {
      n #:: infiniteList(f(n), f)
  }
  infiniteList(2, _*2+3).take(10) print
  // returns 2, 7, 17, 37, 77, 157, 317, 637, 1277, 2557, empty

（上記はライブラリ呼び出しと同等であることに気付きました。この無限のイディオムStream.iterate(2)(_*2+3)の例としてここに書きました。）Stream

ただし、ストリームは結果をメモ化するため、メモリ要件が一定ではなく、非常に大きくなる可能性があります。ドキュメントには、の頭を保持しないとメモ化が回避されると記載されていますStreamが、実際にはこれは注意が必要な場合があります。ストリームヘッドを保持しているとは思わない無限リストコードを実装することもできますが、それでも無制限のメモリ要件がある場合は、ストリームを何らかの方法で処理していることが問題かどうかを判断する必要があります。それはメモ化を引き起こします、またはそれが何か他のものである場合。これは難しいデバッグタスクになる可能性があり、明示的にメモ化されたデータ構造をだましてメモ化されていない結果を返すようにしようとしているため、コードの臭いがあります。

私が欲しいのは、Streamメモ化せずに期待するというセマンティクスを持つものです。そのようなオブジェクトがScalaに存在するようには見えません。私はイテレータを使用して無限の数値系列を実装することを試みてきましたが、イテレータの可変性により、イテレータに対して理解操作を実行したい場合、これは注意が必要です。また、独自のコードを最初から作成しようとしましたが、どこから始めればよいのか（サブクラス化するのか？）、、、などの機能の再実装を回避する方法が明確ではありませんTraversable。mapfold

誰かが、厳密ではなく、不変で、メモ化されていない無限リストの実装の良い例のScalaコードを持っていますか？

より一般的には、トラバース可能、反復可能、シーケンス、ストリーム、およびビューのセマンティクスを理解していますが、この質問を非常に厄介に感じているという事実は、私が何かを誤解しているように感じさせます。非厳密性と非メモ化は完全に直交する特性であるように私には思えますが、Scalaはそれらを統合する設計上の決定を下し、それらをStream簡単に切り離す方法を与えていないようです。これはScala側の見落としですか、それとも私が見落としている非厳密性と非メモ化の間に深い関係がありますか？

質問はかなり抽象的なものだと思います。これは、それを特定の問題に結び付けるいくつかの追加のコンテキストです。

MeissaO'Niellの論文「TheGenuineSieveof Eratosthenes 」で説明されているように、素数ジェネレーターを実装する過程でこの問題が発生します。Iteratorオブジェクトが不十分である場合の簡単な例を、多くのその論文からの詳細。これは、非常にエレガントであるが、疑わしいほど大量のメモリを消費するストリームを使用した完全な実装 です。

これは、コンパイルされないが、私が何を望んでいるかについてのアイデアを提供するイテレーターを使用した単純化された実装です。

import scala.collection.mutable

object ONeillSieve {

  class NumericSeries extends BufferedIterator[Int] with Ordered[NumericSeries] {
    def hasNext = true

    def compare(that: NumericSeries) = that.head.compare(head)

    override def toString() = head + "..."

    var head = 3

    def next() = {
      val r = head
      head += 2
      r
   }
 }

def main(args: Array[String]) {
    val q = mutable.PriorityQueue[NumericSeries]()

    val odds = new NumericSeries

    q += odds.map(odds.head * _)
    odds.next()
    q += odds.map(odds.head * _)

    println("Sieve = %s\nInput = %s".format(q, odds))
  }
}

PriorityQueue最小の要素をキーとする無限の数値級数を作成する必要があります。（したがってBufferedIterator、単純なものではなく、を使用しIteratorます。）また、ここで無限級数の基礎は奇数の整数ですが、最も一般的な解決策には、より複雑な級数が含まれることに注意してください。main関数の最後に、キューに2つの無限級数を含める必要があります。

  1. 3x（3から始まるオッズ）（つまり、9,12,15 ...）
  2. 5x（5から始まるオッズ）（つまり、25、30、35 ...）

上記はコンパイルされません。これは、をodds.map(...)返すのIteratorではなく、NumericSeriesを返すため、優先キューに追加できないためです。

この時点で、私はコレクションクラスの拡張機能に取り組んでいるように見えますが、それは注意が必要なので、どうしても必要な場合を除いて、それを行う必要がないことを確認したいと思います。

4

4 に答える 4

3

EDIT: The below doesn't preserve the Generator type when using filter or map; indeed trying to implement a full 'MyType' for the generator is more or less impossible (look into IndexedSeqView source code to see the mess).

But there is an even easier way around (see my third answer)

Ok, my second try. In order to keep the lazy behaviour for map, filter, etc., the best might be to subclass SeqView or StreamView:

import collection.immutable.StreamView

final case class Generator[A](override val head: A, fun: A => A)
extends StreamView[A, Generator[A]] {
  protected def underlying = this
  def length: Int = Int.MaxValue  // ?
  def iterator = Iterator.iterate(head)(fun)
  def apply(idx: Int): A = {
    if(idx < 0) throw new IndexOutOfBoundsException(idx.toString)
    var res = head
    var i = idx; while(i > 0) {
      res = fun(res)
      i -= 1
    }
    res
  }
}

(I took Rex' suggestion to call this "Generator").

val i = Generator[Int](2, _ * 2 + 3)
i.take(4).foreach(println)
val j = i.map(_ * 0.5)
j.take(4).foreach(println)
于 2013-01-12T22:51:59.503 に答える
1

リストを数回再帰できるようにする必要があるだけの場合Unit => Iterator[A]は、元のリストの代わりに作業してみてください。次の再構築を試してください。

// Old way
val i = Iterator.tabulate(5)(_ + 2)
val j = i.map(_*5)
val k = i.map(_*3)
println(j.mkString(" "))  // Prints 10, 15, 20, 25, 30 as it should
println(k.mkString(" "))  // Prints nothing!  (i was used up!)

// New way
val f = (u: Unit) => Iterator.tabulate(5)(_+2)
val g = f andThen (_.map(_*5))
val h = f andThen (_.map(_*3))
println(g(()).mkString(" "))  // 10, 15, 20, 25, 30
println(h(()).mkString(" "))  // 6, 9, 12, 15, 18

しかし、これはすべて最初からやり直します。途中から新しい作業を開始する必要がある場合は、どこまで進んだかの間にすべての中間要素を保存する意思がある限り、それを行う方法もあります。

val a = Iterator.tabulate(5)(_+2)
val (a1,a2) = a.duplicate
val c = a1.map(_*5)
val d = a2.map(_*3)
println(c.mkString(" "))  // 10, 15, 20, 25, 30...but stores a=2, 3, 4, 5, 6
println(d.mkString(" "))  // 6, 9, 12, 15, 18

このパターンも他のパターンも十分でない場合は、コレクション ライブラリにクラスを作成する必要がありGeneratorます。Iteratororから継承し、内部生成関数とデータを同じ状態で 2 つの新しいコピーをIterable作成するメソッドをオーバーライドまたは作成します。duplicate

于 2013-01-12T22:22:24.960 に答える
1

これがおそらく最も簡単なアプローチです。lazy を作成するだけIterableです：

object Generator {
  def apply[A](head: A)(next: A => A): Generator[A] = {
    val _head = head
    new collection.IterableView[A, Nothing] {
      override def head = _head
      def underlying = sys.error("No underlying structure")
      def iterator = Iterator.iterate(head)(next)
    }
  }
}
type Generator[A] = Iterable[A]

ユースケースは次のとおりです。

val q = collection.mutable.PriorityQueue[Generator[Int]]()
val odds = Generator(3)(_ + 2)
q += odds.map(odds.head * _)
val next = odds.tail
q += next.map(next.head * _)
q.last.take(3).mkString(",") // -> 9,12,21
q.head.take(3).mkString(",") // -> 25,35,45
于 2013-01-13T00:33:55.857 に答える
0

編集:参照用にこの回答をここに残しますが、スタックオーバーフローに遭遇しないようにするには、デフォルトで遅延しているコレクションを使用するのが最善であることがわかりました: SeqView->他の回答を参照してください。

新しいコレクション型を定義したい場合、これは私が想像するものです:

import collection.generic.{GenericTraversableTemplate, GenericCompanion}
import collection.immutable.LinearSeq

final case class InfSeq[A](override val head: A, fun: A => A)
extends LinearSeq[A] with GenericTraversableTemplate[A, List] {
  override def companion: GenericCompanion[List] = List

  def apply(idx: Int): A = {
    if(idx < 0) throw new IndexOutOfBoundsException(idx.toString)
    var res = head
    var i   = idx
    while(i > 0) {
      res = fun(res)
      i  -= 1
    }
    res
  }

  def length            = Int.MaxValue  // ?
  override def isEmpty  = false  
  override def tail     = InfSeq(fun(head), fun)
  override def toString = take(4).mkString("InfSeq(", ",", ",...)")
}

元。

val i = InfSeq[Int](2, _ * 2 + 3)
i.take(4).foreach(println)

明らかに、それは 、 などの機能をまだ解決していませmapんfilter。しかし、慎重に使用すれば.view問題ないはずです。

val j = i.view.map(_ * 0.5)
j.take(4).foreach(println)
于 2013-01-12T22:27:09.493 に答える