Un'altra domanda da Haskell n00b.Haskell: Lista v. Array, differenza di prestazioni
Sto confrontando l'efficienza dei vari metodi utilizzati per risolvere il Problema n. 14 sul sito Web di Project Euler. In particolare, spero di capire meglio i fattori che guidano la differenza nel tempo di valutazione per quattro approcci (leggermente) diversi per risolvere il problema.
(descrizioni di problema # 14 e vari approcci sono al di sotto.)
In primo luogo, una rapida panoramica Problema # 14. Ha a che fare con "numeri di Collatz" (cioè, stesso esercizio di programmazione del mio post precedente che ha esplorato un aspetto diverso di Haskell). Un numero di Collatz per un dato intero è uguale alla lunghezza della sequenza di Collatz per quell'intero. Una sequenza di Collatz per un intero è calcolata come segue: il primo numero ("n0") nella sequenza è quello intero stesso; se n0 è pari, il numero successivo nella sequenza ("n1") è uguale a n/2; se n0 è dispari, allora n1 è uguale a 3 * n0 + 1. Continuiamo ad estendere ricorsivamente la sequenza finché non arriviamo a 1, momento in cui la sequenza è finita. Ad esempio, la sequenza collatz per 5 è: {5, 16, 8, 4, 2, 1} (perché 16 = 3 * 5 + 1, 8 = 16/2, 4 = 8/2, ...).
Problema 14 ci chiede di trovare il numero intero inferiore a 1.000.000 che ha il numero di Collatz più grande. A tal fine, possiamo considerare una funzione "collatz" che, quando passa un intero "n" come argomento, restituisce il numero intero sotto n con il numero di Collatz più grande. In altre parole, p 1000000 ci dà la risposta al Problema # 14.
Ai fini di questo esercizio (cioè, capire le differenze di tempo di valutazione), possiamo considerare le versioni Haskell di 'Collatz' che variano tra due dimensioni:
(1) Attuazione: Dobbiamo memorizzare il set di dati di Numeri di Collatz (che verranno generati per tutti gli interi 1..n) come elenco o array? Io chiamo questa dimensione di "implementazione", cioè l'implementazione di una funzione è "lista" o "matrice".
(2) Algoritmo: calcoliamo il numero di Collatz per ogni intero dato n estendendo la sequenza di Collatz fino a quando non è completa (vale a dire, finché non raggiungiamo 1)? Oppure estendiamo la sequenza solo fino a raggiungere un numero k che è più piccolo di n (a questo punto possiamo semplicemente usare il numero di collatz di k, che abbiamo già calcolato)? Io chiamo questa dimensione "algoritmo", cioè, l'algoritmo di una funzione è "completo" (calcolo del numero di Collatz per ogni intero) o "parziale". Quest'ultimo ovviamente richiede meno operazioni.
Questi sono i quattro possibili versioni della funzione "Collatz": allineamento/parziale lista/parziale, matrice/complete e lista/complete:
import Data.Array ((!) , listArray , assocs)
import Data.Ord (comparing)
import Data.List (maximumBy)
--array implementation; partial algorithm (FEWEST OPERATIONS)
collatzAP x = maximumBy (comparing snd) $ assocs a where
a = listArray (0,x) (0:1:[c n n | n <- [2..x]])
c n i = let z = if even i then div i 2 else 3*i+1
in if i < n then a ! i else 1 + c n z
--list implementation; partial algorithm
collatzLP x = maximum a where
a = zip (0:1:[c n n | n <- [2..x]]) [0..x]
c n i = let z = if even i then div i 2 else 3*i+1
in if i < n then fst (a!!i) else 1 + c n z
--array implementation, complete algorithm
collatzAC x = maximumBy (comparing snd) $ assocs a where
a = listArray (0,x) (0:1:[c n n | n <- [2..x]])
c n i = let z = if even i then div i 2 else 3*i+1
in if i == 1 then 1 else 1 + c n z
--list implementation, complete algorithm (MOST OPERATIONS)
collatzLC x = maximum a where
a = zip (0:1:[c n n | n <- [2..x]]) [0..x]
c n i = let z = if even i then div i 2 else 3*i+1
in if i == 1 then 1 else 1 + c n z
riguardanti la velocità di valutazione: So che gli array sono molto più veloce di accesso rispetto agli elenchi (cioè, O (1) contro O (n) tempo di accesso per un dato indice n) quindi mi aspettavo che l'implementazione "array" di "collatz" fosse più veloce dell'implementazione di "lista", ceteris paribus. Inoltre, mi aspettavo che l'algoritmo "parziale" fosse più veloce dell'algoritmo "completo" (ceteris paribus), dato che ha bisogno di eseguire meno operazioni per costruire il set di dati dei numeri di Collatz.
Testare i nostri quattro funzioni attraverso ingressi di dimensioni diverse, si osserva i seguenti orari di valutazione (commenti qui sotto):
E 'infatti il caso che la versione 'allineamento/parziale' è la versione più veloce di "collatz" (con un buon margine).Tuttavia, trovo un po 'controintuitivo che "list/complete" non sia la versione più lenta. Questo onore va a "lista/parziale", che è più di 20 volte più lento di "elenco/completo"!
La mia domanda: è la differenza nel tempo di valutazione tra "elenco/parziale" e "elenco/completo" (rispetto a quello tra "array/partial" e "array/complete") interamente dovuto alla differenza di accesso efficienza tra liste e array in Haskell? Oppure non sto facendo un "esperimento controllato" (cioè, ci sono altri fattori in gioco)?
Senza fare alcuna analisi, sospetto fortemente che "elenco/parziale" sia lento interamente a causa dell'inefficienza dell'indicizzazione. –