高性能Haskell散列结构.

Question

我正在编写有很多表查找的程序.因此,我仔细阅读Haskell的文档时,我偶然发现了Data.Map(当然),但也Data.HashMap和Data.Hashtable.我不是哈希算法的专家,在检查包之后,它们看起来都非常相似.因此我想知道:

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

2:在大约4000个键值对的地图/表上进行大量查找,哪个性能最高？

Answer 1

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

• Data.Map.Map内部是一个平衡的二进制树,因此查找的时间复杂度为O(log n).我相信它是一个" 持久的 "数据结构,这意味着它的实现使得变异操作产生了一个新的副本,只更新了结构的相关部分.
• Data.HashMap.Map是一个Data.IntMap.IntMap内部,反过来实现为帕特里夏树; 查找的时间复杂度为O(min(n,W)),其中W是整数中的位数.它也是"持久的".
• Data.HashTable.HashTable是一个实际的哈希表,时间复杂度为O(1),用于查找.但是,它是一个可变数据结构 - 操作是就地完成的 - 所以IO如果你想使用它,你就会陷入monad.

2:在大约4000个键值对的地图/表上进行大量查找,哪个性能最高？

不幸的是,我能给你的最佳答案是"它取决于".如果从字面上理解渐近复杂性,则得到O(log 4000)=约12 Data.Map,O(min(4000,64))= 64 for Data.HashMap,O(1)= 1 for Data.HashTable.但它并没有真正起作用......你必须在代码的上下文中尝试它们.

Answer 2

Data.Map和之间的明显区别Data.HashMap是前者需要键Ord,后者Hashable键.大多数公共密钥都是,所以这不是一个决定性的标准.我没有任何经验Data.HashTable,所以我不能对此发表评论.

API的Data.HashMap和Data.Map非常相似,但是Data.Map导出更多的函数,有些,比如alter缺少Data.HashMap,有些是严格和非严格的变体,而Data.HashMap(我假设你的意思是无序容器的散列图)提供了懒惰和严格的API单独的模块.如果您只使用API​​的公共部分,那么切换实际上是无痛的.

关于性能Data.HashMap的无序的容器有漂亮的快速查找,最后我衡量,这显然快于Data.IntMap或Data.Map,在特别适用于的(尚未发布)HAMT分支无序的容器.我认为对于插入来说,它或多或少与之相当,但Data.IntMap有点快Data.Map,但我对此有点模糊.

对于大多数任务而言,两者都具有足够的性能,对于那些不需要的任务,您可能还需要量身定制的解决方案.考虑到你专门询问查找,我会给出Data.HashMap优势.