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

Question

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

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.

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

Answer 1

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

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]]

Answer 2

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

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 оно работает. Что я делаю из этого? Я не знаю:(Эти космические загадки - серьезная ошибка.

Редактировать:

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

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

maximum' = foldl1' max

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

Answer 3

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

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

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

Answer 4

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

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