Pourquoi est-ce premier tamis mise en œuvre plus lente?

Question

Je voulais juste un peu avec expérimentait (pour moi) un nouveau langage de programmation: clojure. Et je l'ai écrit une mise en œuvre « tamis » assez naïf, que je puis essayé d'optimiser un peu.

Bizarrement bien (pour moi au moins), la nouvelle mise en œuvre n'a pas été plus rapide, mais beaucoup plus lent ...

Quelqu'un peut-il donner un aperçu de pourquoi cela est tellement plus lent?

Je suis aussi intéressé par d'autres conseils sur la façon d'améliorer cet algorithme ...

Cordialement,

Arnaud Gouder

; naive sieve. 
(defn sieve
  ([max] (sieve max (range 2 max) 2))
  ([max candidates n]
    (if (> (* n n) max)
      candidates
      (recur max (filter #(or (= % n) (not (= (mod % n) 0))) candidates) (inc n)))))

; Instead of just passing the 'candidates' list, from which I sieve-out the non-primes,
; I also pass a 'primes' list, with the already found primes
; I hoped that this would increase the speed, because:
; - Instead of sieving-out multiples of 'all' numbers, I now only sieve-out the multiples of primes.
; - The filter predicate now becomes simpler.
; However, this code seems to be approx 20x as slow.
; Note: the primes in 'primes' end up reversed, but I don't care (much). Adding a 'reverse' call makes it even slower :-(
(defn sieve2 
  ([max] (sieve2 max () (range 2 max)))
  ([max primes candidates]
    (let [n (first candidates)]
      (if (> (* n n) max)
        (concat primes candidates)
        (recur max (conj primes n) (filter #(not (= (mod % n) 0)) (rest candidates)))))))

; Another attempt to speed things up. Instead of sieving-out multiples of all numbers in the range,
; I want to sieve-out only multiples of primes.. I don't like the '(first (filter ' construct very much...
; It doesn't seem to be faster than 'sieve'.
(defn sieve3
  ([max] (sieve max (range 2 max) 2))
  ([max candidates n]
    (if (> (* n n) max)
      candidates
      (let [new_candidates (filter #(or (= % n) (not (= (mod % n) 0))) candidates)]
        (recur max new_candidates (first (filter #(> % n) new_candidates)))))))

(time (sieve 10000000))
(time (sieve 10000000))
(time (sieve2 10000000))
(time (sieve2 10000000))
(time (sieve2 10000000))
(time (sieve 10000000)) ; Strange, speeds are very different now... Must be some memory allocation thing caused by running sieve2
(time (sieve 10000000))
(time (sieve3 10000000))
(time (sieve3 10000000))
(time (sieve 10000000))

Answer 1

J'ai de bonnes nouvelles et de mauvaises nouvelles. Les bonnes nouvelles sont que vos intuitions sont correctes.

(time (sieve 10000)) ; "Elapsed time: 0.265311 msecs"

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)

(time (sieve2 10000)) ; "Elapsed time: 1.028353 msecs"

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)

Les mauvaises nouvelles sont que les deux sont beaucoup plus lent que vous pensez

(time (count (sieve 10000))) ; "Elapsed time: 231.183055 msecs"
1229

(time (count (sieve2 10000))) ; "Elapsed time: 87.822796 msecs"
1229

Qu'est-ce qui se passe est que, parce que le filtre est paresseux, le filtrage ne se fait pas jusqu'à ce que les réponses doivent être imprimées. Toute la première expression est le comptage est le temps d'envelopper la séquence dans une charge de filtres. Mettre le comptage dans les moyens que la séquence doit effectivement être calculée dans l'expression temporelle, et vous voyez combien de temps il faut vraiment.

Je pense que dans le cas sans le comte, sieve2 prend plus de temps parce qu'il est en train de faire un peu de travail tout en construisant la séquence filtrée.

Lorsque vous mettez le nombre dans, sieve2 est plus rapide car il est le meilleur algorithme.

P.S. Lorsque je tente (temps (tamis 10000000)), ma machine se bloque avec un débordement de pile, probablement en raison de la grande pile de filtre imbrications il est mise en place. Comment se fait-il couru pour vous?

Answer 2

Quelques conseils d'optimisation pour ce genre de nombre Primative lourd mathématiques:

1. Utilisation clojure 1.3
   clonjure 1.3 permet un caissonné vérifié arithmétique de sorte que vous ne serez pas jettes tout entier à.
2. Type Masquer les arguments de la fonction Sinon, vous finirez par jeter tous les Ints / désire ardemment entier pour chaque appel de fonction. (Vous n'êtes pas appeler toutes les fonctions en mesure Hint donc je suis juste la liste ici comme des conseils généraux)
3. ne pas appeler des fonctions d'ordre supérieur. À l'heure actuelle (1.3) fonctions lambda # (...) ne peut pas être compilé ^ statique afin qu'ils ne prennent que l'objet comme arguments. de sorte que les appels à filter nécessiteront la boxe de tous les numéros.

Vous perdre probablement assez de temps dans la boxe / unboxing / Entiers ints qu'il sera difficile de juger vraiment les différentes optimisations. Si vous tapez indice (et l'utilisation clojure 1.3), alors vous aurez probablement obtenir de meilleurs chiffres pour juger vos optimisations.