Haskell Stack Overflow

Question

Estoy escribiendo un algoritmo genético para generar la cadena "helloworld". Pero la función evolucionar crea un desbordamiento de pila cuando n es 10.000 o más.

module Genetics where 

import Data.List (sortBy) 
import Random (randomRIO) 
import Control.Monad (foldM) 

class Gene g where 
    -- How ideal is the gene from 0.0 to 1.0? 
    fitness :: g -> Float 

    -- How does a gene mutate? 
    mutate :: g -> IO g 

    -- How many species will be explored? 
    species :: [g] -> Int 

orderFitness :: (Gene g) => [g] -> [g] 
orderFitness = reverse . sortBy (\a b -> compare (fitness a) (fitness b)) 

compete :: (Gene g) => [g] -> IO [g] 
compete pool = do 
    let s = species pool 
    variants <- (mapM (mapM mutate) . map (replicate s)) pool 
    let pool' = (map head . map orderFitness) variants 
    return pool' 

evolve :: (Gene g) => Int -> [g] -> IO [g] 
evolve 0 pool = return pool 
evolve n pool = do 
    pool' <- compete pool 
    evolve (n - 1) pool' 

Con species pool = 8, un grupo de 8 genes se replica en 8 grupos. Cada grupo muta, y el más apto de cada grupo se selecciona para una mayor evolución (de vuelta a 8 genes).

GitHub

Answer 1

Gracias a la sugerencia de Don deepseq, pude reducir el problema a mapM mutate que hizo demasiados thunks. La nueva versión tiene mutate', que usa seq para evitar el "thunk".

module Genetics where 

import Data.List (maximumBy) 
import Random (randomRIO) 

class Gene g where 
    -- How ideal is the gene from 0.0 to 1.0? 
    fitness :: g -> Float 

    -- How does a gene mutate? 
    mutate :: g -> IO g 

    -- How many species will be explored in each round? 
    species :: [g] -> Int 

best :: (Gene g) => [g] -> g 
best = maximumBy (\a b -> compare (fitness a) (fitness b)) 

-- Prevents stack overflow 
mutate' :: (Gene g) => g -> IO g 
mutate' gene = do 
    gene' <- mutate gene 
    gene' `seq` return gene' 

drift :: (Gene g) => [[g]] -> IO [[g]] 
drift = mapM (mapM mutate') 

compete :: (Gene g) => [g] -> IO [g] 
compete pool = do 
    let islands = map (replicate (species pool)) pool 
    islands' <- drift islands 
    let representatives = map best islands' 
    return representatives 

evolve :: (Gene g) => Int -> [g] -> IO [g] 
evolve 0 pool = return pool 
evolve n pool = compete pool >>= evolve (n - 1) 

GitHub

Answer 2

Si usted está interesado en el rendimiento, que haría uso de un generador de números aleatorio rápido, tales como:

• The mersenne-random package

En segundo lugar, compete parece muy sospechoso, ya que es completamente vago, a pesar de construir algunas estructuras potencialmente grandes. Intente volver a escribir que sea un poco más estricta, usando el martillo deepseq:

import Control.DeepSeq  

compete :: (Gene g, NFData g) => [g] -> IO [g] 
compete pool = do 
    let s = species pool 
    variants <- (mapM (mapM mutate) . map (replicate s)) pool 
    let pool' = (map head . map orderFitness) variants 
    pool' `deepseq` return pool' 

Ninguna de estas cosas tiene que estar en IO, sin embargo, (tema aparte). Algo así como la mónada Rand puede ser more appropriate.

Answer 3

En lugar de utilizar (map head . map orderFitness) donde orderFitness es una sortBy podría utilizar maximumBy y una sola map. Eso no ahorra demasiado (ya que se pasa de O (n log n) a O (n) y podría estar obteniendo otro factor de dos al eliminar el mapa doble), pero es al menos algo más simple y más eficiente . También eliminaría una llamada para revertir.

Dudo que esto solucione el problema sin un deepseq, pero debería ser una mejora sin embargo.

Editar: si la biblioteca estándar y GHC eran perfectos, entonces head . sortBy produciría código idéntico al maximumBy y map head . map sortBy produciría código idéntico al map (head . sortBy) lamentablemente ninguna de estas cosas es probable que sea cierto en la práctica. sortBy tenderá a hacer un montón de asignación de memoria adicional porque es un algoritmo de dividir y conquistar. La combinación de mapas es una optimización que a veces obtienes, pero que no debes contar.

Más importante aún, usar maximumBy es más declarativo. Es más fácil ver qué hace el código y cuánto tiempo llevará. También debería ser más fácil aprovechar optimizaciones, porque sabemos cuál es el objetivo, no solo cómo lo conseguimos.