Algoritmo online lineare di Haskell

Question

Per favore perdonami se ho abusato delle parole grosse nel titolo; Non sono troppo informato su di loro ma spero che descrivano il mio problema. Ho scritto uno schema elaborato per provare e codificare le stringhe in base ai requisiti these. Per le stringhe di lunghezza 10^4 e superiori, il codice che ho scritto è piuttosto lento, e mi chiedo - dal momento che elabora blocchi di 200 alla volta (anche se si muove un solo carattere in avanti a volte per prendere il pezzo successivo), potrebbe essere modificato per produrre il risultato più velocemente o in modo più lineare (ad esempio, emettere immediatamente il risultato per ogni 200 caratteri elaborati). Sarebbe gradito qualsiasi aiuto con quella o altre ottimizzazioni evidenti.

Per suggerimento di tel, ho semplificato il mio esempio:

encode xs = encode' xs [] where 
    encode' []  result = result 
    encode' (z:zs) result 
    | null test = encode' zs (result ++ [z]) 
    | otherwise = encode' (drop numZsProcessed zs) (result ++ processed) 
    where test = ..some test 
     toProcess = take 200 (z:zs) 
     processed = ..do something complicated with toProcess 
     numZsProcessed = ..number of z's processed 

Answer 1

Haskell e ricorsione in coda non vanno d'accordo così come altri linguaggi funzionali e ricorsione in coda. Facciamo qualche riduzione manuale su un codice molto semplice per vedere cosa sta succedendo con la ricorsione della coda. Ecco un'implementazione coda-ricorsiva di map (1+).

go [] r = r 
go (x:xs) r = go xs (r ++ [1+x]) 

Inoltre dobbiamo tenere a mente la definizione di (++):

[] ++ ys = ys 
(x:xs) ++ ys = x : (xs ++ ys) 

Ora cerchiamo di ridurre go [1,2,3,4,5] []. Ricordare che [x,y,z] è notazione per x:(y:(z:[])) o in breve x:y:z:[].

go [1,2,3,4,5] [] 
go [2,3,4,5] ([] ++ [2]) -- 2 here is actually the thunk 1+1, but 
          -- for compactness I am reducing earlier 
go [3,4,5] (([] ++ [2]) ++ [3]) 
go [4,5] ((([] ++ [2]) ++ [3]) ++ [4]) 
go [5] (((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) 
go [] ((((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6]) 
(((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6] 
((([2] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
(((2:([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
((2:(([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
(2:((([] ++ [3]) ++ [4]) ++ [5]) ++ [6] 
2:(((([] ++ [3]) ++ [4]) ++ [5]) ++ [6]) -- first observable output 
2:((([3] ++ [4]) ++ [5]) ++ [6]) 
2:((3:([] ++ [4]) ++ [5]) ++ [6]) 
2:(3:(([] ++ [4]) ++ [5]) ++ [6]) 
2:3:((([] ++ [4]) ++ [5]) ++ [6])   -- second observable output 
2:3:(([4] ++ [5]) ++ [6]) 
2:3:(4:([] ++ [5]) ++ [6]) 
2:3:4:(([] ++ [5]) ++ [6])     -- third observable output 
2:3:4:([5] ++ [6]) 
2:3:4:5:([] ++ [6])       -- fourth observable output 
2:3:4:5:6:[]        -- final output 

Vedere come ogni elemento dell'output deve funzionare verso l'esterno da una serie di parentesi profondamente annidata? Questo fa sì che si prenda un tempo quadratico nella dimensione dell'input per ottenere tutto l'output. Vedrai anche un comportamento secondo il quale i primi elementi vengono ceduti lentamente e diventa sempre più veloce man mano che raggiungi la fine dell'elenco. Questa riduzione lo spiega.

Il problema di prestazioni principale qui è accodare il nuovo elemento alla fine della lista, che richiede tempo proporzionale alla dimensione della lista che si sta accedendo. Un modo migliore è di contro sul fronte, che è una operazione con tant-time. Questo farà sì che l'output risulti invertito, quindi è necessario invertire il risultato.

go [] r = reverse r 
go (x:xs) r = go xs ((1+x):r) 

reverse xs = rev xs []  -- roughly from the report prelude 
rev [] r = r 
rev (x:xs) r = rev xs (x:r) 

E, cerchiamo di ridurre:

go [1,2,3,4,5] [] 
go [2,3,4,5] [2] 
go [3,4,5] [3,2] 
go [4,5] [4,3,2] 
go [5] [5,4,3,2] 
go [] [6,5,4,3,2] 
reverse [6,5,4,3,2] 
rev [6,5,4,3,2] [] 
rev [5,4,3,2] [6] 
rev [4,3,2] [5,6] 
rev [3,2] [4,5,6] 
rev [2] [3,4,5,6] 
rev [] [2,3,4,5,6] 
[2,3,4,5,6]   -- first and all observable output! 

Quindi questo è chiaramente meno lavoro rispetto alla prima versione. Questo è lo stile utilizzato in linguaggi rigorosi come Scheme e ML, perché ha buone prestazioni di memoria. Tuttavia, presenta alcuni svantaggi:

• Tutto l'input deve essere consumato prima che qualsiasi uscita possa essere prodotta. In effetti l'intero calcolo viene eseguito prima che vengano prodotti risultati.
• Per questo motivo, non produce mai alcun output quando viene fornito un elenco infinito.
• Si tratta di reverse, che richiede un tempo aggiuntivo O(n) e non ha nulla a che fare con ciò che stiamo facendo (cosa ha a che fare l'inversione con l'aggiunta di un elemento a ogni elemento e la conservazione dell'ordine?).

In un linguaggio pigro come Haskell, possiamo fare meglio. Stranamente, e magnificamente, il modo in cui lo facciamo è scrivendolo in modo ancora più ingenuo.

go [] = [] 
go (x:xs) = (1+x):go xs 

e ridurre:

go [1,2,3,4,5] 
2:(go [2,3,4,5])  -- first observable output 
2:3:(go [3,4,5])  -- second observable output 
2:3:4:(go [4,5])  -- third observable output 
2:3:4:5:(go [6])  -- fourth observable output 
2:3:4:5:6:(go []) -- fifth observable output 
2:3:4:5:6:[]   -- final output 

persino richiede meno lavoro, e si inizia con produzione prima anche guardando il resto della lista, quindi ha buone prestazioni in un calcolo stream e funziona su input infiniti. E l'implementazione è tanto semplice e ovvia quanto puoi sperare.

Spero che questo ti dia qualche intuizione su come funziona la ricorsione della coda in Haskell. Per il tuo esempio, ti suggerisco di rimuovere la ricorsione della coda e riscriverla in uno stile naif simile al nostro go finale, usando l'intuizione che spero di aver suggerito da questo post di produrre "il più grande prefisso dell'input possibile, il prima possibile" (nota che restituire x:xs restituisce immediatamente x, anche se c'è ancora un po 'di lavoro da fare per calcolare xs - che è la pigrizia in (non-) azione).