暴力评估和内存消耗的暴力

Question

我实现了一个小函数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)

也可以作为一个要点.是的,测试功能是愚蠢的,但它足以显示问题所在.它按预期工作,但内存消耗很高:

$ 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).200 MB应该够了吗？

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

好吧,不,(我不喜欢这种方法......)

任何指针如何重写bruteforce为更友好的内存？

Answer 1

如果主要考虑内存消耗,请停止共享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)

小居民记忆.当然,重新计算意味着总分配要高得多,计算结果也需要更长的时间.

更好的算法可以减少空间和时间消耗.

Answer 2

你可以跳过所有这些Just,Nothing我猜...

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"]本例中的列表).您可以想象,随着n增加,后缀列表将随之增长26^n,而前缀列表将随之增长n.当然,这是以每次迭代构造整个当前字符串为代价的,但内存使用率要低得多.

Answer 3

我认为你的发电机太严格了.一个最佳的生成器应该尽可能多地产生结果列表,只需要很少的关于递归应用程序结果的信息.

让我们考虑以下几行.

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)

尽管如此,由于此更改非常适用于手头的应用程序,因此可能不适用于您的实际应用程序.