Утечка пространства в программе списка
Я решаю некоторые проблемы Euler Проекта в Haskell. Я записал программу для загадки в нем, и она не работала, как я ожидал.
Когда я смотрел в диспетчере задач при запущении программы, я видел, что это использовало> 1 гигабайт RAM на ghc. Друг меня записал программу с тем же значением в Java и успешно выполнился за 7 секунд.
import Data.List
opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) )
$ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]
vw x = hh^2 == x
where hh = (round.sqrt.fromIntegral) x
re = [0..9]
fromDigits x = foldl1 (\n m->10*n+m) x
Я знаю, что эта программа произвела бы число, которое я хочу, учитывая достаточное количество RAM и время, но должен быть лучше работающий путь.
3 ответа
Основная проблема здесь в том, что в последовательности не хватает места. Он определяется следующим образом:
sequence [] = [[]]
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ]
, поэтому проблема в том, что список, созданный рекурсивным вызовом sequence xss , повторно используется для каждого из элементов xs , поэтому он может Выбрасывать до конца. Версия без утечки места -
myseq :: [[a]] -> [[a]]
myseq xs = go (reverse xs) []
where
go [] acc = [acc]
go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ]
PS. ответ кажется Всего 1229314359627783009
Отредактируйте версию, избегая concat:
seqlists :: [[a]] -> [[a]]
seqlists xss = go (reverse xss) [] []
where
go [] acc rest = acc : rest
go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs
обратите внимание, что обе эти версии генерируют результаты в порядке, отличном от стандартной последовательности , поэтому пока они работают над этой проблемой, мы не можем использовать их как специализированную версию последовательности .
Поскольку вы ищете девятнадцатизначное число с теми характеристиками, которые есть в vw, я бы попытался упростить конструкцию в сопоставленной функции, для начала просто fromDigits x*1000+9. Дополнение списка - это O(length-of-the-left-list), так что накидывание последних трех цифр в конце сильно сокращает время вычислений.
В качестве дополнения (для вас обоих), использование строгой версии складки (foldl1') также поможет.
РЕДАКТИРОВАТЬ: Я думаю, что здесь я ошибаюсь - изменение сигнатуры типа на :: Может быть Word64 (что было бы достаточно бит для этой проблемы, я думаю) также занимает вечность / имеет утечку места, поэтому это не может быть старая ошибка Integer.
Кажется, ваша проблема связана со старой ошибкой GHC (которая, как я думал, была исправлена) с Integer, вызывающей утечку пространства. Приведенный ниже код завершается примерно через 150 мс при компиляции с -O2.
import Data.List
import Data.Word
main = print opl
opl :: Maybe Word32
opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) ) $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]
vw x = hh^2 == x
where hh = (round.sqrt.fromIntegral) x
re = [0..9]
fromDigits x = foldl1 (\n m->10*n+m) x