брутфорс с ленивой оценкой и потреблением памяти

Я реализовал небольшую функцию 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 мб должно хватить?

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

ну нет (Мне бы такой подход все равно не понравился...)

Любые указатели, как можно было бы переписать bruteforce, чтобы быть более удобным для памяти?

6
задан lewurm 9 July 2012 в 08:23
поделиться