Сценарию Haskell не хватает места

Я использую проект Euler, чтобы научиться Haskell, и у меня возникают проблемы с тем, как мой код выполняется с помощью haskell. Во второй задаче я вычисляю сумму всех четных чисел Фибоначчи до 4 миллионов. Мой скрипт выглядит так:

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

Hugs выдает ошибку «Сборка мусора не может освободить достаточно места», что, как я предполагаю, означает, что записи списка не освобождаются, поскольку они используются foldr.

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


lazy-evaluation haskell space
person Gabe Moothart    schedule 10.04.2009    source источник
comment
На самом деле хорошая идея. Я уже прошел через многие проблемы, но я хотел научиться Python. ЧП было бы хорошим способом сделать это.   -  person    schedule 30.04.2009

Ответы (5)


arrow_upward
6
arrow_downward

Ряд замечаний/подсказок:

  • x + sums from даже не оцениваются до самого конца
  • Вы берете первые 4 000 000 фибов, а не фибы до 4 000 000
  • Есть более простой способ сделать это

Изменить в ответ на комментарий

Я не буду говорить вам, что проще, потому что в этом вся прелесть задач Project Euler. Но я задам вам кучу вопросов:

  • Сколько четных фибов вы можете иметь подряд?
  • Как долго вы можете обходиться без четной выдумки?
  • Если вы суммируете все четные и нечетные вымыслы (сделайте это вручную), что вы заметите в суммах?
person MarkusQ    schedule 10.04.2009
comment
Я начал с сумм x +, но 4M чисел Фибоначчи представляют собой еще большую проблему! Привет Маркус! - person Norman Ramsey; 10.04.2009
comment
Спасибо... а как проще? - person Gabe Moothart; 10.04.2009
comment
Найдите функции фильтрации и суммы прелюдии. - person Paul Johnson; 11.04.2009

arrow_upward
8
arrow_downward

Во-первых, нельзя использовать объятия. Это игрушка только для обучения.

GHC, однако, является быстрым многоядерным оптимизирующим компилятором для Haskell. Получить здесь. В частности, он выполняет анализ строгости и компилирует собственный код.

Главное, что выделяется в вашем коде, — это использование foldr в очень большом списке. Вероятно, вам нужен хвостовой рекурсивный цикл. Вот так:

import Data.List

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

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

Вот сумма первых 400 000 четных выдумок, чтобы сэкономить вам время. (21с). :-)

person Don Stewart    schedule 10.04.2009
comment
Я использовал объятия, потому что время запуска GHC ужасно, но спасибо. Оказывается, я неправильно понял проблему, но спасибо за предложения - person Gabe Moothart; 10.04.2009
comment
Быстрый компилятор, генерирующий оптимальный код, не компенсирует непонимание проблемы, что и произошло здесь. Вы должны быть в состоянии решить это с ручкой и листом бумаги. - person MarkusQ; 11.04.2009
comment
Re: Время запуска GHC: вам не нужно перезапускать GHCi, просто введите :r и он перезагрузит текущий файл с диска. - person nominolo; 11.04.2009

arrow_upward
4
arrow_downward

Вы неправильно поняли задачу. актуальная задача требует, чтобы вы просуммировали все четные числа Фибоначчи так, чтобы число Фибоначчи само число не превышает 4 миллионов (это только первые 33 числа Фибоначчи).

person newacct    schedule 10.04.2009

arrow_upward
3
arrow_downward

Вы оцениваете четыре миллиона элементов fibs. Эти цифры растут в геометрической прогрессии. Я не знаю, сколько байтов требуется для представления миллионного числа Фибоначчи; только тысячное число Фибоначчи имеет 211 десятичных цифр, поэтому для хранения цифр потребуется 22 32-битных слова, не говоря уже о том, какие накладные расходы gmp накладываются. И эти растут в геометрической прогрессии.

Упражнение: рассчитайте объем памяти, необходимый для хранения четырех миллионов чисел Фибоначчи.

person Norman Ramsey    schedule 10.04.2009

arrow_upward
2
arrow_downward

взгляните на функции Prelude takeWhile, filter, even и sum

takeWhile (‹40) [0..]
фильтровать даже $ takeWhile (‹40) [0..]

сложите их вместе:

ans = sum $ filter even $ takeWhile (‹ 4* 10^6) fibs

person ja.    schedule 11.04.2009