Как я могу улучшить производительность на своем алгоритме сито эратосфена? - PullRequest
Новая
       15

Как я могу улучшить производительность на своем алгоритме сито эратосфена?

4 голосов
/ 17 июня 2011

Я изучаю clojure, пройдя через проект euler, и работаю над задачей № 10 (найдите сумму всех простых чисел ниже двух миллионов. Я реализовал довольно буквальный алгоритм для сита из эратосфена, но он работает слишком медленно до двух миллионов. Я попытался реализовать его с помощью loop-recur, чтобы не создавать новые кадры, но это не оказало большого влияния на производительность. 

(defn find-primes-sum [last-prime nums]
    (loop [p last-prime n nums sum 0]
        (println p)
        (if (empty? n)
        sum
            (recur (first n) (doall (remove #(zero? (mod % (first n))) n)) (+ sum (first n))))))

(defn sieve-primes-until [limit]
    (find-primes-sum 2 (filter odd? (range 2 (inc limit)))))

(println (sieve-primes-until 2000000))

Ответы [ 2 ]

2 голосов
/ 18 июня 2011 
(set! *unchecked-math* true)

(defmacro iloop [[b t n] & body]
  `(loop [~@b]
     (when ~t
       ~@body
       (recur ~n))))

(defn count-primes [^long n]
  (let [c (inc n)
        ^booleans prime? (make-array Boolean/TYPE c)]
    (iloop [(i 2) (<= i n) (inc i)]
      (aset prime? i true))
    (iloop [(i 2) (<= (* i i) n) (inc i)]
      (if (aget prime? i)
        (iloop [(j i) (<= (* i j) n) (inc j)]
          (aset prime? (* i j) false))))
    (areduce prime? i r 0
      (if (aget prime? i)
        (inc r)
        r))))

Эта версия предназначена для альфа-версии Clojure 1.3.0. На моей машине он считает простые числа до 1e8 за 2 секунды. Это может быть легко изменено, чтобы собрать их. Первоначально он был написан, чтобы показать, что вы можете реализовать сито так, чтобы оно работало так же быстро, как и сопоставимая Java.

http://dosync.posterous.com/lispers-know-the-value-of-everything-and-the

1 голос
/ 17 июня 2011

Лично я бы по-другому структурировал код. У меня есть реализация этой проблемы, которая сначала генерирует ленивый последовательность всех простых чисел, а затем суммирует первые 2 000 000 элементов. Занимает 16 секунд на clojure 1.2, но он вряд ли оптимизирован, за исключением использования recur.

Вы также делаете много ненужных сравнений с вашим входным диапазоном; (remove #(zero? (mod % (first n))) n) проверяет всех кандидатов на наличие всех нечетных чисел, что является бессмысленным **, особенно если вы вводите его с помощью doall. На самом деле вам нужно только протестировать простое число кандидата x со всеми известными простыми числами <= sqrt (x) и отбросить кандидата, когда вы найдете свое первое совпадение. </p>

** Я только что заметил, что ваш алгоритм не настолько глуп, но я все же рекомендую переписать ваш алгоритм, поскольку ленивый seq находит «следующее простое число», учитывая последовательность предыдущих простых чисел и число кандидатов.

...