¿Por qué es más lenta la implementación de este tamiz principal?

Question

Estaba experimentando un poco con (para mí) un nuevo lenguaje de programación: clojure. Y escribí una implementación bastante ingenua de 'tamiz', que luego intenté optimizar un poco.

Curiosamente, aunque (al menos para mí), la nueva aplicación no era más rápido, pero mucho más lenta ...

¿Alguien puede dar una idea de por qué esto es así mucho más lento?

También estoy interesado en otras extremidades en cómo mejorar este algoritmo ...

Saludos,

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

Tengo buenas y malas noticias. La buena noticia es que tus intuiciones son correctas.

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

La mala noticia es que ambos son mucho más lento de lo que piensa

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

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

Lo que pasa es que debido a que el filtro es perezoso, el filtrado no es conseguir que se hagan hasta que las respuestas deben ser impresos. Toda la primera expresión que se cuenta es el tiempo para envolver la secuencia en una carga de filtros. Poner el recuento significa que la secuencia en realidad tiene que ser calculada dentro de la expresión de tiempo, y luego verá cuánto tiempo realmente toma.

Creo que en el caso sin el conteo, sieve2 está tardando más porque está haciendo un poco del trabajo mientras construye la secuencia filtrada.

Cuando ingresa el conteo, sieve2 es más rápido porque es el mejor algoritmo.

P.S. Cuando intento (time (tamve 10000000)), mi máquina se bloquea con un desbordamiento de la pila, presumiblemente debido a la gran cantidad de llamadas de filtro anidado que está acumulando. ¿Cómo es que funcionó para ti?

Answer 2

Algunos consejos de optimización para este tipo de número Primative matemáticas pesadas:

1. uso clojure 1.3
   clonjure 1.3 permite la aritmética no marcada, por lo que no podrás convertir todo en Integer.
2. tipo pista la función argumentos De lo contrario, terminará emitiendo todos los Ints/Longs a Entero para cada llamada de función. (no está llamando a ninguna función indirecta, así que lo estoy enumerando aquí como consejo general)
3. no llame a ninguna función de orden superior. Actualmente (1.3) las funciones lambda # (...) no se pueden compilar como^static, por lo que solo toman Object como argumentos. entonces las llamadas al filter requerirán el boxeo de todos los números.

Es probable que pierda suficiente tiempo en el boxeo/desempaquetado de enteros/entrantes que dificultará juzgar realmente las diferentes optimizaciones. Si escribe la sugerencia (y usa clojure 1.3), entonces probablemente obtendrá mejores números para juzgar sus optimizaciones.