#python #performance #clojure #comparison
#python #Производительность #clojure #сравнение
Вопрос:
Недавно я начал изучать Clojure и решил попрактиковаться в задачах Эйлера, чтобы освоиться с доступными структурами данных и попрактиковаться в рекурсии и циклировании.
Я пробовал различные подходы к проблеме 50, но что бы я ни делал, поиск решения для 1000000 так и не был завершен. После того, как я посмотрел, что делали другие, я предположил, что то, что я делаю, тоже не должно занимать вечно, поэтому я ввел эквивалентный алгоритм на Python, чтобы посмотреть, заключается ли проблема в моем непонимании какой-либо вещи Clojure или настроек Java. Python завершен за 10 секунд. Для простых чисел меньше 100000 версия Python была завершена за 0,5 секунды, Clojure — за 5.
Я публикую версию Clojure, которая была создана специально для соответствия коду Python. Можете ли вы помочь мне понять, почему существует такая разница в производительности? Должен ли я использовать непроверенные добавления, подсказки типа, примитивы (но где?) или что?
Итак, вот Clojure:
(defn prime? [n]
(let [r (int (Math/sqrt n))]
(loop [d 2]
(cond
(= n 1) false
(> d r) true
(zero? (rem n d)) false
:other (recur (inc d))))))
(defn primes []
(filter prime? (iterate inc 2)))
(defn cumulative-sum [s]
(reduce
(fn [v, x] (conj v ( (last v) x)))
[(first s)]
(rest s)))
(defn longest-seq-under [n]
"Longest prime seq with sum under n"
(let [ps (vec (take-while #(< % n) (primes))) ; prime numbers up to n
prime-set (set ps) ; set for testing of inclusion
cs (cumulative-sum ps)
cnt (count ps)
max-len (count (take-while #(< % n) cs)) ; cannot have longer sequences
sub-sum (fn [i j] ; sum of primes between the i-th and j-th
(- (cs j) (get cs (dec i) 0)))
seq-with-len (fn [m] ; try m length prime sequences and return the first where the sum is prime
(loop [i 0] ; try with the lowest sum
(if (> i (- cnt m)) ; there are no more elements for and m length sequence
nil ; could not find any
(let [j ( i (dec m)) ; fix length
s (sub-sum i j)]
(if (>= s n) ; overshoot
nil
(if (prime-set s) ; sum is prime
[i (inc j)] ; we just looked for the first
(recur (inc i))))))))] ; shift window
(loop [m max-len] ; try with the longest sequence
(if (not (zero? m))
(let [[i j] (seq-with-len m) ]
(if j
(subvec ps i j)
(recur (dec m))))))))
(assert (= [2 3 5 7 11 13] (longest-seq-under 100)))
(let [s1000 (longest-seq-under 1000)]
(assert (= 21 (count s1000)))
(assert (= 953 (reduce s1000))))
; (time (reduce (longest-seq-under 100000))) ; "Elapsed time: 5707.784369 msecs"
И вот то же самое в Python:
from math import sqrt
from itertools import takewhile
def is_prime(n) :
for i in xrange(2, int(sqrt(n)) 1) :
if n % i == 0 :
return False
return True
def next_prime(n):
while not is_prime(n) :
n = 1
return n
def primes() :
i = 1
while True :
i = next_prime(i 1)
yield i
def cumulative_sum(s):
cs = []
css = 0
for si in s :
css = si
cs.append( css )
return cs
def longest_seq_under(n) :
ps = list(takewhile( lambda p : p < n, primes()))
pss = set(ps)
cs = cumulative_sum(ps)
cnt = len(ps)
max_len = len(list(takewhile(lambda s : s < n, cs)))
def subsum(i, j):
return cs[j] - (cs[i-1] if i > 0 else 0)
def interval_with_length(m) :
for i in xrange(0, cnt-m 1) :
j = i m - 1
sij = subsum(i,j)
if sij >= n :
return None, None
if sij in pss : # prime
return i, j 1
return None, None
for m in xrange(max_len, 0, -1) :
f, t = interval_with_length(m)
if t :
return ps[f:t]
assert longest_seq_under(100) == [2, 3, 5, 7, 11, 13]
assert sum(longest_seq_under(1000)) == 953
# import timeit
# timeit.Timer("sum(longest_seq_under(100000))", "from __main__ import longest_seq_under").timeit(1) # 0.51235757617223499
Спасибо
Комментарии:
1. Какую версию Clojure вы используете? 1.2.x или 1.3?
2. Я выяснил, что было главным виновником: способ вычисления вектора кумулятивной суммы. Я никогда не проверял, что он делает для больших векторов, я предположил, что
last
для вектора используется доступ к массиву, но(source last)
показал, что это рекурсивно. Мой код так и не дошел до основной части с 78000 простыми числами в векторе.3. Работали бы следующие версии:
(defn cumulative-sum-2 [s] (loop [[x amp; xs] s ss 0 acc []] (if x (let [ssx ( ss x)] (recur xs ssx (conj acc ssx))) acc)))
или(defn cumulative-sum-3 [s] (reduce (fn [v, x] (conj v ( (v (dec (count v))) x))) [(first s)] (rest s)))
При использовании одной из них решение все еще примерно в 3 раза медленнее, чем эквивалент Python, но это может быть смягчено переходными процессами или некоторыми методами, которые мне еще предстоит освоить.
Ответ №1:
Я думаю, что замедление происходит из-за того, сколько раз вы повторяете последовательности в longest-seq-under
; каждая из этих итераций берет свое. Вот потрясающе быстрая версия, основанная на комбинации вашего кода и ответа, опубликованного здесь. Обратите внимание, что это primes
лениво, поэтому мы можем связать его с def
vs defn
:
(defn prime? [n]
(let [r (int (Math/sqrt n))]
(loop [d 2]
(cond (= n 1) false
(> d r) true
(zero? (rem n d)) false
:else (recur (inc d))))))
(def primes (filter prime? (iterate inc 2)))
(defn make-seq-accumulator
[[x amp; xs]]
(map first (iterate
(fn [[sum [s amp; more]]]
[( sum s) more])
[x xs])))
(def prime-sums
(conj (make-seq-accumulator primes) 0))
(defn euler-50 [goal]
(loop [c 1]
(let [bots (reverse (take c prime-sums))
tops (take c (reverse (take-while #(> goal (- % (last bots)))
(rest prime-sums))))]
(or (some #(when (prime? %) %)
(map - tops bots))
(recur (inc c))))))
Это завершилось примерно за 6 мс на моей машине:
user> (time (euler-50 1000000))
"Elapsed time: 6.29 msecs"
997651
Комментарии:
1. Да, я тоже видел это решение здесь , но не потратил на него достаточно времени, чтобы полностью понять идею. Но поскольку я также обнаружил, что для других этот менее умный подход тоже работал, хотя и медленнее, я действительно хотел понять, почему я просто не могу сделать то же самое в Clojure. В основном все, что я делаю, это ищу значения в векторе и выполняю два вложенных цикла for для изменения индексов.
2. Причина, по которой я не определил простые числа как def, заключалась в том, что, насколько я знаю, Clojure than зависает в начале этого, поэтому, если я использую список, он остается в памяти после этого. Таким образом, я могу просто отбросить то, что мне не нужно (не то, чтобы это использовалось здесь подобным образом).
Ответ №2:
Я приму свой собственный комментарий в качестве ответа на вопрос, почему Python работал, а Clojure нет: использование last
вектора — это линейная операция, которая не позволила вычислить совокупную сумму так, как я предполагал.
Обновление функции для использования переходного вектора, подобного этому:
(defn cumulative-sum-2 [s]
(loop [[x amp; xs] s
ss 0
acc (transient [])]
(if x
(let [ssx ( ss x)]
(recur xs ssx (conj! acc ssx)))
(persistent! acc))))
в результате версия Clojure последовательно выполняется только в два раза дольше, чем Python. Я вроде как надеялся, что Clojure будет быстрее, чем Python, для тех же операций, интересно, я все еще что-то упускаю. Кстати, я использую 1.2.
Спасибо
Комментарии:
1. Существует также,
peek
который такой же, какlast
для векторов, но гораздо более эффективный.