如何避免不必要的計算？

如果列表中超過3個元素的測試失敗，我需要返回false。有什麼我可以做的優化？如何避免不必要的計算？

isItemOk :: Integer -> Boolean 
isItemOk = (some costly opernation)

這是我試圖優化功能，

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ([ 1 | x <- [1.1000], isItemOk x ])

我的優化嘗試，假設，如果它發現4個元素不會尋找更多的需要。

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum (take 4 [ 1 | x <- [1.1000], isItemOk x ])

謝謝。

來源

2012-09-19 Biswanath

由於'take'和'list comprehension'是懶惰的，你的函數不會超越4。如果你知道你的號碼不會超出限制，那麼嘗試使用'Int'，因爲它比'Integer'快得多。它是'Bool'而不是'Boolean'。 'isListOk'應該帶一個列表參數。 – Satvik

你可以只用filter的東西，檢查失敗的元素，那麼take 4，看看你有多少個元素與length。

懶惰的評估意味着它不會打擾檢查後發現這四個，所以你完成了。當然，如果三個或更少元素的測試失敗，它會檢查整個列表，但是你無能爲力。

避免的重要事情就像「計數測試失敗的元素」或「過濾然後獲取結果的長度」，或類似的東西。如果不先使用take或類似的東西，那麼會強制檢查整個列表。這是「使用null或模式匹配檢查空列表」的更一般版本，通常給初學者提供建議。但看起來你已經在避免這個錯誤！

來源

2012-09-19 23:44:18

對於像3這樣的低數字，您可以使用模式匹配。

case filter isItemOk xs of 
    x1 : x2 : x3 : _ -> ... 
    _    -> ...

來源

2012-09-19 23:42:42 hammar

首先，讓我重寫你的函數一點，因爲

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3

可以說是比你的版本更地道。（請注意，我也改變了類型簽名和你是不正確的。此外，你應該寫1 .. 1000而非1.1000）

懶惰的評價是在這裏你最好的朋友，因爲它通常會確保沒有不必要的計算將是執行。

不幸的是，您在使用length（或將列表中的每個元素映射到1，然後總結結果列表，就像你這樣做）正在阻礙你。也就是說，length在列表的脊柱中是嚴格的：只有當列表的長度達到最後才能產生列表的長度，在這種情況下，這意味着您的程序必須運行您的支票一千次。

一種解決方案是將長度的計算（即，中，列表的脊柱的遍歷）和測試是否所計算的長度不超過一個給定閾值到一個單一的功能即實際上在它的參數列表的脊柱懶：

isNotLongerThan :: [a] -> Integer -> Bool 
isNotLongerThan []  n = n >= 0 
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1)

然後寫

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3

對於可重複使用的解決方案，可以在謂語和閾值兩者當然摘要：

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool 
forNoMoreThan p n = (`isNotLongerThan` n) . filter p 

isListOk :: Bool 
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000]

最後，哈馬爾指出，如果你的脫粒舊的足夠小並且固定，您可以簡單地使用模式匹配來確定列表是否足夠短。

來源

2012-09-20 00:52:08

我想借此機會宣傳lazy natural numbers一下。使用這個庫和genericLength，我們可以只寫

import Data.Number.Natural 
import Data.List 
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000])

，它會做任何更多的工作比它：這個函數將返回前找到最多四個好項目。例如：

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined)) 
False

來源

2012-09-20 06:11:01

如何避免不必要的計算？

回答

相關問題