Почему эта простая ситовая реализация медленнее?

Question

Я просто немного экспериментировал с (для меня) новым языком программирования: clojure. И я написал довольно наивную «ситовую» реализацию, которую я затем попытался немного оптимизировать.

Как ни странно, хотя (для меня по крайней мере), новая реализация не быстрее было, но гораздо медленнее ...

Кто-нибудь может пролить некоторый свет в том, почему это так гораздо медленнее?

Я также заинтересован в других советах в том, как улучшить этот алгоритм ...

С наилучшими пожеланиями,

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

У меня есть хорошие новости и плохие новости. Хорошей новостью является то, что ваши интуиции верны.

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

Плохая новость заключается в том, что оба они гораздо медленнее, чем вы думаете

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

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

То, что происходит в том, что, поскольку фильтр ленив, фильтрация не получает сделано, пока ответы не должны быть напечатаны. Все первое выражение - это время, чтобы обернуть последовательность в нагрузке фильтров. Помещение счетчика означает, что последовательность фактически должна быть рассчитана в выражении синхронизации, а затем вы видите, сколько времени это действительно занимает.

Я думаю, что в случае без счета сите2 занимает больше времени, потому что он выполняет небольшую работу при построении отфильтрованной последовательности.

Когда вы вкладываете счет, сито2 быстрее, потому что это лучший алгоритм.

P.S. Когда я пытаюсь (время (sieve 10000000)), моя машина падает с переполнением стека, по-видимому, из-за огромного стека вызовов вложенных фильтров, которые он наращивает. Почему это побежало для вас?

Answer 2

Некоторых советы по оптимизации такого рода примитивного числа тяжелая математика:

1. использование clojure 1.3
   clonjure 1.3 позволяет выполнить арифметику без коробки, поэтому вы не будете бросать все в Integer.
2. тип подсказка аргументы функции В противном случае вы получите литье всех значений Ints/Longs Integer для каждого вызова функции. (вы не вызываете никаких намеченных функций, поэтому я просто перечисляю его здесь как общий совет)
3. не называть функции более высокого порядка. В настоящее время (1.3) лямбда-функции # (...) не могут быть скомпилированы как^static, поэтому они принимают только объект как аргументы. поэтому для звонков filter потребуется бокс для всех номеров.

Возможно, вы потеряете достаточно времени в боксе/распаковке целых чисел/ints, что затруднит реальную оценку различных оптимизаций. Если вы набираете подсказку (и используете clojure 1.3), вы, скорее всего, получите более качественные цифры, чтобы судить о ваших оптимизации.