6

bruteforce問題の最初の有効な解決策を見つけるために遅延評価を使用して 、小さな関数を実装しました。

import Data.Maybe

bruteforce :: (a -> Bool) -> [a] -> Maybe a
bruteforce f xs
  | null result = Nothing
  | otherwise = Just $ head result
  where
    result = mapMaybe bruteforce' xs
    -- test one instance
    bruteforce' x
      | f x = Just x
      | otherwise = Nothing

generatorString :: Int -> [String]
generatorString 0 = [""]
generatorString deep = concatMap (\x -> map (\ys -> (x:ys)) nextgen) ['a'..'z']
  where nextgen = generatorString (deep - 1)


main :: IO ()
main = do
  putStrLn $ fromJust $ bruteforce ((==) "zabcde") (generatorString 6)

gist としても利用できます。はい、テスト関数はばかげていますが、何が問題なのかを示すには十分です。期待どおりに動作しますが、メモリ消費量が非常に多くなります。

$ ghc --make -O2 brute.hs -o brute -rtsopts
$ ./brute +RTS -s
zabcde
  24,752,866,120 bytes allocated in the heap
  15,748,430,224 bytes copied during GC
     581,741,352 bytes maximum residency (22 sample(s))
      18,464,056 bytes maximum slop
            1719 MB total memory in use (0 MB lost due to fragmentation)
[...]

そこで、より少ないメモリを使用して RTS を強制しようとしました (つまり、GC をより頻繁に呼び出します)。200MBで十分ですか？

$ ./brute +RTS -s -M200M
Heap exhausted;
Current maximum heap size is 209715200 bytes (200 MB);
use `+RTS -M<size>' to increase it.

まあ、いいえ（とにかくこのアプローチは好きではありません...）

bruteforceよりメモリに優しいように書き直す方法はありますか?

4

4 に答える 4

10

メモリ消費が主な懸念事項である場合は、共有を停止しnextgenます。それは巨大なリストです。

だから交換

generatorString deep = concatMap (\x -> map (\ys -> (x:ys)) nextgen) ['a'..'z']
  where nextgen = generatorString (deep - 1)

と

generatorString deep = concatMap (\x -> map (\ys -> (x:ys)) $ generatorString (deep - 1)) ['a'..'z']

そして、それを共有しないことを真剣に考えていることをコンパイラーに伝えます。

$ ghc -O2 -fno-full-laziness -rtsopts bruteforce

それが実行されます

 $ ./bruteforce +RTS -s
 zabcde
 189,448,835,904 bytes allocated in the heap
  18,301,350,520 bytes copied during GC
          29,504 bytes maximum residency (16901 sample(s))
          37,248 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

小さな常駐メモリ。もちろん、再計算は合計割り当てがはるかに高く、結果の計算にもはるかに長い時間がかかることを意味します。

より良いアルゴリズムは、スペースと時間の消費を削減できます。

于 2012-07-09T09:14:40.830 に答える
7

私が推測するすべてのJusts とNothings をスキップできます...

import Data.Maybe (listToMaybe)

bruteforce   :: (a -> Bool) -> [a] -> Maybe a
bruteforce f = listToMaybe . filter f

これはおそらく可能な限りメモリに優しいものbruteforceです。その他の問題は、fブルート フォースされている関数が原因です。

関数は次のgeneratorStringように書き直すことができます。

import Control.Monad (replicateM)

generatorString :: Int -> [String]
generatorString = flip replicateM ['a'..'z']

これがどのように機能するかを説明したい場合は、コメントでお知らせください。要するに、サフィックス共有ではなくプレフィックス共有を使用することです。つまり、次のような文字列を生成します。

"aa"
"ab"
...
"az"
"ba"

... それ以外の：

"aa"
"ba"
...
"za"
"ab"
"bb"

これは、サフィックスのリストを保存して再利用するのではなく、プレフィックス (この単純な例では と のみ) が共有されることを意味します (この例のリスト('a':)) 。増加するにつれて、接尾辞リストは で増加し、接頭辞リストは で増加することが想像できます。もちろん、これには反復ごとに現在の文字列全体を構築するという代償が伴いますが、メモリ使用量ははるかに少なくなります。('b':)["a", "b", "c", ..., "z"]n26^nn

于 2012-07-09T08:33:43.927 に答える
6

あなたのジェネレーターはちょっと厳しすぎると思います。最適なジェネレーターは、再帰アプリケーションの結果に関する情報をできるだけ少なくして、できるだけ多くの結果リストを生成することになっています。

次の行を考えてみましょう。

concatMap (\x -> map (\ys -> (x:ys)) nextgen) ['a'..'z']

nextgen空のリストではないことがわかっている場合にどうなるかを確認してみましょう。これを説明するために、変数nextgenを式で置き換えますundefined:undefined。次の式は、考慮される式の評価を示しています。

  concatMap (\x -> map (\ys -> (x:ys)) (undefined:undefined)) ['a'..'z']
= concat (map (\x -> map (\ys -> (x:ys)) (undefined:undefined)) ['a'..'z'])
= concat (map (\ys -> ('a':ys)) (undefined:undefined) : map (\x -> map (\ys -> (x:ys)) (undefined:undefined)) ['b'..'z'])
= concat (('a':undefined) : undefined) : map (\x -> map (\ys -> (x:ys)) (undefined:undefined)) ['b'..'z'])
= ('a':undefined) : undefined

特定のアプリケーションでは、生成された文字列の最初の文字と検索文字列を比較することで、すでに多くの結果を破棄できます。したがって、生成された文字列の先頭をできるだけ早く生成するジェネレータを探しています。

静的情報 (文字のリスト) と再帰アプリケーションの役割を変更してみましょう。次の式が得られます。

concatMap (\ys -> map (:ys) ['a'..'z']) nextgen

では、先ほどと同じように計算してみましょう。

  concatMap (\ys -> map (:ys) ['a'..'z']) (undefined:undefined)
= concat (map (\ys -> map (:ys) ['a'..'z']) (undefined:undefined))
= concat (map (:undefined) ['a'...'z'] : map (\ys -> map (:ys) ['a'..'z']) undefined)
= map (:undefined) ['a'...'z'] ++ concat (map (\ys -> map (:ys) ['a'..'z']) undefined

アプリケーションmap (:undefined) ['a'...'z']は、すべてのヘッドが定義されているリストをすでに生成しています。したがって、再帰アプリケーションを通常の形式で評価するだけで、これらの文字列のほとんどに対してテストがすでに失敗する可能性があります。

この変更された実装により、次の結果が得られます。

$ ./brute +RTS -s
zabcde
4,165,170,696 bytes allocated in the heap
    5,569,320 bytes copied during GC
       29,848 bytes maximum residency (5 sample(s))
       26,560 bytes maximum slop
            2 MB total memory in use (0 MB lost due to fragmentation)

ただし、この変更は当面のアプリケーションに固有のものであるため、実際のアプリケーションには適用できない場合があります。

于 2012-07-09T10:49:16.117 に答える
1

まだ誰もこれについて言及していないようなので、私はそれを指摘したいと思います

ブルートフォース = Data.List.find

于 2012-07-09T22:58:05.437 に答える