Overhead dizionario immutabile?

Question

Quando si utilizzano dizionari immutabili in F #, quanto sovraccarico c'è quando si aggiungono/rimuovono voci?

Tratterà i bucket interi come immutabili e li clonerà, ricreando solo il bucket di cui è stato modificato l'elemento?

Anche se questo è il caso, sembra che ci sia un sacco di copia che deve essere fatto al fine di creare il nuovo dizionario (?)

Answer 1

Ho esaminato l'implementazione del tipo F # Map<K,V> e penso che sia implementato come functional AVL tree. Memorizza i valori nei nodi interni dell'albero e nelle foglie e per ciascun nodo, assicura che | altezza (a sinistra) - altezza (a destra) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

Penso che entrambe le complessità media e nel peggiore dei casi sono O(log(n)):

• Inserire abbiamo bisogno di clonare tutti i nodi sul percorso dalla radice all'elemento appena inserito e la l'altezza dell'albero è al massimo O(log(n)). Sulla "via del ritorno", l'albero può essere necessario per riequilibrare ogni nodo, ma che è anche solo O(log(n))

• Rimuovere è simile - troviamo l'elemento e quindi copiare tutti i nodi dalla radice a quell'elemento (nodi di riequilibrio al ritorno alla radice)

noti che altri data-strutture che non hanno bisogno di riequilibrare tutti i nodi dalla radice a quella attuale all'inserimento/cancellazione non saranno molto utili nella immutabile scenario, perché è necessario creare nuovi nodi per l'intero percorso comunque.

Answer 2

Un sacco di struttura ad albero può essere riutilizzato. Non conosco la complessità algoritmica a priori, direi che in media c'è solo il logor ammortizzato 'spreco' ...

Perché non provare a scrivere un programma su misura? (Vedremo se riesco a stasera per provare io stesso motivati.)

EDIT

Ok, qui è qualcosa che ho violato. Non ho deciso se ci sono dati utili qui o no.

open System 

let rng = new Random() 
let shuffle (array : _[]) = 
    let n = array.Length 
    for x in 1..n do 
     let i = n-x 
     let j = rng.Next(i+1) 
     let tmp = array.[i] 
     array.[i] <- array.[j] 
     array.[j] <- tmp 

let TryTwoToThe k = 
    let N = pown 2 k 

    GC.Collect() 

    let a = Array.init N id 

    let makeRandomTreeAndDiscard() = 
     shuffle a 
     let mutable m = Map.empty 
     for i in 0..N-1 do 
      m <- m.Add(i,i) 

    for i in 1..20 do 
     makeRandomTreeAndDiscard() 
    for i in 1..20 do 
     makeRandomTreeAndDiscard() 
    for i in 1..20 do 
     makeRandomTreeAndDiscard() 

#time 
// run these as separate interactions 
printfn "16" 
TryTwoToThe 16 

printfn "17" 
TryTwoToThe 17 

printfn "18" 
TryTwoToThe 18 

Quando ho eseguito questo FSI sulla mia macchina, ottengo

--> Timing now on 

> 
16 
Real: 00:00:08.079, CPU: 00:00:08.062, GC gen0: 677, gen1: 30, gen2: 1 
> 
17 
Real: 00:00:17.144, CPU: 00:00:17.218, GC gen0: 1482, gen1: 47, gen2: 4 
> 
18 
Real: 00:00:37.790, CPU: 00:00:38.421, GC gen0: 3400, gen1: 1059, gen2: 17 

che suggerisce la memoria può essere scalando super-lineare, ma non troppo male. Presumo che le collezioni gen0 siano approssimativamente un buon proxy per lo "spreco" del riequilibrio dell'albero. Ma è tardi, quindi non sono sicuro di averlo pensato abbastanza bene. :)