Почему реализация Stream / lazy val быстрее, чем ListBuffer - PullRequest
Новая
       17

Почему реализация Stream / lazy val быстрее, чем ListBuffer

3 голосов
/ 26 декабря 2010

Я кодировал следующую реализацию алгоритмов ленивого сита, используя Stream и lazy val ниже: 

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, первая реализация в 3 раза быстрее, чем вторая.Чем это объясняется? </p>

Я отредактировал вторую версию: она должна была быть sieve (3, ListBuffer (3)) вместо sieve (3, ListBuffer ()).

Ответы [ 2 ]

6 голосов
/ 26 декабря 2010

Ну, я думаю, это строка: 

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

On ListBuffer, takeWhile создает временную коллекцию (которая становится все больше и больше). Между тем, Stream из-за своей строгости избегает этого. Как только происходит сбой forall, он прекращает вычислять takeWhile.

2 голосов
/ 27 декабря 2010

Не совсем отвечаю на вопрос, но так как я провел несколько раз, сравнивая различные комбинации ...

Вы можете получить лучшую производительность, если будете использовать 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, чтобы получить поток, если это необходимо. 

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 петель, и это было быстрее, но менее понятно.

...