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

StackOverflow https://stackoverflow.com/questions/736495

  •  09-09-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

Ряд наблюдений/подсказок:

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

Редактировать в ответ на комментарий

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

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

Другие советы

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

Однако 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 с).:-)

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

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

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

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

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

соедините их вместе:

ans = sum $ filter Even $ takeWhile (< 4* 10^6) фибс

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top