Я работал над решением проблем Project Euler в Clojure, чтобы стать лучше, и я уже несколько раз сталкивался с генерацией простых чисел. Моя проблема в том, что это занимает слишком много времени. Я надеялся, что кто-нибудь сможет помочь мне найти эффективный способ сделать это Clojure-y.
Когда я сделал это кулаком, я грубо заставил это. Это было легко сделать. Но вычисление 10001 простых чисел заняло 2 минуты на Xeon 2,33 ГГц, слишком долго для правил и вообще слишком долго. Здесь был алгоритм:
(defn next-prime-slow
"Find the next prime number, checking against our already existing list"
([sofar guess]
(if (not-any? #(zero? (mod guess %)) sofar)
guess ; Then we have a prime
(recur sofar (+ guess 2))))) ; Try again
(defn find-primes-slow
"Finds prime numbers, slowly"
([]
(find-primes-slow 10001 [2 3])) ; How many we need, initial prime seeds
([needed sofar]
(if (<= needed (count sofar))
sofar ; Found enough, we're done
(recur needed (concat sofar [(next-prime-slow sofar (last sofar))])))))
Заменив next-prime-slow на более новую процедуру, которая учитывала некоторые дополнительные правила (например, свойство 6n + / - 1), я смог ускорить процесс примерно до 70 секунд.
Затем я попытался сделать сито из Эратосфена в чистом Clojure. Я не думаю, что я вытащил все ошибки, но я сдался, потому что это было просто слишком медленно (даже хуже, чем выше, я думаю).
(defn clean-sieve
"Clean the sieve of what we know isn't prime based"
[seeds-left sieve]
(if (zero? (count seeds-left))
sieve ; Nothing left to filter the list against
(recur
(rest seeds-left) ; The numbers we haven't checked against
(filter #(> (mod % (first seeds-left)) 0) sieve)))) ; Filter out multiples
(defn self-clean-sieve ; This seems to be REALLY slow
"Remove the stuff in the sieve that isn't prime based on it self"
([sieve]
(self-clean-sieve (rest sieve) (take 1 sieve)))
([sieve clean]
(if (zero? (count sieve))
clean
(let [cleaned (filter #(> (mod % (last clean)) 0) sieve)]
(recur (rest cleaned) (into clean [(first cleaned)]))))))
(defn find-primes
"Finds prime numbers, hopefully faster"
([]
(find-primes 10001 [2]))
([needed seeds]
(if (>= (count seeds) needed)
seeds ; We have enough
(recur ; Recalculate
needed
(into
seeds ; Stuff we've already found
(let [start (last seeds)
end-range (+ start 150000)] ; NOTE HERE
(reverse
(self-clean-sieve
(clean-sieve seeds (range (inc start) end-range))))))))))
Это плохо. Это также вызывает переполнение стека, если число 150000 меньше. Это несмотря на то, что я использую recur. Это может быть моя вина.
Затем я попробовал сито, используя методы Java на Java ArrayList. Это заняло совсем немного времени и памяти.
Моя последняя попытка - использовать сито с использованием хеш-карты Clojure, вставляя все числа в сито, а затем разделяя числа, которые не являются простыми. В конце он берет список ключей, которые являются простыми числами, которые он нашел. Требуется приблизительно 10-12 секунд, чтобы найти 10000 простых чисел. Я не уверен, что он полностью отлажен. Это тоже рекурсивно (с использованием recur и loop), так как я пытаюсь быть Lispy.
Таким образом, с такими проблемами проблема 10 (суммируя все простые числа до 2000000) убивает меня. Мой самый быстрый код нашел правильный ответ, но это заняло 105 секунд, и мне потребовалось немало памяти (я выделил ему 512 МБ, чтобы мне не пришлось с этим возиться). Мои другие алгоритмы занимают так много времени, что я всегда заканчивал тем, что останавливал их первым.
Я мог бы использовать сито для вычисления такого количества простых чисел в Java или C довольно быстро и без использования большого количества памяти. Я знаю, что мне не хватает чего-то в моем стиле Clojure/Lisp, что вызывает проблему.
Есть ли что-то, что я делаю действительно неправильно? Clojure просто медленно работает с большими последовательностями? Читая некоторые из обсуждений проекта Эйлера, люди вычислили первые 10000 простых чисел в других Lispх менее чем за 100 миллисекунд. Я понимаю, что JVM может замедлить ход событий, и Clojure сравнительно молод, но я не ожидал бы разницы в 100 раз.
Может ли кто-нибудь объяснить мне быстрый способ вычисления простых чисел в Clojure?
