Lista prestazioni manipolazione in Haskell

Question

Attualmente sto imparando Haskell e io sono curioso di sapere quanto segue:

Se posso aggiungere un elemento a un elenco in Haskell, Haskell restituisce una nuova lista (? Completamente), e non lo fa manipolare quello originale.

Ora diciamo che ho una lista di un milione di elementi e aggiungo un elemento alla fine. Haskell "copia" l'intera lista (1 milione di elementi) e aggiunge l'elemento a quella copia? O c'è un bel "trucco" in corso dietro le quinte per evitare di copiare l'intera lista?

E se non c'è un "trucco", il processo di copia di elenchi di grandi dimensioni non è costoso come penso che sia?

Answer 1

Dipende dalla struttura dati che si sta utilizzando. Se utilizzi le normali liste Haskell, queste sarebbero analoghe a un'implementazione tipica delle liste collegate in C o C++. Con questa struttura, le aggiunte sono O (n) complessità, mentre le prepazioni sono O (1) complessità. Se si tenta di aggiungere un milione di elementi, sarà necessario il tempo O (500000500000) (O (1) + O (2) + O (3) + ... + O (1000000)) circa 500000500000 operazioni. Questo è indipendentemente dalla lingua che stai usando, Haskell, C, C++, Python, Java, C#, o persino Assembler.

Tuttavia, se si dovesse utilizzare una struttura come Data.Sequence.Seq, allora utilizza internamente la struttura appropriata per fornire O (1) prependi e appende, ma il costo è che può richiedere un po 'più di RAM. Tutte le strutture dati hanno dei compromessi, tuttavia, dipende da te quale si desidera utilizzare.

In alternativa, è anche possibile utilizzare Data.Vector.Vector o Data.Array.Array, che entrambi forniscono lunghezza fissa, matrici di memoria contigui, ma aggiungendo e prepending è costosa perché si deve copiare l'intero array in una nuova posizione nella RAM. L'indicizzazione è O (1), tuttavia, e la mappatura o il ripiegamento su una di queste strutture sarebbe molto più veloce perché i pezzi dell'array possono adattarsi alla cache della CPU alla volta, al contrario di elenchi o sequenze collegate che hanno elementi sparsi dappertutto la tua RAM.

Haskell "copia" l'intera lista (1 milione di elementi) e aggiunge l'elemento a quella copia?

Non necessariamente, il compilatore può determinare se è sicuro di avere solo il cambiamento next puntatore dell'ultimo valore al punto al nuovo valore anziché la lista vuota, o se è pericoloso, può essere necessario copiare l'intero elenco . Questi problemi sono tuttavia inerenti alla struttura dei dati, non alla lingua. In generale, direi che gli elenchi di Haskell sono migliori degli elenchi concatenati C perché il compilatore è più capace di analizzare quando questo è sicuro di quanto lo sia un programmatore, e il compilatore C non farà questo genere di analisi, semplicemente fanno esattamente come 'stato detto.

Answer 2

Quando si utilizzano le liste, l'aggiunta è costosa e l'elenco deve essere copiato, ma non gli elementi. Inoltre, il prepending è economico poiché il nuovo valore punta semplicemente sull'elenco originale.

Prendere l'accodamento "third" a ["first", "second"]: il nuovo elenco è (:) "first" ((:) "second" ((:) "third" [])). Pertanto, il primo costruttore deve essere uno nuovo poiché il secondo argomento deve essere un nuovo valore come ... Le stringhe non vengono duplicate. La nuova lista punta alle stesse stringhe in memoria.

Si noti che nel caso in cui il vecchio valore è scartato, il compilatore potrebbe decidere di riutilizzarlo invece di allocare memoria per nuovi valori e garbage collection di quelli vecchi. In ogni caso, l'aggiunta verrà eseguita in O (n) in quanto ha bisogno di trovare la fine di esso.

