Data.Hashtable的算法复杂性

Question

我正在尝试编写一个利用哈希值的函数(用于实现A*).

经过一些研究,我发现事实上的标准是Data.Map.

但是,在阅读API文档时,我发现: O(log n). Find the value at a key.

实际上,文档通常表明大O时间明显低于标准Hash的O(1).

所以我找到了Data.HashTable. https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html 本文档没有直接提及大O,这让我相信它可能符合我的期望.

我有几个问题:1)这是正确的吗？O(lookupInDataHashTable)= O(1)？2)为什么我会想要使用Data.Map效率低下？3)我的数据结构需求是否有更好的库？

Answer 1

Data.HashTable已被弃用,您将无法在当前找到它base.

它被弃用了,因为它表现不佳hashtables.

但是,hashtables并且Data.HashTable都是可变实现,Data.Map而且Data.HashMap是不可变的.

Haskell中的可变哈希映射类似于其他语言中的桶阵列或开放寻址解决方案.不可变地图基于树木或尝试.通常,不可变的关联容器不能用O(1)修改来实现.

那么为什么要使用不变的地图？

首先,在Haskell中API更方便.我们不能在纯函数中使用可变映射,只能在IO或ST操作中使用.

其次,可以在线程之间安全地共享不可变映射,这通常是一个至关重要的特性.

第三,在实践中,可变映射和不可变映射之间的性能差异可能是微不足道的,即它不会显着影响整体程序性能.O(log n)也受可用内存的限制,因此与O(1)相比,我们没有得到壮观的渐近差异.特别是,Data.HashMap使用16分支trie,因此trie深度实际上不能超过6或7.

第四,由于我不完全理解的原因(更优化的库？更好地优化GHC？),不可变地图可以更快速地显示出来; 我已经尝试了几次Data.HashMap用可变映射替换hashtables,但之后性能总是有点差.

Answer 2

鉴于 Data.Map 效率低下，我为什么要使用它？

它可能效率不高，但它支持 Ord 实例的任何类型的键，即使那些不能哈希为整数的键。

O(lookupInDataHashTable) = O(1) 吗？

一般来说是的。“lookupInDataHashTable”的工作流程以及对应的大O表示法的表现是：

因此，除非您有很长的字符串作为键，否则查找函数可以保证 O(1) 的性能。

有没有更好的库可以满足我的数据结构需求？

这取决于您的密钥的类型。对于不同的整数，Data.IntMap 最好，对于其他可哈希类型，Data.HashMap 显示出不错的性能，否则您别无选择，只能使用 Data.Map。