¿Sobrecarga del diccionario inmutable?

Question

Al usar diccionarios inmutables en F #, ¿cuánta sobrecarga hay al agregar/eliminar entradas?

¿Tratará los cubos enteros como inmutables y los clonará y solo recreará el cubo cuyo elemento ha cambiado?

Incluso si ese es el caso, parece que hay un montón de copia que hay que hacer con el fin de crear el nuevo diccionario (?)

Answer 1

Miré la implementación del tipo F # Map<K,V> y creo que se implementa como functional AVL tree. Almacena los valores en los nodos internos del árbol así como en las hojas y para cada nodo, se asegura de que | altura (izquierda) - altura (derecha) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

creo que los dos complejidad media y peor de los casos son O(log(n)):

• Insertar tenemos que clonar todos los nodos en el camino desde la raíz hasta el elemento y el recién insertado la altura del árbol es como máximo O(log(n)). En el "camino de vuelta", el árbol puede ser necesario volver a equilibrar cada nodo, pero eso es también única O(log(n))

• Eliminar es similar - nos encontramos con el elemento y luego clonar todos los nodos de la raíz a ese elemento (nodos de reequilibrio en el camino de regreso a la raíz)

Tenga en cuenta que otras estructuras de datos que no necesitan volver a equilibrar todos los nodos de la raíz a la actual en la inserción/deleción no va a ser muy útil en el inmutable escenario, porque necesita crear nuevos nodos para toda la ruta de todos modos.

Answer 2

Una gran parte de la estructura de árbol puede ser reutilizado. No sé la complejidad algorítmica al azar, supongo que en promedio solo hay como 'desperdicio' de logN amortizado ...

¿Por qué no intentar escribir un programa para medir? (Veremos si puedo conseguir motivado esta noche para probar en mi misma.)

EDITAR

autorización, aquí es algo que han pirateado. No he decidido si hay datos útiles aquí 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 

Cuando ejecuto esto en FSI en mi caja, me sale

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

lo que sugiere la memoria puede estar escalando super-linealmente pero no demasiado mal. Supongo que las colecciones gen0 son aproximadamente un buen sustituto del "desperdicio" de reequilibrar el árbol. Pero es tarde, así que no estoy seguro si he pensado bien sobre esto. :)