Perché Clojure è 10 volte più lento di Python per la soluzione equivalente di Euler 50?

Question

Recentemente ho iniziato a studiare Clojure e ho deciso di esercitarmi sui problemi di Eulero per comprendere le strutture dati disponibili e praticare la ricorsione e il ciclo.

Ho provato vari approcci a Problem 50, ma non importa quello che ho fatto, trovando la soluzione per 1000000 mai terminata. Dopo aver guardato cosa facevano gli altri, immaginavo che quello che stavo facendo non dovesse durare neanche per sempre, quindi ho digitato l'algoritmo equivalente in Python per vedere se il problema risiede nella mia mancanza di comprensione di qualche cosa Clojure, o impostazione Java. Python finito in 10 secondi. Per i primi di 100000, la versione di Python terminata in 0,5 sec, Clojure in 5.

Sto postando la versione Clojure che è stata creata appositamente per abbinare il codice Python. Puoi aiutarmi a capire perché c'è una tale differenza di prestazioni? Dovrei usare unchecked-add, digitare hint, primitives (ma dove?) O cosa?

Quindi, ecco 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" 

E qui è la stessa cosa 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 

Grazie

Answer 1

I accetterà il mio commento come risposta per il domanda perché Python abbia funzionato e Clojure no: usare last di un vettore è un'operazione lineare che ha impedito che la somma cumulativa venisse calcolata nel modo in cui intendevo che fosse.

Aggiornamento la funzione da utilizzare un vettore transitorio come questo:

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

risultati nella versione Clojure di eseguire solo il doppio del tempo come Python, in modo coerente. Ho sperato che Clojure sarebbe più veloce di Python per le stesse operazioni, mi chiedo se mi manchi ancora qualcosa. Sto usando 1.2 a proposito.

Grazie

Answer 2

Credo che il rallentamento viene dal numero di volte che iterazioni sulle sequenze in longest-seq-under; ognuna di queste iterazioni ha il suo pedaggio. Ecco una versione veloce fumante, basata su una combinazione del tuo codice e della risposta pubblicata here. Si noti che primes è pigro, in modo che possiamo legare con 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 & 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)))))) 

Questo finito in circa 6 ms sulla mia macchina:

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