性能Haskell散列结构。

我正在写程序,做了很多表查找。 就这样,当我偶然发现Data.Map (当然),还有Data.HashMapData.Hashtable时,我正在Data.Map Haskell文档。 我不是散列algorithm方面的专家,在检查包之后,他们看起来都非常相似。 因此我想知道:

1:如果有什么重大区别?

2:在大约4000个键值对的地图/表上,查找量最大的是哪一个?

3 Solutions collect form web for “性能Haskell散列结构。”

1:如果有什么主要区别?

  • Data.Map.Map在内部是一个平衡的二叉树,所以查找的时间复杂度是O(log n)。 我相信这是一个“ 持久的 ”数据结构,这意味着它的实现使得变化操作产生一个新的副本,只更新结构的相关部分。
  • Data.HashMap.Map在内部是一个Data.IntMap.IntMap ,它又被实现为Patricia树; 其查找的时间复杂度为O(min(n,W)),其中W是整数中的位数。 它也是“持久的”。
  • Data.HashTable.HashTable是一个实际的哈希表,其查询的时间复杂度为O(1)。 然而,这是一个可变的数据结构 – 操作是在原地完成的 – 所以如果你想使用它,你就被困在IO monad中。

2:在大约4000个键值对的地图/表上,查找量最大的是哪一个?

不幸的是,我可以给你的最好的答案是“这取决于”。 如果从字面上Data.Map渐近复杂性, Data.Map ,O(min( Data.HashMap ))= 64, Data.HashMap O(log 4000)= 12, Data.Map O(1)= 1。 但是这并不是真的那样…你必须在你的代码中尝试它们。

Data.MapData.HashMap区别在于前者需要Ord键,后者是Hashable键。 大多数常用密钥都是,所以这不是一个决定性的标准。 我没有任何与Data.HashTable经验,所以我不能对此发表评论。

Data.HashMapData.Map的API非常相似,但Data.Map导出更多的函数,其中一些像Data.HashMap中没有Data.HashMap ,另外一些提供了严格和非严格的变体,而Data.HashMap (I假设你的意思是来自无序容器的散列表)在单独的模块中提供了惰性和严格的API。 如果你只使用API​​的公共部分,切换是非常痛苦的。

关于性能, 无序容器的 Data.HashMap查找速度相当快,最后我测量,它明显快于Data.IntMapData.Map ,特别适用于(尚未发布的) 无序容器的 HAMT分支。 我认为插入,它是或多或less与Data.IntMapData.IntMap并且比Data.Map快一点,但是我有点模糊。

对于大多数任务来说,这两者都是充分的performance,对于那些不是那些任务的人来说,无论如何你可能都需要一个量身定制的解决scheme。 考虑到你特别要求查询,我会给Data.HashMap的边缘。

Data.HashTable的文档现在说“使用哈希表包”。 有一个很好的博客文章解释了为什么哈希表是一个很好的包。 它使用ST monad。

  • 你如何在Haskell中表示graphics?
  • 什么是Haskell的DataKinds扩展?
  • 如何在Haskell项目中使用DLL?
  • 究竟是什么让选项在斯卡拉monad?
  • 为什么Haskell的Prelude.read没有返回一个Maybe?
  • 为什么在Haskell中将副作用build模为monad?
  • 什么是应用风格的实际用途?
  • 在Haskell中求幂
  • 是什么让Haskell的types系统比其他语言的types系统更“强大”呢?
  • 什么(f。)。 g的意思是在Haskell?
  • 我什么时候想要使用免费的Monad + Interpreter模式?