Unverwechselbare Wörterbuch-Overhead?

Question

Wenn Sie in F # unveränderbare Wörterbücher verwenden, wie hoch ist der Aufwand beim Hinzufügen/Entfernen von Einträgen?

Wird es ganze Eimer als unveränderlich behandeln und diese klonen und nur den Eimer neu erstellen, dessen Gegenstand sich geändert hat?

Selbst wenn dies der Fall ist, so scheint es, als gäbe es eine Menge Kopieren ist, die getan werden muss, um das neue Wörterbuch erstellen (?)

Answer 1

Ich schaute auf die Implementierung der F # Map<K,V> Art und ich denke, dass es als functional AVL tree implementiert ist. Er speichert die Werte sowohl in den inneren Knoten des Baums als auch in den Blättern und stellt für jeden Knoten sicher, dass | Höhe (links) - Höhe (rechts) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

denke ich, dass die beiden mittleren und Worst-Case-Komplexität sind O(log(n)):

• Insert wir alle Knoten auf dem Pfad von der Wurzel zu dem neu eingefügten Element klonen müssen und die Die Höhe des Baumes ist höchstens O(log(n)). Auf dem „Rückweg“, kann der Baum jeden Knoten neu zu gewichten müssen, aber das ist auch nur O(log(n))

• entfernen ist ähnlich - wir das Element und dann klonen alle Knoten von der Wurzel zu diesem Element (Rebalancing Knoten finden auf dem Weg zur Wurzel zurück)

Beachten Sie, dass andere Datenstrukturen, die wirklich nützlich sein, nicht alle Knoten von der Wurzel zu dem aktuellen Neuverteilung müssen nicht in den unveränderlichen auf Einfügen/Löschen werden Szenario, weil Sie sowieso neue Knoten für den gesamten Pfad erstellen müssen.

Answer 2

Viele der Baumstruktur wiederverwendet werden kann. Ich kenne die algorithmische Komplexität nicht auswendig, ich würde im Durchschnitt sagen, dass es nur amortisierten logN 'Verschwendung' gibt ...

Warum nicht versuchen, ein Programm zu messen? (Wir werden sehen, ob ich heute Abend motiviert kann es selbst zu versuchen.)

EDIT

Ok, hier ist etwas, das ich gehackt. Ich habe nicht entschieden, ob es hier nützliche Daten gibt oder nicht.

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 

Als ich dies in FSI laufen auf meiner Box, erhalte ich

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

, die der Speicher-linear Super, aber nicht zu schlecht kann die Skalierung vermuten lässt. Ich gehe davon aus, dass die gen0-Sammlungen in etwa ein guter Ersatz für die "Verschwendung" des Rebalancing des Baumes sind. Aber es ist spät, also bin ich mir nicht sicher, ob ich das gut genug durchdacht habe. :)