執行較慢使用無限列表

當我開始嘗試讓我的頭一輪的Haskell性能，是什麼使事物快，慢，和我這個有點困惑。執行較慢使用無限列表

我有一個生成素數的列表達到一定值的函數的兩種實現。首先是直客哈斯克爾維基：

primesTo :: (Ord a, Num a, Enum a) => a -> [a] 
primesTo m = eratos [2..m] where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m])

第二個是相同的，但使用一個無限清單內：

primes2 :: (Ord a, Num a, Enum a) => a -> [a] 
primes2 m = takeWhile (<= m) (eratos [2..]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..])

在這兩種情況下，負作用是：

minus :: (Ord a) => [a] -> [a] -> [a] 
minus (x:xs) (y:ys) = case (compare x y) of 
      LT -> x : minus xs (y:ys) 
      EQ ->  minus xs  ys 
      GT ->  minus (x:xs) ys 
minus xs _ = xs

後者的實現比前者慢得多（〜100x），我不明白爲什麼。我會認爲哈斯克爾的懶惰評估會讓他們在引擎蓋下相當等價。

這顯然是一個簡化的測試用例 - 在現實生活中，優化是沒有問題的（雖然我不明白爲什麼需要這樣做），但對我來說，一個函數只會產生一個無限的素數列表比有限列表更普遍有用，但看起來較慢。

來源

2014-01-19 WillW

注意，您可以提振takeWhile出primes2的，並獲得了嘗試更寬泛的素數的功能。你可以看看生成的核心和C來查看差異，但我認爲，簡而言之，從算法上思考，不同之處在於無限列表版本做了一些「重疊」工作，使得獲得m + 1的工作比primesTo兩次，爲m，然後爲m + 1。但如果你不需要這項工作，最好不要這樣做。因此，對於這種算法，如果您事先知道您需要的最大值，則可以節省工作量。 – misterbee

作爲一個練習來找到另一個具有類似屬性的問題+算法會很有啓發。 – misterbee

看起來，我認爲有minus步驟，通過成對列表

(xs `minus` [p*p, p*p+p..m]) -- primesTo 
(xs `minus` [p*p, p*p+p..]) -- primes2

的功能有很大的區別，當一個表到達結束終止。在上面的第一個minus表達式中，當後面的列表耗盡時，不會超過(m-p*p)/p步驟。在第二個中，它將總是採取步驟length xs的順序。

所以你的無限列表禁用了至少一個有意義的優化。

來源

2014-01-19 21:00:03

我知道後面的列表終止了minus的執行，並且當p傾向於m時，負值計算變得更短。我試圖理解的是懶惰評估的時間和地點，並且不適用於無限列表 - 我期望在這種情況下，減號只會被評估爲儘可能多地滿足takeWhile（以及上述所有內容它）與明確界定的情況不會有太大的不同。 – WillW

'minus'不會逐個列出列表。只有當頭相等時，兩個名單纔會消耗「減」。所以在這兩種情況下，步數將更接近'length xs'。然而，在第一個例子中，可以耗盡素數列表，避免使用thunk，並檢查'p'的最後一個倍數和下一個倍數之間的'xs'。 – ollanta

一個區別是，在第二種情況下，你需要生成一個額外的素數。在takeWhile知道停止之前，您需要生成大於m的第一個素數。

此外，這兩個名單上的[..m]邊界過濾和倍數的名單有助於減少計算次數。只要其中一個列表變爲空，minus立即通過它的secons子句返回，而在無限情況下，負值在第一種情況下卡住。您可以探索這個好一點，如果你還測試情況：只有列表中的一個是無限的：

--this is also slow 
primes3 :: (Ord a, Num a, Enum a) => a -> [a] 
primes3 m = takeWhile (<= m) (eratos [2..m]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..]) 

--this fast 
primes4 :: (Ord a, Num a, Enum a) => a -> [a] 
primes4 m = takeWhile (<= m) (eratos [2..]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m])

來源

2014-01-19 21:09:29 hugomg

執行較慢使用無限列表

回答

相關問題