Pourquoi est-ce scala génération premier si la mémoire / lente intensive?

Question

Je manque de mémoire tout en trouvant le nombre premier 10001e.

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

Est-ce parce que, après chaque « itération » (est-ce le terme correct dans ce contexte?) De primes, j'augmenter la pile de fonctions à appeler pour obtenir l'élément suivant par un?

Une solution que je l'ai trouvé sur le web qui ne recourt pas à une solution itérative (que je voudrais éviter d'entrer dans la programmation fonctionnelle / idiomatiques scala) est cette (problème 7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

D'après ce que je peux voir, cela ne conduit pas à cette récursivité comme façon. Est-ce une bonne façon de le faire, ou connaissez-vous une meilleure façon?

Answer 1

Une raison pour laquelle cela est lent que est pas le tamis d'Eratosthène. Lire http://www.cs.hmc.edu/~oneill/ papiers / Sieve-JFP.pdf pour une explication détaillée (les exemples sont en Haskell, mais peuvent être traduits directement en Scala).

Mon ancienne solution pour le problème Euler # 7 n'a pas été le « vrai » tamis de soit, mais il semble fonctionner assez de bon pour les petits nombres:

object Sieve {

    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 main(args: Array[String]) {
      println(primes(10000)) //note that indexes are zero-based
    }
}

Je pense que le problème avec votre première version est que vous avez seulement defs et non val qui recueille les résultats et peut être consulté par la fonction de production, de sorte que vous recalcule toujours à partir de zéro.

Answer 2

Oui, il est parce que vous « augmentez la pile de fonctions à appeler pour obtenir l'élément suivant, par un après chaque "itération" "- à savoir ajouter un nouveau filtre sur le dessus de la pile de filtres à chaque fois après avoir obtenu chaque prime. C'est beaucoup trop de filtres .

Cela signifie que chaque produit est testé premier par tous ses nombres premiers précédents - mais seulement ceux en dessous de sa racine carrée sont vraiment nécessaires. Par exemple, pour obtenir le 10001 ème prime, 104743, il y aura 10000 filtres créés , lors de l'exécution. Mais il y a seulement 66 nombres premiers, ci-dessous 323 la racine carrée de 104743, donc seulement 66 filtres ont vraiment besoin . Tous les autres 9934 seront là inutilement, en prenant la mémoire, dur au travail produisant de la valeur ajoutée absolument pas.

Ce est la grave lacune de ce « tamis fonctionnel », qui semble avoir son origine dans le code des années 1970 par David Turner, et ont plus tard trouvé son chemin dans < a href = "http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html" rel = "nofollow noreferrer"> le livre de SICP et d'autres endroits. Il est pas que c'est un division d'essai tamis (plutôt que le tamis d'Eratosthène ). C'est beaucoup trop à distance une préoccupation pour elle. Section de première instance, lorsque optimale mise en œuvre, est parfaitement capable de produire le premier de 10000e très rapide.

La grave lacune de ce code est qu'il ne retarde pas la création de filtres au bon moment, et finit par créer beaucoup trop d'entre eux.

complexités Parler maintenant, le code "vieux tamis" est O (n ² ) , nombres premiers n produits . La division d'essai optimal est O (n ^1,5 / log ^0,5 (n)) , et le tamis de Eratosthènes est O (n * log (n) * log (log (n))) . Comme commandes empiriques de la croissance la première est généralement considérée comme ~ n^2, la seconde et la troisième ~ n^1.45 ~ n^1.2.

Vous pouvez trouver des générateurs à base de Python code pour la division d'essai optimale mis en œuvre dans cette réponse (2ème moitié) . Il était initialement discuté ici traitant de l'équivalent Haskell de votre fonction tamis.

---

Tout comme une illustration, un "lisible pseudocode" :) pour l'ancien tamis est

primes = sieve [2..]  where
   sieve (x:xs) = x : sieve [ y | y <- xs, rem y x > 0 ]
                         -- list of 'y's, drawn from 'xs',
                         --         such that (y % x > 0)

et pour la division d'essai optimal (TD) du tamis, synchronisé sur les carrés de nombres premiers,

primes = sieve [2..] primes   where
  sieve (x:xs) ps = x : (h ++ sieve [ y | y <- t, rem y p > 0 ] qs)
          where
            (p:qs) = ps     -- 'p' is head elt in 'ps', and 'qs' the rest
            (h,t)  = span (< p*p) xs    -- 'h' are elts below p^2 in 'xs'
                                        -- and 't' are the rest

et un tamis d'Eratosthène , conçu par Richard Bird , comme on le voit dans cet article de JFP mentionné dans une autre réponse ici,

primes = 2 : minus [3..] 
               (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] primes)
                      -- function of 'p' and 'r', that returns 
                      -- a list with p^2 as its head elt, ...

