我正在寻找一个无monad的恒定访问查询O(1)关联数组。
考虑假设的类型:
data HT k v = ???
我想一次构造一个不变的结构:
fromList :: Foldable t, Hashable k => t (k,v) -> HT k v
我想随后使用恒定时间访问来反复查询它:
lookup :: Hashable k => HT k v -> k -> Maybe v
似乎有两个候选库不足:
unordered-containers hashtables unordered-containersunordered-containers包含HashMap类型的strict和lazy变体。如 HashMap 函数所记录的，两个lookup都具有O(log n)查询。此查询访问时间似乎是由于HashMap类型的构造而造成的，这些类型具有内部树结构，允许O(log n) insert 功能。一个可以理解的设计在许多用例中都进行了折衷，但是由于我不需要可变的HashMap，因此这种折衷会妨碍我的用例。hashtableshashtables包含HashTable类型类和具有不同表构造策略的三种实例类型。该库的类型类定义了恒定时间O(1) lookup 函数定义，但它永久嵌入在ST monad中。没有办法“冻结”有状态的HashTable实现，并且没有未嵌入有状态的monad的lookup函数。当整个计算都封装在状态monad中时，该库的类型类接口(interface)经过了精心设计，但是这种设计不适用于我的用例。是否存在其他一些定义类型和函数的库，它们可以构造不嵌入有状态monad的不可变常量访问查询O(1)关联数组？
是否存在某种方法来包装或修改这些现有的基于散列的库，以产生不嵌入有状态单子(monad)的不可变常量访问查询O(1)关联数组？
最佳答案
您想要的库是…unordered-containers。或者，如果您愿意，也可以只是Data.Map中的普通旧containers。
unordered-containers documentation中的注释说明了为什么您不必担心查询的O(log n)时间复杂度:
许多操作的平均情况复杂度为O(log n)。该实现使用一个较大的基数(即16)，因此实际上这些操作是恒定时间。
对于某些类型的功能数据结构，这是一种常见的做法，因为它允许良好的共享属性，同时还具有良好的时间复杂性。即使对于非常大的n，log16仍然会产生非常小的数字，因此您几乎总是可以将这些复杂性视为“有效的恒定时间”。
如果这对您的应用程序来说是一个瓶颈，那么当然可以采取其他措施，但是我发现这种可能性很小。毕竟log16(1,000,000)小于5，所以您的查找时间不会很快增加。处理所有数据将比查找开销花费更多的时间。
与往常一样:首先进行简介。如果您因某种原因而绝对需要世界上最快的哈希图，则可能需要命令式哈希图，但是对于我所遇到的每种情况，功能都很好。