¿Por qué Clojure es 10 veces más lento que Python para la solución equivalente de Euler 50?

Question

Recientemente comencé a aprender Clojure y decidí practicar en los problemas de Euler para familiarizarme con las estructuras de datos disponibles y practicar recursividad y bucles.

Probé varios enfoques para Problem 50, pero no importaba lo que hiciera, encontrar la solución para 1000000 nunca terminada. Después de buscar lo que otros hicieron, supuse que lo que estaba haciendo no debería durar demasiado, así que escribí el algoritmo equivalente en Python para ver si el problema radica en mi falta de comprensión de Clojure o configuración de Java. Python terminó en 10 segundos. Para números primos por debajo de 100000, la versión de Python finalizó en 0.5 segundos, Clojure en 5.

Estoy publicando la versión Clojure que se creó específicamente para que coincida con el código Python. ¿Puedes ayudarme a entender por qué hay tal diferencia en el rendimiento? ¿Debo utilizar unchecked-add, tipo sugerencias, primitivas (pero dónde?) O qué?

Así que aquí es 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" 

Y aquí es la misma en 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

Aceptaré mi comentario como respuesta a la pregunta por qué Python funcionó y Clojure no: el uso de last de un vector es una operación lineal que evitaba que la suma acumulada se computara de la manera que yo pretendía.

Actualización de la función de usar un vector transitoria como esto:

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

resultados en la versión Clojure que sólo se ejecutan dos veces más que Python, de forma coherente. Esperaba que Clojure fuera más rápido que Python para las mismas operaciones, me pregunto si aún extraño algo. Estoy usando 1.2 por cierto.

Gracias

Answer 2

Creo que la desaceleración proviene de la cantidad de veces que iterar a través de las secuencias en longest-seq-under; cada una de esas iteraciones tiene su precio. Aquí hay una versión para fumar rápido, basada en una combinación de su código y la respuesta publicada here. Tenga en cuenta que primes es lento, por lo que podemos enlazarlo 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)))))) 

Esto terminó en aproximadamente 6 ms en mi máquina:

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