online - haskell pagina oficial

Haskell Space Overflow

Question

He compilado este programa y estoy tratando de ejecutarlo.

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

Obtengo lo siguiente de GHC

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

Supongo que esta es una de las cosas de "desbordamiento espacial" que he estado escuchando. (Soy bastante nuevo para Haskell.) ¿Cómo lo arreglo? ¿Tengo que volver a escribir collatzLength para que sea recursivo?

Answer 1

Aquí hay un programa más corto que falla de la misma manera:

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

Sí.

$ 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.

Con -O2 funciona. ¿Qué hago de eso? No lo sé :( Estos misterios espaciales son un problema serio.

Editar:

Thx a Hammar por señalar al culpable.

Cambiando su programa para usar

maximum'' = foldl1'' max

Lo hace funcionar sin -O2 . La implementación del maximum de Prelude es floja y, por lo tanto, no funciona para listas largas sin el polvo mágico del compilador.

Answer 2

Como autor del código en cuestión, ahora estoy un poco avergonzado porque no tiene uno sino dos posibles errores de desbordamiento de la pila.

1. Utiliza Int . En un sistema de 32 bits, esto se desbordará, ya que la secuencia de Collatz puede ir un poco más alta que el número inicial. Este desbordamiento puede causar recursión infinita a medida que la función salta hacia adelante y hacia atrás entre los valores negativos y positivos.

   En el caso de números entre uno y un millón, el peor punto de partida es 704511, que llega a 56.991.483.520 antes de volver a descender hacia 1. Esto está bien fuera del rango de 32 bits.

2. Utiliza maximumBy . Esta función no es estricta, por lo que causará un desbordamiento de pila cuando se usa en listas largas. Un millón de elementos es más que suficiente para que esto suceda con el tamaño de pila predeterminado. Todavía funciona con optimizaciones habilitadas, sin embargo, debido al análisis de rigurosidad realizado por GHC.

   La solución es usar una versión estricta. Como ninguno está disponible en las bibliotecas estándar, podemos usar el estricto doblado izquierdo nosotros mismos.

Aquí hay una versión actualizada que debería (con suerte) estar libre de desbordamiento de pila, incluso sin optimizaciones.

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 3

Creo que es más probable que estés golpeando el desbordamiento de enteros con algunas de las secuencias de Collatz, y luego terminando en un ciclo "artificial" que contiene desbordamientos pero nunca golpea 1. Eso produciría una recursión infinita.

Recuerde que algunas secuencias de Collatz son mucho más grandes que su número de inicio antes de que finalmente (?) Terminen en 1.

Intente ver si soluciona su problema para utilizar Integer lugar de Int .

Answer 4

Use el optimizador (a través del indicador -O2 ) cada vez que le preocupe el rendimiento. Las optimizaciones de GHC son muy importantes no solo para ejecutar el tiempo sino también para apilar. He probado esto con GHC 7.2 y la optimización se ocupa de su problema.

EDITAR: Además, si está en una máquina de 32 bits, asegúrese de usar Int64 o Word64 . Desbordará el tamaño de un int de 32 bits y provocará la no terminación de lo contrario (gracias a Henning por esto, votó positivamente su respuesta).