Tại sao Clojure chậm hơn 10 lần so với Python đối với giải pháp tương đương Euler 50?

Question

Gần đây tôi đã bắt đầu học Clojure và quyết định thực hành các vấn đề về Euler để thu thập các cấu trúc dữ liệu có sẵn và thực hành đệ quy và lặp lại.

Tôi đã thử các cách tiếp cận khác nhau để Problem 50, nhưng không có vấn đề gì tôi đã làm, việc tìm kiếm giải pháp cho 1000000 chưa bao giờ kết thúc. Sau khi tôi tra cứu những gì người khác đã làm, tôi đoán những gì tôi đang làm không nên mất mãi mãi, vì vậy tôi gõ vào thuật toán tương đương trong Python để xem liệu vấn đề nằm trong sự thiếu hiểu biết của tôi về một số điều Clojure, hoặc thiết lập Java. Python hoàn thành trong 10 giây. Đối với số nguyên tố dưới 100000, phiên bản Python đã hoàn thành sau 0,5 giây, Clojure ở 5.

Tôi đăng phiên bản Clojure được tạo riêng để phù hợp với mã Python. Bạn có thể giúp tôi hiểu tại sao có sự khác biệt về hiệu suất như vậy không? Tôi có nên sử dụng bỏ chọn, thêm gợi ý, nguyên thủy (nhưng ở đâu?) Hoặc cái gì?

Vì vậy, đây là 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" 

Và đây là như nhau trong 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 

Cảm ơn

Answer 1

tôi sẽ chấp nhận bình luận riêng của tôi như là câu trả lời cho câu hỏi tại sao Python làm việc và Clojure không: sử dụng last của một vectơ là một phép toán tuyến tính, ngăn cản tổng tích luỹ được tính theo cách tôi dự định.

Cập nhật chức năng sử dụng một vector thoáng qua như thế này:

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

kết quả trong phiên bản Clojure chạy chỉ gấp đôi thời gian như Python, nhất quán. Tôi hy vọng Clojure sẽ nhanh hơn sau đó Python cho các hoạt động tương tự, tự hỏi nếu tôi vẫn còn bỏ lỡ một cái gì đó. Tôi đang sử dụng 1,2 bằng cách này.

Cảm ơn

Answer 2

Tôi nghĩ rằng sự suy giảm xuất phát từ số lần bạn lặp qua các chuỗi trong longest-seq-under; mỗi lần lặp lại đó đều mất phí. Đây là phiên bản hút thuốc nhanh, dựa trên sự kết hợp mã của bạn và câu trả lời được đăng here. Lưu ý rằng primes là lười biếng, vì vậy chúng tôi có thể gắn nó với 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)))))) 

này hoàn thành trong khoảng 6 ms trên máy tính của tôi:

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