Court et rapide. ( minus a b est une a liste avec tous les elts de b progressivement retiré de celui-ci; < a href = "http://en.wikipedia.org/wiki/Haskell_features#Hamming_numbers" rel = "nofollow noreferrer"> union a b est une liste a avec tous les elts de b progressivement ajouté à sans doubles, à la fois traitant de l'ordre, non décroissante listes). foldr est le droit fois d'une liste. Parce qu'il est linéaire fonctionne à ce ~ n^1.33, pour le faire fonctionner à l'~ n^1.2 arbre ressemblant à plier la fonction foldi peut être utilisé).

---

La réponse à la deuxième question est aussi un yes . Votre deuxième code, re-écrit en même "pseudo-code",

ps = 2 : [i | i <- [3..], all ((> 0).rem i) (takeWhile ((<= i).(^2)) ps)]

est très similaire au tamis optimal TD ci-dessus - à la fois les dispositions nécessaires pour chaque candidat à tester par tous les nombres premiers en dessous de sa racine carrée. Alors que le tamis qui prend des dispositions avec une séquence d'exécution des filtres différés, cette dernière définition récupère de nouveau les nombres premiers nécessaires à nouveau pour chaque candidat. On pourrait être plus rapide qu'un autre en fonction d'un compilateur, mais les deux sont essentiellement les mêmes.

Et le troisième est aussi un yes : le tamis d'Eratosthène est mieux,

ps = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- drop 1 ps])

unionAll = foldi union' []          -- one possible implementation
union' (x:xs) ys = x : union xs ys
   -- unconditionally produce first elt of the 1st arg 
   -- to avoid run-away access to infinite lists

On dirait qu'il peut être mis en œuvre Scala aussi, à en juger par la similitude des autres extraits de code. (Bien que je ne sais pas Scala). unionAll ici met en œuvre la structure de pliage arborescente

FWIW, voici un vrai Sieve d'Eratosthène:

def sieve(n: Int) = (2 to math.sqrt(n).toInt).foldLeft((2 to n).toSet) { (ps, x) => 
    if (ps(x)) ps -- (x * x to n by x) 
    else ps
}

Voici un flux infini de nombres premiers en utilisant une variante de la Sieve d'Eratosthène qui conserve ses propriétés fondamentales:

case class Cross(next: Int, incr: Int)

def adjustCrosses(crosses: List[Cross], current: Int) = {
  crosses map {
    case cross @ Cross(`current`, incr) => cross copy (next = current + incr)
    case unchangedCross                 => unchangedCross
  }
}

def notPrime(crosses: List[Cross], current: Int) = crosses exists (_.next == current)

def sieve(s: Stream[Int], crosses: List[Cross]): Stream[Int] = {
    val current #:: rest = s

    if (notPrime(crosses, current)) sieve(rest, adjustCrosses(crosses, current))
    else current #:: sieve(rest, Cross(current * current, current) :: crosses)
}

def primes = sieve(Stream from 2, Nil)

Il est un peu difficile à utiliser, cependant, puisque chaque élément du Stream est composé en utilisant la liste crosses, qui a autant de chiffres car il y a eu des nombres premiers jusqu'à un certain nombre, et il semble que, pour une raison quelconque, ces des listes sont conservés en mémoire pour chaque numéro dans le Stream.

Par exemple, vous êtes invité par un commentaire, primes take 6000 contains 56993 jetterait une exception GC alors que primes drop 5000 take 1000 contains 56993 retournerait un résultat assez rapide sur mes tests.

Answer 3

Answer 4

Answer 5

FWIW, voici un vrai Sieve d'Eratosthène:

def sieve(n: Int) = (2 to math.sqrt(n).toInt).foldLeft((2 to n).toSet) { (ps, x) => 
    if (ps(x)) ps -- (x * x to n by x) 
    else ps
}

Voici un flux infini de nombres premiers en utilisant une variante de la Sieve d'Eratosthène qui conserve ses propriétés fondamentales:

case class Cross(next: Int, incr: Int)

def adjustCrosses(crosses: List[Cross], current: Int) = {
  crosses map {
    case cross @ Cross(`current`, incr) => cross copy (next = current + incr)
    case unchangedCross                 => unchangedCross
  }
}

def notPrime(crosses: List[Cross], current: Int) = crosses exists (_.next == current)

def sieve(s: Stream[Int], crosses: List[Cross]): Stream[Int] = {
    val current #:: rest = s

    if (notPrime(crosses, current)) sieve(rest, adjustCrosses(crosses, current))
    else current #:: sieve(rest, Cross(current * current, current) :: crosses)
}

def primes = sieve(Stream from 2, Nil)

Il est un peu difficile à utiliser, cependant, puisque chaque élément du Stream est composé en utilisant la liste crosses, qui a autant de chiffres car il y a eu des nombres premiers jusqu'à un certain nombre, et il semble que, pour une raison quelconque, ces des listes sont conservés en mémoire pour chaque numéro dans le Stream.

Par exemple, vous êtes invité par un commentaire, primes take 6000 contains 56993 jetterait une exception GC alors que primes drop 5000 take 1000 contains 56993 retournerait un résultat assez rapide sur mes tests.

Answer 6

Answer 7

Answer 8