Ora se il tuo programma si aggiunge molto agli elenchi, potresti voler utilizzare una diversa struttura di dati per poter aggiungere in O (1) come DList il pacchetto dlist. (https://hackage.haskell.org/package/dlist-0.5/docs/Data-DList.html)

Answer 3

Questa è una domanda sorprendentemente complessa, a causa di due caratteristiche di Haskell e GHC:

1. valutazione pigra
2. Elenco fusione

Elenco fusione significa che in alcune situazioni, GHC può riscrivere il codice di elaborazione dell'elenco in un ciclo che non alloca le celle dell'elenco. Quindi, a seconda del contesto in cui viene utilizzato, lo stesso codice potrebbe non comportare costi aggiuntivi.

Valutazione pigra significa che se il risultato di un'operazione non viene consumato, non si paga il costo del calcolo. Così, per esempio, questo è a buon mercato, perché hai solo per costruire i primi dieci elementi della lista:

example = take 10 ([1..1000000] ++ [1000001]) 

Infatti, in quel codice l'take 10 possono fondersi con la lista di aggiunta, quindi è la stessa come solo [1..10].

Ma supponiamo solo che stiamo consumando tutti gli elementi di tutti gli elenchi che creiamo e che il compilatore non sta fondendo le operazioni delle liste. Ora alle vostre domande:

Se aggiungo un elemento a un elenco in Haskell, Haskell restituisce un (completamente?) Nuovo elenco e non manipola quello originale. Ora diciamo che ho un elenco di un milione di elementi e aggiungo un elemento alla fine. Haskell "copia" l'intera lista (1 milione di elementi) e aggiunge l'elemento a quella copia? O c'è un bel "trucco" in corso dietro le quinte per evitare di copiare l'intera lista?

Esistono trucchi per evitare di copiare l'intera lista, ma aggiungendoli alla fine li sconfiggi. La cosa da capire è che le strutture dati funzionali sono normalmente progettate in modo che le operazioni che le "modificano" sfruttino lo condivisione delle strutture per riutilizzare il più possibile la vecchia struttura. Così, per esempio, aggiungendo due liste può essere definita in questo modo:

(++) :: [a] -> [a] -> [a] 
[] ++ ys = ys 
(x:xs) ++ ys = x : xs ++ ys 

Guardando questa definizione, si può dire che l'elenco ys sarà riutilizzato nel risultato. Quindi, se abbiamo xs = [1..3], ys = [4..5] e xs ++ ys, tutte completamente valutato e mantenuto in memoria in una sola volta, che sarà simile a questa memoria-saggio:

  +---+---+ +---+---+ +---+---+ 
     xs = | 1 | -----> | 2 | -----> | 3 | -----> [] 
      +---+---+ +---+---+ +---+---+ 

      +---+---+ +---+---+ 
     ys = | 4 | -----> | 5 | -----> [] 
      +---+---+ +---+---+  
      ^
      | 
      +------------------------------------+ 
                | 
      +---+---+ +---+---+ +---+---+ | 
xs ++ ys = | 1 | -----> | 2 | -----> | 3 | -------+ 
      +---+---+ +---+---+ +---+---+ 

Questo è il lungo modo di dire questo: se si fa xs ++ ys , e non si fonde, e si consuma l'intera lista, quindi creerà una copia di xs ma riutilizzerà la memoria per ys.

Ma ora diamo un'occhiata di nuovo a questo pezzo della tua domanda:

Ora diciamo che ho una lista di un milione di elementi e aggiungo un elemento alla fine. Haskell "copia" l'intera lista (1 milione di elementi) e aggiunge l'elemento a quella copia?

Sarebbe qualcosa come [1..1000000] ++ [1000001] e sì, copierà l'intero milione di elementi. D'altra parte, [0] ++ [1..1000000] copierà solo lo [0]. La regola generale è questa:

• L'aggiunta di elementi all'inizio di un elenco è la più efficiente.
• L'aggiunta di elementi alla fine di un elenco è spesso inefficace, in particolare se lo si fa ripetutamente.

Le soluzioni generali a questo tipo di problema sono:

1. Modificare l'algoritmo in modo che si utilizzano gli elenchi in un modello di accesso che supportano in modo efficiente.
2. Non utilizzare elenchi; utilizzare un'altra struttura di dati di sequenza che supporti in modo efficiente il tipo di accesso necessario per il problema in questione. Un'altra risposta menzionato liste differenza, ma gli altri degni di nota sono:
   • Data.Sequence
   • Data.Set
   • Data.Vector