不可变字典的开销是什么？

Question

在使用不可变字典时，向其中添加/删除条目会产生多少开销？

它是否会将整个桶视为不可变的，并克隆那些仅重新创建项已更改的桶？

即使是这种情况，似乎仍需要进行大量复制才能创建新字典(?)

- Roger Johansson

Answer 1

我查看了F#语言的Map<K,V>类型的实现方式，我认为它是使用一种函数式AVL树实现的。它将值存储在树的内部节点和叶子节点，并确保每个节点满足|height(left) - height(right)| <= 1的条件。

            A 
         /     \
        B       C
      /   \
     D     E

我认为平均和最坏情况下的复杂度都是 O(log(n))：

• 插入 我们需要克隆从根节点到新插入元素路径上的所有节点，而树的高度最多为 O(log(n))。在“返回”的过程中，树可能需要重新平衡每个节点，但这也只需要 O(log(n))

• 删除 类似于插入 - 我们找到元素，然后克隆从根到该元素的所有节点（在返回到根时重新平衡节点）

请注意，其他不需要在插入/删除时重新平衡从根到当前节点的所有节点的数据结构在不可变场景下并不真正有用，因为您仍然需要为整个路径创建新节点。

- Tomas Petricek

---

还有不同的Map实现。其中一个在http://fsprojects.github.io/FSharpx.Collections/PersistentHashMap.html上描述的使用“哈希数组映射字典树”，需要log32N跃点。这可以被视为对于所有实际问题都是O(1)。 - forki23

Answer 2

很多树形结构可以被重复使用。我不知道算法复杂度，但我猜平均只有像摊销logN的“浪费”...

为什么不尝试编写一个程序来衡量呢？（我们将看看今晚我是否能够激发自己去尝试。）

编辑

好的，这是我编写的一些东西。我还没有决定这里是否有任何有用的数据。

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集合大致可以代表树重新平衡的“浪费”。但现在已经很晚了，我不确定自己是否已经仔细思考过这个问题。 :)

- Brian

---

那么在F#中，字典是一种二叉树而不是哈希表？我猜这很有道理。 如果是这样，它是自平衡的吗？ - Roger Johansson

是的，可以。您可以查看map.fs中CTP的实现。 - Brian