5

リスト内の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 ])

ありがとう。

4

4 に答える 4

8

filter失敗した要素をチェックするもので使用するだけで、 で要素のtake 4数を確認できますlength。

遅延評価とは、これら 4 つを見つけた後は何もチェックしないことを意味するので、これで完了です。もちろん、3 つ以下の要素でテストが失敗した場合は、リスト全体がチェックされますが、それについてできることは何もありません。

避けるべき重要なことは、「テストに失敗した要素を数える」、または「フィルタリングしてから結果の長さを取得する」、またはそのようなものです。最初にまたは同様のものを使用しtakeないと、リスト全体を強制的にチェックすることになります。nullこれは、初心者によくある「空のリストをチェックするためにパターン マッチングを使用する」というアドバイスの、より一般的なバージョンです。しかし、あなたはすでにその間違いを回避しているようです!

于 2012-09-19T23:44:18.180 に答える
6

3のような小さい数の場合は、パターンマッチングを使用できます。

case filter isItemOk xs of
   x1 : x2 : x3 : _ -> ...
   _                -> ...
于 2012-09-19T23:42:42.800 に答える
5

この機会に、怠惰な自然数を少し誇大宣伝したいと思います。このライブラリとを使用してgenericLength、次のように書くことができます

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

そしてそれはそれがしなければならない以上の仕事をしません：この関数は戻る前に多くても4つの大丈夫なアイテムを見つけます。例えば：

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined))
False
于 2012-09-20T06:11:01.287 に答える
4

最初に関数を少し書き直してみましょう。

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

間違いなく、あなたのバージョンよりも慣用的です。(あなたの型シグネチャが間違っていたので、型シグネチャも変更したことに注意してください。さらに、1 .. 1000ではなく書くべき1.1000でした。)

遅延評価は、通常、不必要な計算が実行されないようにするため、ここでの最良の友です。

残念ながら、あなたの使用length(またはリストから各要素を 1 にマッピングし、結果のリストを合計すること) は、ここで邪魔になっています。つまり、lengthはリストの背骨で厳密です: リストを最後まで評価した場合にのみ、リストの長さを生成できます。つまり、この場合、プログラムはチェックを 1000 回実行する必要があります。

解決策は、長さの計算 (つまり、リストのスパインの走査) と、​​計算された長さが特定のしきい値を超えないかどうかのテストを、実際にはそのスパインで遅延している単一の関数に結合することです。引数リスト:

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]

最後に、hammar が指摘するように、しきい値が十分に小さく固定されている場合は、単純にパターン マッチングを使用して、リストが十分に短いかどうかを判断できます。

于 2012-09-20T00:52:08.200 に答える