Утечка пространства в программе списка

Question

Я решаю некоторые проблемы Project Euler в Haskell. Я написал программу для загадки, и она не сработала, как я ожидал.

Когда я посмотрел в диспетчере задач при запуске программы, я увидел, что она использует> 1 гигабайт оперативной памяти на 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

Я знаю, что эта программа выдаст желаемое число, учитывая достаточное количество оперативной памяти и времени, но должен быть более эффективный способ.

Answer 1

Основная проблема здесь в том, что в последовательности есть утечка пространства. Это определяется так:

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. ответ вроде бы Just 1229314359627783009

Редактировать версия без конкатата:

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

обратите внимание, что обе эти версии генерируют результаты в порядке, отличном от стандартного sequence, поэтому, пока они работают для этой проблемы, мы не можем использовать его в качестве специализированной версии sequence.

Answer 2

Исходя из ответа, данного Саймоном Марлоу, приведена версия последовательности, которая позволяет избежать утечки пространства, в то же время работая так же, как оригинал, включая сохранение порядка.

Он по-прежнему использует простое понимание списка оригинальной последовательности - единственное отличие состоит в том, что введена ложная зависимость от данных, которая препятствует совместному использованию рекурсивного вызова.

sequenceDummy d [] = d `seq` [[]]
sequenceDummy _ (xs:xss) = [ y:ys | y <- xs, ys <- sequenceDummy (Just y) xss ]

sequenceUnshared = sequenceDummy Nothing

Я думаю, что это лучший способ избежать совместного использования, которое приводит к утечке пространства.

Я бы обвинял чрезмерное разделение в преобразовании "полной лени". Обычно это делает большую работу по созданию совместного использования, которое позволяет избежать повторных вычислений, но иногда повторное вычисление намного более эффективно, чем сохранение общих результатов.

Было бы неплохо, если бы был более прямой способ сказать компилятору не делиться определенным выражением - приведенный выше фиктивный аргумент Maybe работает и эффективен, но в основном это хак, достаточно сложный, чтобы ghc мог не говорите, что нет реальной зависимости. (На строгом языке у вас нет этих проблем, потому что у вас есть общий доступ, когда вы явно привязываете переменную к значению.)

Answer 3

Поскольку вы ищете девятнадцатизначное число с теми характеристиками, которые есть в vw, я постараюсь упростить конструкцию в отображенной функции, просто скажем fromDigits x*1000+9 для начинающих.При добавлении к списку используется O (длина левого списка), поэтому добавление последних трех цифр в конец сокращает время вычислений.

В качестве отступления (для вас обоих), используястрогая версия сгиба (foldl1') также поможет.

Answer 4

РЕДАКТИРОВАТЬ: я думаю, что я здесь не так - изменение сигнатуры типа на :: Может быть, 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