Perché Ruscello / pigro implementazione val utilizzando è più veloce di un ListBuffer

Question

I codificato la seguente implementazione di algoritmi setaccio pigri con Stream e val pigro sotto:

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
}

e la successiva implementazione utilizzando (mutevole) 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))}

Quando ho fatto numeri primi (). TakeWhile (_ <1000000) .size, la prima implementazione è 3 volte più veloce rispetto alla seconda. Qual è la spiegazione per questo?

Ho modificato la seconda versione: avrebbe dovuto essere setaccio (3, ListBuffer (3)), invece di setaccio (3, ListBuffer ())

.

Answer 1

Bene, la mia ipotesi è questa linea:

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

Il ListBuffer, takeWhile crea una raccolta temporanea (che diventa sempre più grande e più grande). Nel frattempo, Stream, a causa della sua non-severità, evita di farlo. Non appena il forall fallisce, si ferma il calcolo del takeWhile.

Answer 2

Non proprio di rispondere alla domanda, ma dal momento che ho trascorso alcuni momenti di benchmarking varie combinazioni ...

È possibile ottenere prestazioni migliori se si utilizza Iterator, ArrayBuffer e evitare di takeWhile nel ciclo interno, per ridurre al minimo le allocazioni di memoria.

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))
}

Ecco una versione con Iterator invece di Stream, è più veloce e si può sempre utilizzare primes3().toStream per ottenere un flusso, se necessario.

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
  }
}

Risultati:

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

Ho anche provato a sostituire from, find e hasNoDivisor con un paio di cicli while, e che era più veloce, ma meno comprensibile.