Warum ist Clojure 10 mal langsamer als Python für die äquivalente Lösung von Euler 50?

Question

Ich habe vor kurzem begonnen, Clojure zu lernen und beschloss, an Euler-Problemen zu üben, um einen Überblick über die verfügbaren Datenstrukturen zu bekommen und Rekursion und Schleifenbildung zu üben.

Ich habe verschiedene Ansätze ausprobiert, um Problem 50 aber egal, was ich tat, die Lösung für 1000000 wurde nie fertig. Nachdem ich nachgeschaut habe, was andere gemacht haben, dachte ich mir, dass das, was ich mache, auch nicht ewig dauern sollte, also habe ich den entsprechenden Algorithmus in Python eingegeben, um zu sehen, ob das Problem in meinem mangelnden Verständnis von Clojure oder einer Java-Einstellung liegt. Python war in 10 Sekunden fertig. Für Primzahlen unter 100000 war die Python-Version in 0,5 Sekunden fertig, Clojure in 5.

Ich poste hier die Clojure-Version, die speziell für den Python-Code erstellt wurde. Können Sie mir helfen zu verstehen, warum es einen solchen Unterschied in der Leistung gibt? Sollte ich unchecked-add, type hints, primitives (aber wo?) oder was verwenden?

Hier ist also 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"

Und hier ist das Gleiche in 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

Gracias

Answer 1

Ich denke, die Verlangsamung kommt von der Anzahl der Iterationen durch die Sequenzen in longest-seq-under Jede dieser Wiederholungen fordert ihren Tribut. Hier ist eine schnelle Version, die auf einer Kombination aus Ihrem Code und der geposteten Antwort basiert aquí . Beachten Sie, dass primes ist faul, also können wir es mit def gegen 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 & 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))))))

Auf meinem Rechner war dies in etwa 6 ms abgeschlossen:

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

Answer 2

Ich akzeptiere meinen eigenen Kommentar als Antwort auf die Frage, warum Python funktioniert und Clojure nicht: mit last eines Vektors ist eine lineare Operation, die verhindert, dass die kumulative Summe so berechnet werden kann, wie ich es beabsichtigt hatte.

Aktualisieren der Funktion, um einen transienten Vektor wie diesen zu verwenden:

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

führt dazu, dass die Clojure-Version durchweg nur doppelt so lange läuft wie Python. Ich hatte irgendwie gehofft, dass Clojure schneller als Python für die gleichen Operationen sein würde, frage mich, ob ich noch etwas vermisse. Ich bin mit 1.2 durch die Art und Weise.

Gracias