爲什麼我的Clojure素數懶惰序列如此緩慢？

Question

我正在做項目歐拉問題7（計算10001總理）。我編寫了一個懶惰序列形式的解決方案，但它超慢，而我在網絡上找到的另一個解決方案（下面的鏈接）和基本上相同的東西需要不到一秒鐘的時間。

我是新來的clojure和懶惰的序列，所以我使用take-while，懶貓休息或地圖可能是罪魁禍首。你能否看看我的代碼，並告訴我，如果你看到任何東西？

，一個第二下運行的解決方案是在這裏： https://zach.se/project-euler-solutions/7/

它不使用懶惰序列。我想知道爲什麼它如此之快，而我的速度太慢（他們遵循的過程是相似的）。

我的解決方案，它是超級慢：

(def primes 
    (letfn [(getnextprime [largestprimesofar] 
    (let [primessofar (concat (take-while #(not= largestprimesofar %) primes) [largestprimesofar])] 
     (loop [n (+ (last primessofar) 2)] 
      (if 
      (loop [primessofarnottriedyet (rest primessofar)] 
       (if (= 0 (count primessofarnottriedyet)) 
       true 
       (if (= 0 (rem n (first primessofarnottriedyet))) 
        false 
        (recur (rest primessofarnottriedyet))))) 
      n 
      (recur (+ n 2))))))] 
    (lazy-cat '(2 3) (map getnextprime (rest primes))))) 

要嘗試，只需加載和運行像（取10000個素數），而使用Ctrl + C殺死進程，因爲實在是太慢了。但是，如果您嘗試（取100個素數），您應該立即獲得答案。

Answer 1

讓我重新編寫一段代碼，將其分解成更容易討論的代碼。我使用的是相同的算法，我只是將一些內部表單分解成單獨的函數。

(declare primes) ;; declare this up front so we can refer to it below 

(defn is-relatively-prime? [n candidates] 
    (if (= 0 (count candidates)) 
    true 
    (if (zero? (rem n (first candidates))) 
     false 
     (is-relatively-prime? n (rest candidates))))) 

(defn get-next-prime [largest-prime-so-far] 
    (let [primes-so-far (concat (take-while #(not= largest-prime-so-far %) primes) [largest-prime-so-far])] 
    (loop [n (+ (last primes-so-far) 2)] 
     (if 
     (is-relatively-prime? n (rest primes-so-far)) 
     n 
     (recur (+ n 2)))))) 

(def primes 
    (lazy-cat '(2 3) (map get-next-prime (rest primes)))) 

(time (let [p (doall (take 200 primes))])) 

最後一行只是爲了更容易在REPL中獲得一些非常粗糙的基準。通過將時序聲明作爲源文件的一部分，我可以不斷重新加載源代碼，並且每次都獲得新的基準。如果我只加載一次文件，並繼續嘗試執行(take 500 primes)，則基準將會傾斜，因爲primes將保留其已計算的素數。我還需要doall，因爲我在let聲明中提取素數，如果我不使用doall，它只會將延遲序列存儲在p中，而不是實際計算素數。

現在，讓我們得到一些基本值。在我的電腦，我得到這個：

Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 274.492597 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 293.673962 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 322.035034 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 285.29596 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 224.311828 msecs" 

所以約275毫秒，或採取50.我的第一個懷疑是我們如何讓primes-so-far在let語句中get-next-prime。我們正在通過完整的素數列表（直到我們擁有它），直到我們得到一個與迄今爲止最大的素數相等的數。然而，我們構建代碼的方式，所有素數都已排序，所以我們有效地遍歷除最後一個素數以外的所有素數，然後連接最後一個值。我們得到的結果與primes序列中已經實現的完全相同，因此我們可以跳過整個步驟，只使用primes。這應該可以拯救我們

我的下一個懷疑是呼叫(last primes-so-far)在循環中。當我們在一個序列上使用last函數時，它也從頭到尾拖曳列表（或者至少，這是我的理解 - 我不會讓它通過Clojure編譯器編寫者， case code來加快速度。）但是，我們不需要它。我們打電話get-next-prime與largest-prime-so-far，並且由於我們的素數是有序的，就已經意識到它們而言，這已經是素數的最後一個了，所以我們可以使用largest-prime-so-far而不是(last primes)。這會給我們這樣的：

(defn get-next-prime [largest-prime-so-far] 
    ; deleted the let statement since we don't need it 
    (loop [n (+ largest-prime-so-far 2)] 
    (if 
     (is-relatively-prime? n (rest primes)) 
     n 
     (recur (+ n 2))))) 

這似乎像它應該加快速度，因爲我們已經消除了兩個完整的走過的素數序列。我們來試試吧。

Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 242.130691 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 223.200787 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 287.63579 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 244.927825 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 274.146199 msecs" 

嗯，也許稍微好一些（？），但沒有接近我預期的改善。我們來看看is-relatively-prime?的代碼（正如我重寫的那樣）。首先跳出來的是count函數。 primes序列是一個序列，而不是一個向量，這意味着count函數也必須遍歷完整列表以添加其中的元素。更糟糕的是，如果我們從10個候選人名單開始，第一次走完整個循環，然後走下一個循環的剩餘九個候選人，然後剩下8個候選人，依此類推。隨着質數越來越大，我們將在計數函數中花費越來越多的時間，所以也許這就是我們的瓶頸。

我們想擺脫那count，並且這表明我們可以使用if-let做更循環的方式。就像這樣：

(defn is-relatively-prime? [n candidates] 
    (if-let [current (first candidates)] 
    (if (zero? (rem n current)) 
     false 
     (recur n (rest candidates))) 
    true)) 

的(first candidates)函數將返回nil如果候選人列表是空的，如果出現這種情況，if-let功能會發現，並自動跳轉到else子句，在這種情況下是我們的返回結果的「真」。否則，我們將執行「then」子句，並且可以測試n是否可以被當前候選人整除。如果是的話，我們會回覆錯誤的，否則我們會和其他候選人一起回頭。我也利用了zero?的功能，只是因爲我可以。讓我們看看這給我們帶來了什麼。

Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 9.981985 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 8.011646 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 8.154197 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 9.905292 msecs" 
Loading src/scratch_clojure/core.clj... done 
"Elapsed time: 8.215208 msecs" 

很有戲劇性，呃？我是一箇中級Clojure編碼器，對內部構件有一個非常粗略的理解，所以我用一粒鹽來分析我的分析結果，但基於這些數字，我猜你會被count咬傷。

有「快」的代碼是使用你的是不是一個其他的優化，而這想逃出來的is-relatively-prime?測試時current平方比n更大---你可能會加速你的代碼多一些，如果你能把它扔進去。但我認爲count是你要找的主要東西。

Answer 2

基於@ manutter的解決方案，我會繼續加快速度。

(declare primes) 

(defn is-relatively-prime? [n candidates] 
    (if-let [current (first candidates)] 
    (if (zero? (rem n current)) 
     false 
     (recur n (rest candidates))) 
    true)) 

(defn get-next-prime [largest-prime-so-far] 
    (let [primes-so-far (concat (take-while #(not= largest-prime-so-far %) primes) [largest-prime-so-far])] 
    (loop [n (+ (last primes-so-far) 2)] 
     (if 
     (is-relatively-prime? n (rest primes-so-far)) 
     n 
     (recur (+ n 2)))))) 

(def primes 
    (lazy-cat '(2 3) (map get-next-prime (rest primes)))) 

(time (first (drop 10000 primes))) 

「經過時間：14092.414513毫秒」

確定。首先，讓我們來添加這個current^2 > n優化：

(defn get-next-prime [largest-prime-so-far] 
    (let [primes-so-far (concat (take-while #(not= largest-prime-so-far %) primes) [largest-prime-so-far])] 
    (loop [n (+ (last primes-so-far) 2)] 
     (if 
      (is-relatively-prime? n 
           (take-while #(<= (* % %) n) 
              (rest primes-so-far))) 
     n 
     (recur (+ n 2)))))) 

user> (time (first (drop 10000 primes))) 
"Elapsed time: 10564.470626 msecs" 
104743 

尼斯。現在讓我們來看看get-next-prime接近：

，如果你仔細檢查算法，你會發現，這樣的： (concat (take-while #(not= largest-prime-so-far %) primes) [largest-prime-so-far])真的等於所有到目前爲止，我們已經找到了素數，並(last primes-so-far)真是largest-prime-so-far。因此，讓我們把它改寫了一點：

(defn get-next-prime [largest-prime-so-far] 
    (loop [n (+ largest-prime-so-far 2)] 
    (if (is-relatively-prime? n 
      (take-while #(<= (* % %) n) (rest primes))) 
     n 
     (recur (+ n 2))))) 

user> (time (first (drop 10000 primes))) 
"Elapsed time: 142.676634 msecs" 
104743 

讓我們增加一個數量級以上順序：

user> (time (first (drop 100000 primes))) 
"Elapsed time: 2615.910723 msecs" 
1299721 

哇！這只是令人興奮的！

但這並非全部。讓我們來看看is-relatively-prime函數： 它只是檢查沒有候選人均勻分配數字。所以它真的是什麼not-any?庫功能。所以讓我們把它替換成get-next-prime。

(declare primes) 

(defn get-next-prime [largest-prime-so-far] 
    (loop [n (+ largest-prime-so-far 2)] 
    (if (not-any? #(zero? (rem n %)) 
        (take-while #(<= (* % %) n) 
           (rest primes))) 
     n 
     (recur (+ n 2))))) 

(def primes 
    (lazy-cat '(2 3) (map get-next-prime (rest primes)))) 

實在是有點更高效

user> (time (first (drop 100000 primes))) 
"Elapsed time: 2493.291323 msecs" 
1299721 

，顯然更清潔和更短。