在 F# 中使用不可变字典时,添加/删除条目有多少开销?
是否会将整个存储桶视为不可变的并克隆它们并仅重新创建其项目已更改的存储桶?
即使是这种情况,似乎还需要进行大量复制才能创建新字典(?)
最佳答案
我查看了F#的实现Map<K,V>
类型,我认为它被实现为 functional AVL tree .它将值存储在树的内部节点以及叶子节点中,并且对于每个节点,它确保 |height(left) - height(right)| <= 1。
A
/ \
B C
/ \
D E
我认为平均和最坏情况的复杂度都是
O(log(n))
:O(log(n))
.在“回来的路上”,树可能需要重新平衡每个节点,但这也只是 O(log(n))
请注意,在插入/删除时不需要重新平衡从根节点到当前节点的所有节点的其他数据结构在不可变场景中不会真正有用,因为无论如何您都需要为整个路径创建新节点。
关于f# - 不可变字典开销?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2793069/