Immutable Dictionary overhead?

Question

Lorsque vous utilisez des dictionnaires non modifiables dans F #, combien de temps système y a-t-il lorsque vous ajoutez/supprimez des entrées? Traitera-t-il des seaux entiers comme immuables et les clonera-t-il et ne recréera-t-il que le seau dont l'article a changé?

Même si tel est le cas, il semble que il y a beaucoup de copie qui doit être fait afin de créer le nouveau dictionnaire (?)

Answer 1

J'ai regardé la mise en œuvre du type F # Map<K,V> et je pense qu'il est implémenté comme functional AVL tree. Il stocke les valeurs dans les nœuds internes de l'arbre ainsi que dans les feuilles et pour chaque nœud, il s'assure que | hauteur (gauche) - hauteur (droite) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

Je pense que les deux complexité moyenne et les plus défavorables sont O(log(n)):

• Insérer nous avons besoin de cloner tous les nœuds sur le chemin de la racine à l'élément nouvellement inséré et la la hauteur de l'arbre est au maximum O(log(n)). Sur le « retour », l'arbre peut avoir besoin de rééquilibrer chaque nœud, mais c'est aussi que O(log(n))

• Remove est similaire - on trouve l'élément, puis cloner tous les nœuds de la racine à cet élément (nœuds de rééquilibrage sur le chemin du retour à la racine)

Notez que d'autres structures de données qui ne ont pas besoin de rééquilibrer tous les nœuds de la racine à l'actuel lors de l'insertion/suppression ne sera pas vraiment utile dans l'immuable scénario, car vous devez créer de nouveaux nœuds pour le chemin entier de toute façon.

Answer 2

Beaucoup de la structure de l'arbre peut être réutilisé. Je ne connais pas la complexité algorithmique, je dirais qu'en moyenne, il n'y a que comme une «perte» logNumérée ...

Pourquoi ne pas essayer d'écrire un programme sur mesure? (Nous verrons si je peux motiver ce soir pour essayer moi-même.)

EDIT

Ok, voici quelque chose que je piraté. Je n'ai pas décidé s'il y a des données utiles ici ou non.

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 

Quand je lance cela dans ma boîte sur FSI, je reçois

--> 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 

qui suggère la mémoire peut être mise à l'échelle super-linéaire mais pas trop mal. Je présume que les collections gen0 sont à peu près une bonne approximation du «gaspillage» du rééquilibrage de l'arbre. Mais il est tard donc je ne suis pas sûr si j'ai assez bien réfléchi. :)