Переполнение пространства на Хаскеле - PullRequest
Новая
       12

Переполнение пространства на Хаскеле

9 голосов
/ 21 августа 2011

Я скомпилировал эту программу и пытаюсь ее запустить. 

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Int -> Int
collatzLength = Memo.arrayRange (1, 1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ maximumBy (comparing fst) $ [(collatzLength n, n) | n <- [1..1000000]]

Я получаю следующее от GHC 

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

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

Ответы [ 4 ]

11 голосов
/ 22 августа 2011

Как автор рассматриваемого кода, я теперь немного смущен, потому что у него есть не одна, а две возможные ошибки переполнения стека.

  1. Используется Int. В 32-битной системе это будет переполнено, поскольку последовательность Коллатца может быть немного выше, чем начальное число. Это переполнение может вызвать бесконечную рекурсию, когда функция перемещается назад и вперед между отрицательными и положительными значениями.

    В случае чисел от одного до миллиона худшая отправная точка - 704511, которая достигает 56 991 483 520, а затем возвращается к 1. Это далеко за пределы 32-битного диапазона.

  2. Используется maximumBy. Эта функция не является строгой, поэтому она будет вызывать переполнение стека при использовании в длинных списках. Одного миллиона элементов более чем достаточно, чтобы это произошло с размером стека по умолчанию. Однако он по-прежнему работает с включенными оптимизациями из-за анализа строгости, выполненного GHC.

    Решение - использовать строгую версию. Поскольку ни одна из них не доступна в стандартных библиотеках, мы можем использовать строгую левую складку сами.

Вот обновленная версия, которая (надеюсь) должна быть без переполнения стека, даже без оптимизации. 

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]
7 голосов
/ 22 августа 2011

Вот более короткая программа, которая завершается таким же образом: 

main = print (maximum [0..1000000])

Да. 

$ ghc --make harmless.hs && ./harmless
[1 of 1] Compiling Main             ( harmless.hs, harmless.o )
Linking harmless ...
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

С -O2 это работает. Что я делаю из этого? Я не знаю :( Эти космические загадки - серьезная ошибка.

Edit:

Спасибо Хаммару за указание на виновника.

Изменение вашей программы на использование 

maximum' = foldl1' max

Заставляет работать без -O2. Реализация Prelude maximum ленива и поэтому не работает для длинных списков без волшебной пыли компилятора.

6 голосов
/ 22 августа 2011

Я думаю, что наиболее вероятно, что вы нажмете целочисленное переполнение с некоторыми последовательностями Коллатца, а затем окажетесь в «искусственном» цикле, который содержит переполнения, но никогда не достигнет 1. Это приведет к бесконечной рекурсии.

Помните, что некоторые последовательности Коллатца становятся намного больше, чем их начальное число, прежде чем они окончательно (?) Получат значение 1.

Попробуйте посмотреть, исправит ли ваша проблема использование Integer вместо Int.

4 голосов
/ 22 августа 2011

Используйте оптимизатор (через флаг -O2) в любое время, когда вы беспокоитесь о производительности. Оптимизация GHC чрезвычайно важна не только для выполнения, но и для использования в стеке. Я протестировал это с GHC 7.2 и оптимизация позаботилась о вашей проблеме.

РЕДАКТИРОВАТЬ: Кроме того, если вы используете 32-битную машину, обязательно используйте Int64 или Word64. Вы переполните размер 32-битного целого и в противном случае вызовете прерывание (спасибо Хеннингу за это, просим ответить на него).

...