爲什麼這個天真的篩實現這麼慢

這裏是我的代碼爲什麼這個天真的篩實現這麼慢

let primes = 
    let rec primesRec remain = 
     let prime = Seq.head remain 
     seq { yield Seq.head remain; yield! primesRec (Seq.filter (fun n -> n % prime <> 0) remain) } 
    primesRec (Seq.initInfinite (fun i -> i + 2))

首先，我知道這是不是有效，因爲篩是應該的，但我認爲它應該仍然比快得多它是。

Seq.take 100 primes |> List.ofSeq

已經花費的時間量noticable（< 1秒），它完全凍結1000（如，我不想再等待）。

所以，據我所知，這個序列的構造方法是先取其餘元素的第一個元素，然後遞歸生成其他元素，但過濾其餘元素。我錯在認爲這是複雜的二次方？它只是通過所有現有的素數來生成每個新的素數。

我知道，因爲我想要第1000個素數，它實際上在素數的大小上是二次的，大約是8000，但它應該仍然是大約100 000 000次迭代。不應該在一秒之內執行嗎？

來源

2014-07-03 Luka Horvat

你可能會喜歡這樣：真正的篩（http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf） - 也看看這個[現場] （http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell）） - 這裏都有解釋 – Carsten

無論代碼如何，100M迭代對於擠入第二個代碼都是非常重要的。 – Mau

這不是記憶remain seq所以每次迭代它都計算所有質數再次達到prime。

你有關100M迭代的理論可能是正確的，但請記住，它不僅僅是做一些模運算：它創建序列和迭代器，分配內存並將東西推入堆棧等等。

我通過如下緩存remain seq來製作此高性能。但是，您也可以使用List而不是seq來解決此問題。

let primes = 
    let rec primesRec remain = 
     let prime = Seq.head remain 
     seq { yield Seq.head remain; yield! primesRec (Seq.filter (fun n -> n % prime <> 0) (Seq.cache remain)) } 
    primesRec (Seq.initInfinite (fun i -> i + 2))

來源

2014-07-03 09:00:50

你可以給一些代碼來解決這個與F＃中的列表？（這是有點意思 - 有人認爲'seq's有他們懶惰..你有一個列表在這裏的問題...） – Carsten

爲什麼這個天真的篩實現這麼慢

回答

相關問題