Perdita di spazio nel programma di elenco

Question

Sto risolvendo alcuni problemi di Project Euler in Haskell. Ho scritto un programma per un indovinello e non ha funzionato come mi aspettavo.

Quando ho controllato il task manager durante l'esecuzione del programma, ho visto che stava usando> 1 gigabyte di RAM su ghc. Un mio amico ha scritto un programma con lo stesso significato in Java ed è riuscito in 7 secondi.

import Data.List 

opl = find vw $ map (\x-> fromDigits (x++[0,0,9])) 
     $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re] 

vw x = hh^2 == x 
    where hh = (round.sqrt.fromIntegral) x 

re = [0..9] 

fromDigits x = foldl1 (\n m->10*n+m) x 

So che questo programma sarebbe uscita il numero che voglio dato abbastanza RAM e il tempo, ma ci deve essere un modo migliore prestazioni.

Answer 1

Il problema principale qui è che la sequenza ha una perdita di spazio. È definito così:

sequence [] = [[]] 
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ] 

quindi il problema è che la lista prodotta dalla chiamata ricorsiva sequence xss viene riutilizzata per ciascuno degli elementi di xs, quindi non può essere scartato fino alla fine. Una versione senza perdite di spazio è

myseq :: [[a]] -> [[a]] 
myseq xs = go (reverse xs) [] 
where 
    go [] acc = [acc] 
    go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ] 

PS. la risposta sembra essere Just 1229314359627783009

Modifica versione evitando il concat:

seqlists :: [[a]] -> [[a]] 
seqlists xss = go (reverse xss) [] [] 
where 
    go []  acc rest = acc : rest 
    go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs 

nota che entrambe queste versioni generare i risultati in un ordine diverso dallo standard sequence, così mentre lavorano per questo problema non possiamo usarne una come versione specializzata di sequence.

Answer 2

EDIT: Penso di essermi sbagliato qui - cambiare il tipo di firma in :: Forse Word64 (che sarebbe abbastanza bit per questo problema credo) richiede anche per sempre/ha una perdita di spazio, quindi non potrebbe essere il vecchio bug Integer.

Il tuo problema sembra essere un vecchio bug di GHC (che pensavo fosse corretto) con Integer che causava una perdita di spazio. Il codice seguente termina in circa 150 ms quando compilato con -O2.

import Data.List 
import Data.Word 

main = print opl 

opl :: Maybe Word32 
opl = find vw $ map (\x-> fromDigits (x++[0,0,9])) $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re] 

vw x = hh^2 == x 
    where hh = (round.sqrt.fromIntegral) x 

re = [0..9] 

fromDigits x = foldl1 (\n m->10*n+m) x 

Answer 3

Visto che siete alla ricerca di un numero diciannove cifre con quelle caratteristiche si trovano in VW, mi piacerebbe provare a semplificare la costruzione della funzione mappato solo dire fromDigits x*1000+9 per cominciare. L'aggiunta ad una lista è O (lunghezza della lista di sinistra), quindi lanciare le ultime tre cifre alla fine fa male al tempo di calcolo.

Come una parte (per entrambi), l'uso della versione rigida della piega (foldl1') aiuterà anche.

Answer 4

In seguito alla risposta di Simon Marlow, ecco una versione di sequenza che evita la perdita di spazio mentre altrimenti funziona esattamente come l'originale, inclusa la conservazione dell'ordine.

Utilizza ancora la semplice e semplice lista di comprensione della sequenza originale - l'unica differenza è che viene introdotta una dipendenza di dati falsi che impedisce la condivisione della chiamata ricorsiva.

sequenceDummy d [] = d `seq` [[]] 
sequenceDummy _ (xs:xss) = [ y:ys | y <- xs, ys <- sequenceDummy (Just y) xss ] 

sequenceUnshared = sequenceDummy Nothing 

Penso che questo sia un modo migliore per evitare la condivisione che porta alla perdita di spazio.

Incolperei la condivisione eccessiva della trasformazione della "pigrizia totale". Normalmente questo è un ottimo lavoro di creazione di condivisione che evita le ricompense, ma a volte la ricompilazione è molto più efficiente di memorizzare i risultati condivisi.

Sarebbe bello se ci fosse un modo più diretto per dire al compilatore di non condividere un'espressione specifica - il suddetto argomento fittizio Maybe funziona ed è efficiente, ma è fondamentalmente un hack che è semplicemente abbastanza complicato che ghc puo ' Dire che non c'è una reale dipendenza. (In un linguaggio rigoroso non hai questi problemi perché hai solo condivisione dove leghi esplicitamente una variabile a un valore.)