haskell - 高性能 Haskell 哈希结构。

Question

我正在编写执行大量表查找的程序。因此，当我偶然发现 Data.Map (当然)，以及 Data.HashMap 和 Data.Hashtable 时，我正在仔细阅读 Haskell 文档>。我不是散列算法方面的专家，在检查了这些包之后，它们看起来都非常相似。因此我想知道:

1:主要差异是什么(如果有)？

2:在对约 4000 个键值对的 map /表进行大量查找时，哪一个性能最佳？

Answer 1

1: What are the major differences, if any?

• Data.Map.Map 内部是平衡二叉树，因此其查找时间复杂度为 O(log n)。我相信这是一个“persistent ”数据结构，这意味着它的实现使得变异操作产生一个新副本，仅更新结构的相关部分。
• Data.HashMap.Map 内部是一个 Data.IntMap.IntMap，它又被实现为 Patricia 树；其查找时间复杂度为 O(min(n, W))，其中 W 是整数中的位数。也是“执着”。新版本(>= 0.2)使用哈希数组映射尝试。根据文档:“许多操作的平均复杂度为 O(log n)。实现使用很大的基数(即 16)，因此实际上这些操作的时间是恒定的。”
• Data.HashTable.HashTable 是一个实际的哈希表，查找时间复杂度为 O(1)。然而，它是一个可变的数据结构——操作是就地完成的——所以如果你想使用它，你就会陷入IO monad。

2: Which would be the most performant with a high volume of lookups on maps/tables of ~4000 key-value pairs?

不幸的是，我能给你的最好答案是“这取决于情况”。如果从字面上理解渐近复杂度，则 Data.Map 的 O(log 4000) = 大约 12，Data.HashMap 的 O(min(4000, 64)) = 64对于 Data.HashTable，O(1) = 1。但它实际上并不是这样工作的...您必须在代码的上下文中尝试它们。