Скрипту на Haskell не хватает места - PullRequest
Новая
       20

Скрипту на Haskell не хватает места

2 голосов
/ 10 апреля 2009

Я использую проект 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.

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

Ответы [ 5 ]

8 голосов
/ 10 апреля 2009

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

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 тыс. Даже фибсов , чтобы сэкономить вам время (21сек). : -)

6 голосов
/ 10 апреля 2009

Количество наблюдений / подсказок:

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

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

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

  • Сколько четных выдумок у вас может быть подряд?
  • Как долго вы можете без четкой выдумки?
  • Если вы суммируете все четные и нечетные (сделайте это вручную), что вы заметите в суммах?
4 голосов
/ 10 апреля 2009

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

3 голосов
/ 10 апреля 2009

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

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

2 голосов
/ 11 апреля 2009

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

takeWhile (<40) [0 ..] <br> фильтровать даже $ takeWhile (<40) [0 ..] </p>

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

ans = sum $ filter даже $ takeWhile (<4 * 10 ^ 6) fibs </p>

...