Eloer 50의 동등한 솔루션에 대해 Clojure가 Python보다 10 배 더 느린 이유는 무엇입니까?



performance comparison (2)

최근에 Clojure를 배우기 시작했고 오일러 문제를 연습하여 사용 가능한 데이터 구조를 파악하고 반복 및 반복을 연습하기로 결정했습니다.

문제 50에 대한 다양한 접근법을 시도했지만, 내가 한 것과 상관없이, 1000000에 대한 솔루션을 찾지 못했습니다. 다른 사람들이 무엇을했는지를 조사한 후에도 영원히 받아 들여서는 안되는 것을 짐작했다. Python에서 동등한 알고리즘을 사용하여 문제가 Clojure 나 Java 설정에 대한 이해가 부족한 것인지 확인했다. 파이썬은 10 초 만에 완성되었습니다. 100000 미만의 소수에 대해서는 파이썬 버전이 0.5 초, Clojure가 5로 끝난다.

나는 Python 코드와 일치하도록 특별히 만들어진 Clojure 버전을 게시하고있다. 왜 그런 성능 차이가 있는지 이해할 수 있습니까? 확인되지 않은 추가, 형식 힌트, 프리미티브 (하지만?) 또는 무엇을 사용해야합니까?

여기 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"

파이썬에서도 마찬가지입니다.

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

감사

https://src-bin.com


Answer #1

Python이 작동하는 이유와 Clojure가하지 않은 질문에 대한 대답으로 내 자신의 의견을 받아 들일 것입니다. last 벡터 사용은 누적 합계가 의도 한대로 계산되지 못하게하는 선형 작업입니다.

다음과 같은 임시 벡터를 사용하는 함수 업데이트 :

(defn cumulative-sum-2 [s]
  (loop [[x & xs] s
         ss 0
         acc (transient [])]
    (if x      
      (let [ssx (+ ss x)]
        (recur xs ssx (conj! acc ssx)))
      (persistent! acc))))

결과적으로 Clojure 버전은 파이썬보다 두 배나 길게 실행됩니다. 나는 Clojure가 똑같은 작업을하기 위해 파이썬보다 더 빨라 졌으면 좋겠다. 나는 아직도 뭔가를 놓친다는 것을 궁금해한다. 나는 1.2를 사용하고있다.

감사


Answer #2

나는 slowdown이 longest-seq-under 의 시퀀스를 반복하는 횟수에 기인한다고 생각합니다. 그 반복의 각각은 그것의 통행세를 가지고 간다. 여기에 게시 된 코드와 답변의 조합을 기반으로 한 빠른 버전의 금연입니다. primes 는 게으르므로 defdefn 바인드 할 수 있습니다.

(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 & xs]]
  (map first (iterate
              (fn [[sum [s & 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))))))

내 컴퓨터에서 약 6ms 후에 완료되었습니다.

user> (time (euler-50 1000000))
"Elapsed time: 6.29 msecs"
997651




comparison