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