Как я могу улучшить производительность моего алгоритма Clojure Sieve of Eratosthenes?

Я изучаю Clojure, просматривая проект Эйлера, и работаю над проблемой номер 10 (найти сумму всех простых чисел меньше двух миллионов. Я реализовал довольно буквальный алгоритм для сита эратосфенов, но он работает слишком медленно, чтобы быть полезным до 2 млн. Я попытался реализовать его с помощью 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))

clojure lisp sieve-of-eratosthenes
person Scott    schedule 17.06.2011    source источник
comment
В Связанной части этой страницы есть несколько вопросов, которые могут вас заинтересовать.   -  person Goran Jovic    schedule 17.06.2011

Ответы (2)


arrow_upward
2
arrow_downward 

(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 alpha. На моей машине он считает простые числа до 1e8 за 2 секунды. Его можно легко переделать, чтобы собрать их. Первоначально он был написан, чтобы показать, что вы можете реализовать сито так, чтобы оно работало так же быстро, как сопоставимая Java.

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

person dnolen    schedule 18.06.2011

arrow_upward
1
arrow_downward

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

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

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

person Joost Diepenmaat    schedule 17.06.2011
comment
Абстракция хороша для глаз и хороша для оптимизации. Писать более мелкие и лучшие функции более интуитивно, чем оптимизировать сложную. Итак, как сказал @ Joost-Diepenmaat, по крайней мере, разделите простое поколение и суммирование. Однако не стоит слишком зацикливаться на этой конкретной проблеме. Некоторые люди пишут ситовые алгоритмы для своей докторской степени! - person Paul Lam; 17.06.2011
comment
Я не уверен, понимаете ли вы, что пытается сделать код (следовало бы прокомментировать!). Когда он повторяется, диапазон чисел заменяется диапазоном чисел, из которого удалены все кратные последнего простого числа, потому что они, очевидно, не могут быть простыми числами или полезны в качестве множителя. doall предназначен для принудительной оценки remove #(zero? (mod % (first n))) n), чтобы предотвратить переполнение стека из-за лени. - person Scott; 17.06.2011
comment
Еще одно замечание: если бы я переписал его, чтобы найти следующее простое число с учетом всех предыдущих чисел, мне нужно было бы проверить каждое число в диапазоне, или есть способ ограничить числа, которые мне нужно проверить (помимо, очевидно, использования диапазона только с четные числа) - person Scott; 17.06.2011
comment
Думаю, я это понимаю, но, насколько я понимаю, выполнение алгоритма таким образом подразумевает выполнение гораздо большего количества тестов на делимость, потому что вы начинаете с огромного списка кандидатов, которые вы медленно отсеиваете. Если вы определяете простое число X как неделимое на все простые числа ‹= sqrt X, вы должны получить более быстрый алгоритм. По крайней мере, моя реализация намного быстрее, чем ваша, и не делает ничего особенно умного. - person Joost Diepenmaat; 17.06.2011
comment
Re: ваш второй вопрос: вам нужно проверить только предыдущие простые числа. - person Joost Diepenmaat; 17.06.2011
comment
Упс, я имел в виду все предыдущие простые числа. Должен ли я тестировать каждое число постепенно, начиная с последнего простого числа, которое я нашел (например, имея предыдущие простые числа {2, 3, 5, 7}, мне нужно проверять 8, 9, 10 и 11, пока я не получу следующее простое число) или есть ли способ ограничить количество чисел, которые мне нужно проверить на простоту? - person Scott; 17.06.2011
comment
Что ж, вы всегда можете перейти от последнего простого числа + 2, поскольку четные числа, кроме 2, не являются простыми. Там вы можете сделать несколько оптимизаций, чтобы исключить еще несколько очевидных непростых чисел, но главное преимущество состоит в том, что для проверки того, является ли следующее число простым, вам нужно только проверить, делится ли оно на любое из предыдущих простых чисел (и вы можете прекратить тестирование, если это так, поэтому работайте от 2 и выше до sqrt X - цель всегда состоит в том, чтобы быстро отбросить непростые числа). - person Joost Diepenmaat; 17.06.2011