为什么 Map 在读取时比 Dictionary 慢，在 F# 中（来自我附加的基准）

Question

我偶然发现了这个页面：http : //jackfoxy.com/simple-lookups-in-fsharp/

它对用于插入和检索的各种集合进行基准测试。

如果我们看一下这张表（网页上的第二张）：

String Key by Number of Elements in Lookup Structure, 10,000 random lookups
        Map     IntMap  Dict    HashTbl     HshMltMap
10^2    1.3     n/a     0.4     0.3     1.5
10^3    1.7     n/a     0.4     0.4     1.5
10^4    3.0     n/a     0.7     0.7     1.8
10^5    5.3     n/a     1.5     1.2     2.4
10^6    8.4     n/a     1.6     1.5     6.3

我们可以看到，当 Map 变大时，使用 Map 进行查找比使用 Dictionary 慢 5 倍。

由于 Map 是只读的，因此可以以最优化的方式组织数据，因为它不处理插入、调整大小等。为什么它这么慢？

Answer 1

C# 字典是使用哈希表实现的，因此查找速度接近于O(1).

F# Map，由于不变性，必须使用二叉树，因此查找速度为O(logN).

F# Map 和其他不可变数据结构实际上处理插入。你仍然需要向地图插入一个元素，但得到一个新地图，而旧地图仍然完好无损。为了使其有效，新的和旧的必须共享元素（不涉及克隆/复制）。

是的，最好的方法是使用树（F# Map、Set）或链表（F# List）。