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

Question

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

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

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

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

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

Арно Гаудер

; 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

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

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

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

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

Answer 2

Некоторые советы по оптимизации для этого вида Primary Number Heavy Math:

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

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