Génération rapide de nombres premiers à Clojure

Question

J'ai travaillé sur la résolution de Projet Euler problèmes en Clojure pour aller mieux, et j'ai déjà couru dans le premier numéro de la génération d'un couple de fois. Mon problème est qu'il est juste de prendre trop longtemps. J'espérais que quelqu'un pourrait m'aider à trouver une manière efficace de faire cela dans un Clojure-y moyen.

Quand j'ai fait ceci, j'ai brute forcé. C'était facile à faire. Mais le calcul de 10001 nombres premiers a pris 2 minutes de cette façon sur un Xeon 2.33 GHz, trop long pour les règles, et trop long en général. Ici était l'algorithme:

(defn next-prime-slow
    "Find the next prime number, checking against our already existing list"
    ([sofar guess]
        (if (not-any? #(zero? (mod guess %)) sofar)
            guess                         ; Then we have a prime
            (recur sofar (+ guess 2)))))  ; Try again   							

(defn find-primes-slow
    "Finds prime numbers, slowly"
    ([]
        (find-primes-slow 10001 [2 3]))   ; How many we need, initial prime seeds
    ([needed sofar]
        (if (<= needed (count sofar))
            sofar                         ; Found enough, we're done
            (recur needed (concat sofar [(next-prime-slow sofar (last sofar))])))))

Par le remplacement de la prochaine prime-lent avec une nouvelle routine qui a pris quelques règles additionnelles en compte (comme la 6n +/- 1 bien) j'ai été en mesure d'accélérer les choses pour environ 70 secondes.

Ensuite, j'ai essayé de faire un crible d'Eratosthène dans le plus pur Clojure. Je ne pense pas que j'ai obtenu tous les bugs, mais j'ai abandonné parce que c'était tout simplement trop lent (encore pire que les précédents, je pense).

(defn clean-sieve
    "Clean the sieve of what we know isn't prime based"
    [seeds-left sieve]
    (if (zero? (count seeds-left))
        sieve              ; Nothing left to filter the list against
        (recur
            (rest seeds-left)    ; The numbers we haven't checked against
            (filter #(> (mod % (first seeds-left)) 0) sieve)))) ; Filter out multiples

(defn self-clean-sieve  ; This seems to be REALLY slow
    "Remove the stuff in the sieve that isn't prime based on it's self"
    ([sieve]
        (self-clean-sieve (rest sieve) (take 1 sieve)))
    ([sieve clean]
        (if (zero? (count sieve))
            clean
            (let [cleaned (filter #(> (mod % (last clean)) 0) sieve)]
                (recur (rest cleaned) (into clean [(first cleaned)]))))))

(defn find-primes
    "Finds prime numbers, hopefully faster"
    ([]
        (find-primes 10001 [2]))
    ([needed seeds]
        (if (>= (count seeds) needed)
            seeds        ; We have enough
            (recur       ; Recalculate
                needed
                (into
                    seeds    ; Stuff we've already found
                    (let [start (last seeds)
                            end-range (+ start 150000)]   ; NOTE HERE
                        (reverse    											
                            (self-clean-sieve
                            (clean-sieve seeds (range (inc start) end-range))))))))))

Ce qui est mauvais. Il provoque aussi des débordements de pile si le nombre 150000 est plus petit. Ceci malgré le fait que j'utilise se reproduire. Qui peut être de ma faute.

Ensuite, j'ai essayé un tamis, à l'aide de méthodes de Java sur Java ArrayList. Cela a pris un peu de temps, et de la mémoire.

Ma dernière tentative est un tamis à l'aide d'un Clojure de hachage de la carte, l'insertion de tous les nombres dans la passoire puis dissoc avec des nombres qui ne sont pas le premier. À la fin, il prend la liste des clés, qui sont les nombres premiers, c'trouvé. Il faut environ 10 à 12 secondes pour trouver 10000 nombres premiers. Je ne suis pas sûr que c'est entièrement de débogage encore. Il est récursif trop (à l'aide de réapparaître et de la boucle), depuis que je suis en train de l'être Lispy.

Donc avec ce genre de problèmes, la résolution 10 (somme de tous les nombres premiers en vertu de 2000000) est en train de me tuer. Mes plus rapide code est venu avec la bonne réponse, mais il a fallu 105 secondes pour le faire, et besoin d'un peu de mémoire (je l'ai donné 512 MO juste pour que je n'aurais pas de chichi avec elle). Mes autres algorithmes de prendre si longtemps, j'ai toujours fini par arrêter d'abord.

Je pourrais utiliser un tamis à calculer que le nombre de nombres premiers en Java ou C assez rapide et sans utiliser autant de mémoire. Je sais que je doit manquer quelque chose dans mon Clojure/Lisp style qui est à l'origine du problème.

Est-il quelque chose que je fais vraiment mal? Est Clojure juste un peu lent avec grandes séquences? La lecture de certains de le projet Euler discussions on a calculé le premier 10000 nombres premiers dans d'autres Lisps en moins de 100 millisecondes. Je me rends compte de la JVM peut ralentir les choses et Clojure est relativement jeune, mais je ne m'attends pas à une 100x différence.

Quelqu'un peut-il m'éclairer sur un moyen rapide de calculer les nombres premiers en Clojure?

Answer 1

Voici une autre approche qui célèbre l'interopérabilité Java de Clojure. Cela prend 374ms sur un processeur 2,4 Ghz Core 2 Duo (fonctionnant avec un seul thread). Je laisse l'implémentation efficace Miller-Rabin dans BigInteger de Java # isProbablePrime se charger du contrôle de primalité.

 (def certainty 5)

(defn prime? [n]
      (.isProbablePrime (BigInteger/valueOf n) certainty))

(take 10001 
   (filter prime? 
      (take-nth 2 
         (range 1 Integer/MAX_VALUE)))) 
 

La certitude de 5 de Miller-Rabin n’est probablement pas très bonne pour des nombres beaucoup plus grands que cela. Cette certitude est égale à 96,875% de certitude qu’elle est primordiale (1 - .5 ^ certitude)

Answer 2

Je me rends compte que c’est une très vieille question, mais j’ai récemment fini par chercher la même chose et les liens ici n’étaient pas ce que je cherchais (restreint autant que possible aux types fonctionnels, générant paresseusement tous les ~ premiers ~ que je veux) .

Je suis tombé sur une bonne implémentation en F # , donc tous les crédits sont les siens. Je l'ai simplement porté à Clojure:

 (defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
  []
  (let [reinsert (fn [table x prime]
                   (update-in table [(+ prime x)] conj prime))]
    (defn primes-step [table d]
                 (if-let [factors (get table d)]
                   (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
                          (inc d))
                   (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                                 (inc d))))))
    (primes-step {} 2)))
 

L'utilisation est simplement

 (->>
  (gen-primes)
  (filter #(< % 2000000)
  ; do what you need with the stuff
)
 

Answer 3

Très tard pour la fête, mais je vais donner un exemple, en utilisant les BitSets Java:

 (defn sieve [n]
  "Returns a BitSet with bits set for each prime up to n"
  (let [bs (new java.util.BitSet n)]
    (.flip bs 2 n)
    (doseq [i (range 4 n 2)] (.clear bs i))
    (doseq [p (range 3 (Math/sqrt n))]
      (if (.get bs p)
        (doseq [q (range (* p p) n (* 2 p))] (.clear bs q))))
    bs))
 

En l'exécutant sur un Macbook Pro 2014 (Core i7 à 2,3 GHz), je reçois:

 user=> (time (do (sieve 1e6) nil))
"Elapsed time: 64.936 msecs"
 

Answer 4

Voir le dernier exemple ici: http://clojuredocs.org/clojure_core/clojure.core/lazy-seq

 ;; An example combining lazy sequences with higher order functions
;; Generate prime numbers using Eratosthenes Sieve
;; See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;; Note that the starting set of sieved numbers should be
;; the set of integers starting with 2 i.e., (iterate inc 2) 
(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s))))))

user=> (take 20 (sieve (iterate inc 2)))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
 

Answer 5

Voici une implémentation simple et agréable:

http://clj-me.blogspot.com/2008/06/primes.html

... mais il est écrit pour certaines versions de Clojure antérieures à la 1.0. Voir lazy_seqs dans Clojure Contrib pour une version compatible avec la version actuelle du langage.