插入新绑定时是否复制了整个Map？

Question

我想更好地理解例如Data.Map的实习生.当我在Map中插入一个新的绑定时,由于数据的不变性,我得到一个与旧数据结构加上新绑定相同的新数据结构.

我想了解这是如何实现的.编译器最终是通过使用数百万个绑定复制整个数据结构来实现的吗？通常可以说可变数据结构/数组(例如Data.Judy)或命令式编程语言在这种情况下表现更好吗？在字典/键值存储方面,不可变数据是否具有任何优势？

Answer 1

Map建立在树数据结构上.基本上,新的Map值被构造,但它会与指针的几乎完全充满旧结构.由于Haskell中的值永远不会改变,因此这是一种安全且非常重要的优化,称为共享.

这意味着您可以使用相同数据结构的许多相似版本,但只有树的不同分支才会重新存储; 其余的只是指向分支原始副本的指针.而且,当然,如果你扔掉旧的Map你,树枝做的改变将被垃圾回收器回收.

共享是不可变数据结构性能的关键.您可能会发现这篇维基百科文章很有用; 它有一些启发性图表,显示修改后的数据如何通过共享来表示.

@JFritsch:在插入地图后,您需要复制具有N个元素的树的O(log N)节点.事实上,通常使用纯数据结构,您可能需要在单个可变短暂数据结构上进行额外的对数量工作.但是对于插入到树中,您将不得不为首先递归到节点而支付相同数量的开销,因此在分配更多内存时,该操作的渐近性能保持不变.使用Judy数组,它可以在内部使用小哈希表,在某些地方使用O(1). (5认同)
@JFritsch:但是,对于不可变存储,您可以随时恢复到任何以前版本的存储,只需保留指向它的指针即可.这为您提供了或多或少的免费"撤消"功能,并允许您并行评估对商店的多种可能编辑(例如,如果它是游戏板),没有额外的推理或锁定开销. (5认同)
@JFritsch:嗯,它仍然需要构造树的修改部分.这可以通过懒惰来缓解(只有你实际看到的树的部分才能构建),但是如果你不需要不变性提供的任何优点(更简单的编程模型,你可以保留多个修改版本而不存储整个副本,等等,当然简单直接写入内存会更快.但它通常没有你想象的那么大. (3认同)

Answer 2

否.Data.Map.insert插入状态的文档需要O(log n)时间.如果它必须复制整个结构,那么就不可能满足那个界限.

Answer 3

Data.Map不复制旧地图; 它(懒惰地)分配O(log N)个新节点,这些节点指向(从而共享)大部分旧地图.

因为"更新"地图不会破坏旧版本,所以这种数据结构为您提供了构建并发算法的更大自由.