Scala performances - Sieve

Question

En ce moment, je suis en train d'apprendre Scala. J'ai commencé petit, écrire quelques algorithmes simples. Je l'ai rencontré quelques problèmes quand je voulais mettre en œuvre l'algorithme Sieve de trouver tous les nombres premiers inférieurs à un certain seuil.

Ma mise en œuvre est:

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(_))

    }
}

Malheureusement, il échoue quand je veux à l'ordinateur tous les nombres premiers plus petits que 1000000 (1 million). Je reçois OutOfMemory.

Avez-vous une idée sur la façon d'optimiser le code, ou comment puis-je mettre en œuvre cet algorithme de façon plus élégante.

PS. J'ai fait quelque chose de très semblable dans Haskell, et là, je ne l'ai pas rencontré de problèmes

Answer 1

J'aller avec un flux infini. En utilisant une structure de données paresseuse permet de coder à peu près comme dans Haskell. Il lit automatiquement plus « déclarative » que le code que vous avez écrit.

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)

De toute évidence, ce n'est pas l'approche la plus performante. Lire Le véritable Sieve d'Eratosthène pour une bonne explication (il est Haskell, mais pas trop difficile). Pour les plages réelles grandes que vous devriez considérer Sieve de Atkin.

Answer 2

Le code en question n'est pas récursive queue, donc Scala ne peut pas optimiser loin la récursion. En outre, Haskell est non stricte par défaut, vous ne pouvez donc pas comparer à peine à Scala. Par exemple, alors que les prestations Haskell de foldRight, les avantages Scala de foldLeft.

Il existe de nombreuses implémentations Scala de Sieve d'Eratosthène, y compris dans le débordement de pile. Par exemple:

(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 3

La réponse suivante est d'environ 100 fois plus rapide que le « one-liner » réponse à l'aide d'un ensemble (et les résultats ne ont pas besoin de tri à l'ordre croissant) et est plus d'une forme fonctionnelle que l'autre réponse à l'aide d'un tableau bien qu'il utilise un BitSet mutable comme une matrice de tamisage:

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

Il peut être testé par le code suivant:

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

Avec les résultats de la ci-dessus comme suit:

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

Il y a une surcharge de l'ordre de 40 millisecondes pour les gammes tamis même petites, et il y a différentes réponses non linéaires avec une plage de plus en plus que la taille de la BitSet se développe au-delà des différents caches du processeur.

Answer 4

Il ressemble à la liste est pas d'espace très effecient sage. Vous pouvez obtenir une exception de mémoire en faisant quelque chose comme ceci

1 to 2000000 toList

Answer 5

I "triché" et utilisé un tableau mutable. Je ne me sentais sale du tout.

  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
  }