在haskell中有效地計算列表中某個元素的比例

Question

這需要長長的列表，我想這是我長期使用的問題。

ratioOfPrimes :: [Int] -> Double 
ratioOfPrimes xs = fromIntegral (length (filter isPrime xs))/ fromIntegral(length xs) 

有沒有更高效的方法呢？

Answer 1

length的雙重使用不是這裏的主要問題。您的實施中的多次遍歷產生了一個常數因子，並且使用雙重length和filter可以獲得O(3n)的平均複雜度。由於流融合，它甚至是O(2n)，正如Impredicative已經提到的那樣。但實際上，由於常數因素不會對性能產生顯着影響，因此甚至可以忽略它們，因此，傳統上講，您的實現仍具有O(n)的複雜度，其中n是輸入列表的長度。

這裏真正的問題是，只有當isPrime的複雜度爲O(1)時，上述情況纔會成立，但事實並非如此。該函數通過所有素數列表遍歷，所以它本身的複雜度爲O(m)。所以這裏戲劇性的性能下降是由於你的算法的最終複雜度爲O(n*m)造成的，因爲在輸入列表的每次迭代中，它必須將所有素數列表遍歷到未知深度。

爲了優化，我建議先對輸入列表（需要O(n*log n)）進行排序，然後在所有素數列表中迭代自定義查找，這將在每次迭代中刪除已訪問的數字。通過這種方式，您將能夠在所有素數列表上實現單遍歷，理論上可以授予您複雜度爲O(n*log n + n + m)，通過突出顯示成本中心，常規上可以將其簡單地看作O(n*log n)。

Answer 2

所以，這裏有一些事情要做。讓我們來看看一些操作涉及：

• length
• filter
• isPrime
• length

正如你所說，使用length兩次沒有什麼幫助，因爲這是列表爲O(n)。你做了兩次。然後是filter，它也將在O(n)中完成整個列表。我們想要做的就是一次性完成所有這些。

Data.List.Stream模塊中的功能實現了一種名爲Stream Fusion的技術，例如將您的(length (filter isPrime xs))調用重寫爲單個循環。不過，你仍然有第二次電話會議。你可以用一對蓄電池的重寫這整件事變成單眼皮（或使用該國家或ST單子），並在單次做到這一點：

ratioOfPrimes xs = let 
    (a,b) = foldl' (\(odd,all) i -> if (isPrime i) then (odd +1, all+1) else (odd, all+1)) (0,0) xs 
in a/b 

然而，在這種情況下，你也可以搬走從使用列表並使用vector庫。載體庫實現相同的流融合技術用於去除中間列表，但也有一些其它的漂亮的功能：

• length是O(1)
• 的Data.Vector.Unboxed模塊可以存儲unboxable類型（其原始類型如Int肯定是）沒有盒裝表示的開銷。所以這個int列表將被存儲爲一個低級的Int數組。

使用vector軟件包應該可以讓您編寫上面的慣用表示法，並且比單遍轉換的性能更好。

import qualified Data.Vector.Unboxed as U 

ratioOfPrimes :: U.Vector Int -> Double 
ratioOfPrimes xs = (fromIntegral $ U.length . U.filter isPrime $ xs)/(fromIntegral $ U.length xs) 

當然，這還沒有被提及的事情是isPrime功能，以及是否真正的問題是，它是爲大型n緩慢。一個不成熟的總檢查員可能會輕易地將注意力從列表中排除出水面。