3

以下のStreamとlazyvalを使用して、lazysieveアルゴリズムの次の実装をコーディングしました。

def primes(): Stream[Int] = {
   lazy val ps = 2 #:: sieve(3)
   def sieve(p: Int): Stream[Int] = {
       p #:: sieve(
            Stream.from(p + 2, 2).
             find(i=> ps.takeWhile(j => j * j <= i).
                     forall(i % _ > 0)).get)
  }
  ps
}

および（可変）ListBufferを使用した次の実装：

import scala.collection.mutable.ListBuffer
def primes(): Stream[Int] = {
    def sieve(p: Int, ps: ListBuffer[Int]): Stream[Int] = {
        p #:: { val nextprime =
            Stream.from(p + 2, 2).
            find(i=> ps.takeWhile(j => j * j <= i).
                 forall(i % _ > 0)).get
            sieve(nextprime, ps += nextprime)
         }
    }       
    sieve(3, ListBuffer(3))}

primes（）。takeWhile（_ <1000000）.sizeを実行したとき、最初の実装は2番目の実装より3倍高速です。これの説明は何ですか？

2番目のバージョンを編集しました。sieve（3、ListBuffer（））ではなくsieve（3、ListBuffer（3））である必要があります。

4

2 に答える 2

6

さて、私の推測では、次の行です。

find(i=> ps.takeWhile(j => j * j <= i).forall(i % _ > 0)).get

ListBufferで、一時的なコレクションを作成します (これtakeWhileはどんどん大きくなります)。一方、Streamは非厳密であるため、そうすることを避けています。が失敗するとすぐに、 のforall計算を停止しtakeWhileます。

于 2010-12-26T17:05:12.903 に答える
2

質問に実際に答えているわけではありませんが、さまざまな組み合わせのベンチマークに時間を費やしたので...

を使用し、内側のループを回避して、メモリ割り当てを最小限に抑えると、パフォーマンスが向上IteratorしArrayBufferますtakeWhile。

def primes2(): Stream[Int] = {
  def sieve(p: Int, ps: ArrayBuffer[Int]): Stream[Int] = {
    def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
      val n = ps(j)
      if (n*n > prime_?) true
      else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
    }
    p #:: { 
      val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
      sieve(nextprime, ps += nextprime)
    }
  }     
  sieve(3, ArrayBuffer(3))
}

Iteratorの代わりに を使用したバージョンを次に示します。Streamより高速で、primes3().toStream必要に応じていつでも Stream を取得するために使用できます。

def primes3() = List(2,3).iterator ++ new Iterator[Int] {
  val ps = ArrayBuffer[Int](3)
  def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
    val n = ps(j)
    if (n*n > prime_?) true
    else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
  }
  def hasNext = true
  def next() = {
    val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
    ps += nextprime
    nextprime
  }
}

結果：

primes : warming...
primes : running...
primes : elapsed: 3.711
res39: Int = 283145
primes2: warming...
primes2: running...
primes2: elapsed: 1.039
res40: Int = 283145
primes3: warming...
primes3: running...
primes3: elapsed: 0.530
res41: Int = 283146

fromまた、findとhasNoDivisorをいくつかのループに置き換えてみましwhileたが、これはより高速でしたが、わかりにくかったです。

于 2010-12-27T06:21:44.783 に答える