Eloer 50の同等のソリューションでClojureがPythonより10倍遅いのはなぜですか？

Question

私は最近Clojureを学び始め、利用可能なデータ構造と再帰とループを練習するためにオイラーの問題を練習することに決めました。

私はProblem 50にさまざまなアプローチを試みましたが、私が何をしても、1000000の解決策を見つけることは決して終わりませんでした。私は他の人が何をしたかを調べた後、私がやっていたことは永遠に取るべきではないと思ったので、Pythonで等価なアルゴリズムを打ち込んで、ClojureのことやJavaの設定の問題があるかどうかを調べました。 Pythonは10秒で終了しました。 100000未満の素数については、Pythonバージョンは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" 

そして、ここでは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 

おかげ

Answer 1

私はのための答えとしての私自身のコメントを受け付けますなぜPythonが働いていたのか、Clojureはしなかったのですか？lastベクトルの使用は、私が意図した通りに累積合計が計算されるのを防ぐ線形演算です。

このような一過性のベクターを使用する機能の更新：常に、唯一の倍の長Pythonなどを実行するにはClojureのバージョンで

(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が同じ操作のためにPythonより早くなることを望んでいました。私は途中で1.2を使用しています。

ありがとうございました

Answer 2

私は減速がで配列を介して、あなたが反復回数から来ていると思いますlongest-seq-under;それらの反復のそれぞれがその通行料を払う。ここにあなたのコードと答えの組み合わせに基づいて、喫煙高速版です投稿here。 primesは怠け者であることに注意してください、私たちはdefn対defとそれをバインドすることができます。これは、私のマシンで約6ミリ秒で終了

(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)))))) 

：

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