Scala performance - Сито

Question

Прямо сейчас я пытаюсь выучить Scala. Я начал с малого, написав несколько простых алгоритмов. Я столкнулся с некоторыми проблемами, когда хотел реализовать алгоритм Sieve, чтобы найти все простые числа ниже определенного порога.

Моя реализация:

import scala.math

object Sieve {

    // Returns all prime numbers until maxNum
    def getPrimes(maxNum : Int) = {
        def sieve(list: List[Int], stop : Int) : List[Int] = {
            list match {
                case Nil => Nil
                case h :: list if h <= stop => h :: sieve(list.filterNot(_ % h == 0), stop)
                case _ => list
            }
        }
        val stop : Int = math.sqrt(maxNum).toInt
        sieve((2 to maxNum).toList, stop)
    }

    def main(args: Array[String]) = {
        val ap = printf("%d ", (_:Int)); 

        // works
        getPrimes(1000).foreach(ap(_))

        // works 
        getPrimes(100000).foreach(ap(_))

        // out of memory
        getPrimes(1000000).foreach(ap(_))

    }
}

К сожалению, происходит сбой, когда я хочу запрограммировать все простые числа меньше 1000000 (1 миллион). Я получаю OutOfMemory.

Есть ли у вас какие-либо идеи о том, как оптимизировать код или как я могу реализовать этот алгоритм более изящно.

PS: я сделал что-то очень похожее на Haskell, и там я не столкнулся с какими-либо проблемами.

Answer 1

Данный код не является хвостовой рекурсией, поэтому Scala не может оптимизировать эту рекурсию. Кроме того, Haskell не является строгим по умолчанию, поэтому вы вряд ли сможете сравнить его со Scala. Например, в то время как Haskell получает foldRight, Scala получает foldLeft.

Существует множество реализаций Scala из Эратосфена в Scala, в том числе в переполнении стека. Например:

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

Answer 2

Я бы пошел с бесконечным Потоком. Использование ленивой структуры данных позволяет кодировать почти так же, как в Haskell. Он автоматически читает более «декларативно», чем код, который вы написали.

import Stream._

val primes = 2 #:: sieve(3)

def sieve(n: Int) : Stream[Int] =
      if (primes.takeWhile(p => p*p <= n).exists(n % _ == 0)) sieve(n + 2)
      else n #:: sieve(n + 2)

def getPrimes(maxNum : Int) = primes.takeWhile(_ < maxNum)

Очевидно, что это не самый эффективный подход. Прочитайте Подлинное сито Эратосфена для хорошего объяснения (это Хаскель, но не слишком сложно). Для действительно больших диапазонов вы должны рассмотреть Сито Аткина .

Answer 3

Следующий ответ примерно в 100 раз быстрее, чем «однострочный» ответ с использованием набора (и результаты не нуждаются в сортировке по возрастанию) и является более функциональной формой, чем другой ответ использует массив , хотя он использует изменяемый BitSet в качестве просеивающего массива:

object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    }
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
  }
}

Это можно проверить по следующему коду:

object Main extends App {
  import SoE._
  val top_num = 10000000
  val strt = System.nanoTime()
  val count = makeSoE_Primes(top_num).size
  val end = System.nanoTime()
  println(s"Successfully completed without errors. [total ${(end - strt) / 1000000} ms]")
  println(f"Found $count primes up to $top_num" + ".")
  println("Using one large mutable1 BitSet and functional code.")
}

С результатами вышеизложенного:

Successfully completed without errors. [total 294 ms]
Found 664579 primes up to 10000000.
Using one large mutable BitSet and functional code.

Служебная нагрузка составляет около 40 миллисекунд даже для небольших диапазонов сит, и существуют различные нелинейные отклики с увеличением диапазона по мере того, как размер BitSet выходит за пределы разных кэшей ЦП.

Answer 4

Я "обманул" и использовал изменяемый массив. Не чувствовал себя грязным вообще.

  def primesSmallerThan(n: Int): List[Int] = {
    val nonprimes = Array.tabulate(n + 1)(i => i == 0 || i == 1)
    val primes = new collection.mutable.ListBuffer[Int]
    for (x <- nonprimes.indices if !nonprimes(x)) {
      primes += x
      for (y <- x * x until nonprimes.length by x if (x * x) > 0) {
        nonprimes(y) = true
      }
    }
    primes.toList
  }

Answer 5

Похоже, Список не очень эффективен в космическом плане. Вы можете получить исключение нехватки памяти, выполнив что-то вроде этого

1 to 2000000 toList