Генерация быстрого первичного номера в Clojure
Я работал над решением проблем 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?
Ответы
Ответ 1
Здесь другой подход, который отмечает Clojure Java interop. Это занимает 374 мс на 2,4 ГГц Core 2 Duo (работает однопоточно). Я разрешаю эффективную реализацию Miller-Rabin в Java BigInteger#isProbablePrime с проверкой соответствия.
(def certainty 5)
(defn prime? [n]
(.isProbablePrime (BigInteger/valueOf n) certainty))
(concat [2] (take 10001
(filter prime?
(take-nth 2
(range 1 Integer/MAX_VALUE)))))
Вероятность Miller-Rabin 5, вероятно, не очень хороша для чисел, намного больших, чем это. Эта определенность равна 96.875% определенному ее простому (1 - .5^certainty)
Ответ 2
Я понимаю, что это очень старый вопрос, но я недавно закончил тем, что искал то же самое, и ссылки здесь были не тем, что я искал (максимально ограничен функциональными типами, лениво генерируя ~ каждое ~ простое число, которое я хочу),
Я наткнулся на хорошую реализацию F #, так что все кредиты его. Я просто перенес это на Clojure:
(defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
[]
(letfn [(reinsert [table x prime]
(update-in table [(+ prime x)] conj prime))
(primes-step [table d]
(if-let [factors (get table d)]
(recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
(inc d))
(lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
(inc d))))))]
(primes-step {} 2)))
Использование просто
(take 5 (gen-primes))
Ответ 3
Очень поздно вечеринке, но я приведу пример, используя Java BitSets:
(defn sieve [n]
"Returns a BitSet with bits set for each prime up to n"
(let [bs (new java.util.BitSet n)]
(.flip bs 2 n)
(doseq [i (range 4 n 2)] (.clear bs i))
(doseq [p (range 3 (Math/sqrt n))]
(if (.get bs p)
(doseq [q (range (* p p) n (* 2 p))] (.clear bs q))))
bs))
Запустив это на MacBook Pro 2014 (ядро Core i7), я получаю:
user=> (time (do (sieve 1e6) nil))
"Elapsed time: 64.936 msecs"
Ответ 4
См. последний пример здесь:
http://clojuredocs.org/clojure_core/clojure.core/lazy-seq
;; An example combining lazy sequences with higher order functions
;; Generate prime numbers using Eratosthenes Sieve
;; See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;; Note that the starting set of sieved numbers should be
;; the set of integers starting with 2 i.e., (iterate inc 2)
(defn sieve [s]
(cons (first s)
(lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
(rest s))))))
user=> (take 20 (sieve (iterate inc 2)))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
Ответ 5
Здесь хорошая и простая реализация:
http://clj-me.blogspot.com/2008/06/primes.html
... но он написан для некоторой версии версии Clojure до версии 1.0. См. lazy_seqs в Clojure Contrib для того, который работает с текущей версией языка.
Ответ 6
(defn sieve
[[p & rst]]
;; make sure the stack size is sufficiently large!
(lazy-seq (cons p (sieve (remove #(= 0 (mod % p)) rst)))))
(def primes (sieve (iterate inc 2)))
с размером стека 10 М, я получаю 1001-е число в ~ 33 секунды в Macbook 2.1Gz.
Ответ 7
Итак, я только начал с Clojure, и да, это очень много на Project Euler, не так ли? Я написал довольно простой алгоритм простого деления пробного деления, но он не слишком сильно затухает до того, как каждый пробег разделов становится слишком медленным.
Итак, я начал снова, на этот раз используя ситовый метод:
(defn clense
"Walks through the sieve and nils out multiples of step"
[primes step i]
(if (<= i (count primes))
(recur
(assoc! primes i nil)
step
(+ i step))
primes))
(defn sieve-step
"Only works if i is >= 3"
[primes i]
(if (< i (count primes))
(recur
(if (nil? (primes i)) primes (clense primes (* 2 i) (* i i)))
(+ 2 i))
primes))
(defn prime-sieve
"Returns a lazy list of all primes smaller than x"
[x]
(drop 2
(filter (complement nil?)
(persistent! (sieve-step
(clense (transient (vec (range x))) 2 4) 3)))))
Использование и скорость:
user=> (time (do (prime-sieve 1E6) nil))
"Elapsed time: 930.881 msecs
Я очень доволен скоростью: он заканчивается REPL, работающим на MBP 2009 года. Это в основном быстро, потому что я полностью избегаю идиоматического Clojure и вместо этого обхожусь вокруг, как обезьяна. Это также на 4 раза быстрее, потому что я использую переходный вектор для работы на сите вместо того, чтобы оставаться полностью неизменным.
Изменить: После нескольких исправлений/исправлений ошибок от Will Ness он теперь работает намного быстрее.
Ответ 8
Здесь простое сито в схеме:
http://telegraphics.com.au/svn/puzzles/trunk/programming-in-scheme/primes-up-to.scm
Здесь пробег для простых чисел до 10000:
#;1> (include "primes-up-to.scm")
; including primes-up-to.scm ...
#;2> ,t (primes-up-to 10000)
0.238s CPU time, 0.062s GC time (major), 180013 mutations, 130/4758 GCs (major/minor)
(2 3 5 7 11 13...
Ответ 9
Основываясь на комментарии Уилла, вот мой запрос postponed-primes:
(defn postponed-primes-recursive
([]
(concat (list 2 3 5 7)
(lazy-seq (postponed-primes-recursive
{}
3
9
(rest (rest (postponed-primes-recursive)))
9))))
([D p q ps c]
(letfn [(add-composites
[D x s]
(loop [a x]
(if (contains? D a)
(recur (+ a s))
(persistent! (assoc! (transient D) a s)))))]
(loop [D D
p p
q q
ps ps
c c]
(if (not (contains? D c))
(if (< c q)
(cons c (lazy-seq (postponed-primes-recursive D p q ps (+ 2 c))))
(recur (add-composites D
(+ c (* 2 p))
(* 2 p))
(first ps)
(* (first ps) (first ps))
(rest ps)
(+ c 2)))
(let [s (get D c)]
(recur (add-composites
(persistent! (dissoc! (transient D) c))
(+ c s)
s)
p
q
ps
(+ c 2))))))))
Исходное представление для сравнения:
Вот моя попытка портировать этот генератор простых чисел с Python на Clojure. Ниже приведена бесконечная ленивая последовательность.
(defn primes
[]
(letfn [(prime-help
[foo bar]
(loop [D foo
q bar]
(if (nil? (get D q))
(cons q (lazy-seq
(prime-help
(persistent! (assoc! (transient D) (* q q) (list q)))
(inc q))))
(let [factors-of-q (get D q)
key-val (interleave
(map #(+ % q) factors-of-q)
(map #(cons % (get D (+ % q) (list)))
factors-of-q))]
(recur (persistent!
(dissoc!
(apply assoc! (transient D) key-val)
q))
(inc q))))))]
(prime-help {} 2)))
Использование:
user=> (first (primes))
2
user=> (second (primes))
3
user=> (nth (primes) 100)
547
user=> (take 5 (primes))
(2 3 5 7 11)
user=> (time (nth (primes) 10000))
"Elapsed time: 409.052221 msecs"
104743
изменить:
Сравнение производительности, где postponed-primes использует очередь простых чисел, замеченных до сих пор, а не рекурсивный вызов postponed-primes:
user=> (def counts (list 200000 400000 600000 800000))
#'user/counts
user=> (map #(time (nth (postponed-primes) %)) counts)
("Elapsed time: 1822.882 msecs"
"Elapsed time: 3985.299 msecs"
"Elapsed time: 6916.98 msecs"
"Elapsed time: 8710.791 msecs"
2750161 5800139 8960467 12195263)
user=> (map #(time (nth (postponed-primes-recursive) %)) counts)
("Elapsed time: 1776.843 msecs"
"Elapsed time: 3874.125 msecs"
"Elapsed time: 6092.79 msecs"
"Elapsed time: 8453.017 msecs"
2750161 5800139 8960467 12195263)
Ответ 10
От: http://steloflute.tistory.com/entry/Clojure-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8-%EC%B5%9C%EC%A0%81%ED%99%94
Использование массива Java
(defmacro loopwhile [init-symbol init whilep step & body]
`(loop [~init-symbol ~init]
(when ~whilep [email protected] (recur (+ ~init-symbol ~step)))))
(defn primesUnderb [limit]
(let [p (boolean-array limit true)]
(loopwhile i 2 (< i (Math/sqrt limit)) 1
(when (aget p i)
(loopwhile j (* i 2) (< j limit) i (aset p j false))))
(filter #(aget p %) (range 2 limit))))
Использование и скорость:
user=> (time (def p (primesUnderb 1e6)))
"Elapsed time: 104.065891 msecs"
Ответ 11
Я только начал использовать Clojure, поэтому не знаю, хорошо ли это, но вот мое решение:
(defn divides? [x i]
(zero? (mod x i)))
(defn factors [x]
(flatten (map #(list % (/ x %)) (filter #(divides? x %) (range 1 (inc (Math/floor (Math/sqrt x))))))))
(defn prime? [x]
(empty? (filter #(and divides? (not= x %) (not= 1 %)) (factors x))))
(def primes
(filter prime? (range 2 java.lang.Integer/MAX_VALUE)))
(defn sum-of-primes-below [n]
(reduce + (take-while #(< % n) primes)))
Ответ 12
После перехода к этой теме и поиска более быстрой альтернативы уже существующим, я удивлен, что никто не связан с следующей статьей Christophe Grand
(defn primes3 [max]
(let [enqueue (fn [sieve n factor]
(let [m (+ n (+ factor factor))]
(if (sieve m)
(recur sieve m factor)
(assoc sieve m factor))))
next-sieve (fn [sieve candidate]
(if-let [factor (sieve candidate)]
(-> sieve
(dissoc candidate)
(enqueue candidate factor))
(enqueue sieve candidate candidate)))]
(cons 2 (vals (reduce next-sieve {} (range 3 max 2))))))
Как и ленивая версия:
(defn lazy-primes3 []
(letfn [(enqueue [sieve n step]
(let [m (+ n step)]
(if (sieve m)
(recur sieve m step)
(assoc sieve m step))))
(next-sieve [sieve candidate]
(if-let [step (sieve candidate)]
(-> sieve
(dissoc candidate)
(enqueue candidate step))
(enqueue sieve candidate (+ candidate candidate))))
(next-primes [sieve candidate]
(if (sieve candidate)
(recur (next-sieve sieve candidate) (+ candidate 2))
(cons candidate
(lazy-seq (next-primes (next-sieve sieve candidate)
(+ candidate 2))))))]
(cons 2 (lazy-seq (next-primes {} 3)))))
Ответ 13
Идиоматичный и не так уж плох
(def primes
(cons 1 (lazy-seq
(filter (fn [i]
(not-any? (fn [p] (zero? (rem i p)))
(take-while #(<= % (Math/sqrt i))
(rest primes))))
(drop 2 (range))))))
=> #'user/primes
(first (time (drop 10000 primes)))
"Elapsed time: 0.023135 msecs"
=> 104729
Ответ 14
Уже много ответов, но у меня есть альтернативное решение, которое генерирует бесконечную последовательность простых чисел. Я также был заинтересован в выборе нескольких решений.
Сначала немного взаимодействия с Java. для справки:
(defn prime-fn-1 [accuracy]
(cons 2
(for [i (range)
:let [prime-candidate (-> i (* 2) (+ 3))]
:when (.isProbablePrime (BigInteger/valueOf prime-candidate) accuracy)]
prime-candidate)))
Бенджамин @fooobar.com/questions/103903/... is primes-fn-2
nha @fooobar.com/questions/103903/... is primes-fn-3
Мои реализации - primes-fn-4:
(defn primes-fn-4 []
(let [primes-with-duplicates
(->> (for [i (range)] (-> i (* 2) (+ 5))) ; 5, 7, 9, 11, ...
(reductions
(fn [known-primes candidate]
(if (->> known-primes
(take-while #(<= (* % %) candidate))
(not-any? #(-> candidate (mod %) zero?)))
(conj known-primes candidate)
known-primes))
[3]) ; Our initial list of known odd primes
(cons [2]) ; Put in the non-odd one
(map (comp first rseq)))] ; O(1) lookup of the last element of the vec "known-primes"
; Ugh, ugly de-duplication :(
(->> (map #(when (not= % %2) %) primes-with-duplicates (rest primes-with-duplicates))
(remove nil?))))
Указанные числа (время в миллисекундах для подсчета первых N простых чисел) являются самыми быстрыми из серии 5, JVM не перезапускается между экспериментами, поэтому ваш пробег может варьироваться:
1e6 3e6
(primes-fn-1 5) 808 2664
(primes-fn-1 10) 952 3198
(primes-fn-1 20) 1440 4742
(primes-fn-1 30) 1881 6030
(primes-fn-2) 1868 5922
(primes-fn-3) 489 1755 <-- WOW!
(primes-fn-4) 2024 8185
Ответ 15
Если вам не нужно ленивое решение, и вы просто хотите, чтобы последовательность простых чисел была ниже определенного предела, прямая реализация Sieve of Eratosthenes довольно быстрая. Вот моя версия с использованием переходных процессов:
(defn classic-sieve
"Returns sequence of primes less than N"
[n]
(loop [nums (transient (vec (range n))) i 2]
(cond
(> (* i i) n) (remove nil? (nnext (persistent! nums)))
(nums i) (recur (loop [nums nums j (* i i)]
(if (< j n)
(recur (assoc! nums j nil) (+ j i))
nums))
(inc i))
:else (recur nums (inc i)))))
