Непрерывный словарь накладных расходов?

Question

При использовании неизменяемых словарей в F #, сколько накладных расходов при добавлении/удалении записей?

Будет ли он обрабатывать целые ведра как неизменные и клонировать их и только воссоздавать ведро, предмет которого изменился?

Даже если это так, похоже, есть много копирования, что должно быть сделано для того, чтобы создать новый словарь (?)

Answer 1

Я посмотрел на реализацию типа F # Map<K,V>, и я думаю, что он реализован как functional AVL tree. Он сохраняет значения во внутренних узлах дерева, а также в листах и ​​для каждого узла, он гарантирует, что | высота (слева) - высота (справа) | < = 1.

  A 
     / \ 
     B  C 
    / \ 
    D  E 

Я думаю, что оба средние и наихудшие сложности являются O(log(n)):

• Вставьте нам нужно клонировать все узлы на пути от корня к вновь вставленному элементу и высота дерева не более O(log(n)). На «обратный путь», дерево, возможно, потребуется, чтобы сбалансировать каждый узел, но это также только O(log(n))

• Удалить аналогично - мы находим элемент, а затем клонировать все узлы от корня к этому элементу (перебалансирования узлы на обратном пути к корню)

Следует отметить, что другие данные-структура, которые не требуют, чтобы сбалансировать все узлы, от корня до текущего при вставке/удаление не будет действительно полезной в неизменном сценарий, потому что вам все равно нужно создавать новые узлы для всего пути.

Answer 2

Много структуры дерева можно использовать повторно. Я не знаю алгоритмической сложности из рук в руки, я бы предположил, что в среднем есть только как амортизированный logN «отходы» ...

Почему бы не попытаться написать программу для измерения? (Мы увидим, если я могу получить мотивированный сегодня вечером, чтобы попробовать это сам.)

EDIT

Хорошо, вот что-то я взломал. Я не решил, есть ли какие-либо полезные данные здесь или нет.

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 

Когда я запускаю это в FSI на мой ящик, я получаю

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

который предполагает память может быть масштабирование супер-линейно, но не слишком сильно. Я предполагаю, что коллекции gen0 являются примерно хорошим прокси-сервером для «отходов» для балансировки дерева. Но уже поздно, поэтому я не уверен, подумал ли я об этом достаточно хорошо. :)