Почему эта реализация основного сита медленнее? - PullRequest
Новая
       22

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

7 голосов
/ 04 января 2011

Я просто немного экспериментировал с (для меня) новым языком программирования: 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))

Ответы [ 2 ]

4 голосов
/ 06 января 2011

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

(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)), моя машина дает сбой с переполнением стека, вероятно, из-за огромного стека вложенных вызовов фильтров, которые она создает.Как получилось, что он побежал за тобой?

2 голосов
/ 05 января 2011

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

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

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

...