是否存在有用的 Haskell HashMap/HashTable/Dictionary 库? [英] Does a useful Haskell HashMap/HashTable/Dictionary library exist?
问题描述
我正在寻找一个无 monad 的常量访问查询 O(1) 关联数组.
I'm looking for a monad-free, constant access query O(1) associative array.
考虑假设的类型:
data HT k v = ???
我想构造一个不可变结构一次:
I want to construct an immutable structure once:
fromList :: Foldable t, Hashable k => t (k,v) -> HT k v
我想随后用恒定时间访问重复查询它::
I want to subsequently query it repeatedly with constant time access::
lookup :: Hashable k => HT k v -> k -> Maybe v
似乎有两个候选库不足:
There appears to be two candidate libraries which fall short:
unordered-containers 包含 HashMap 类型的严格变体和惰性变体.两个 HashMap 都有 O(log n) 查询，如 lookup 函数.这个查询访问时间似乎是由于 HashMap 类型的构造，它具有允许 O(log n) insert功能.对于许多用例来说，这是一种可以理解的设计权衡，但由于我不需要可变的 HashMap，这种权衡阻碍了我的用例.
unordered-containers contains both strict and lazy variants of the type HashMap. Both HashMaps have O(log n) queries as documented by the lookup function. This query access time appears to be due to the construction of the HashMap types, which have an internal tree structure allowing for O(log n) insert functionality. An understandable design trade off for many use-cases, but since I don't need a mutable HashMap this tradeoff hampers my use-case.
hashtables 包含一个 HashTable 类型类和三个具有不同表构造策略的实例类型.这个库的类型类定义了一个常数时间O(1) lookup 函数定义，但它永远嵌入在 ST monad 中.没有办法冻结"有状态的 HashTable 实现并拥有一个未嵌入有状态 monad 的 lookup 函数.当整个计算包装在一个状态单子中时，库的类型类接口设计得很好，但这种设计不适合我的用例.
hashtables contains a HashTable type-class and three instance types with varying table constructions strategies. This library's type-class defines a constant time O(1) lookup function definition, but it is eternally embedded in the ST monad. There is no way to "freeze" the stateful HashTable implementations and have a lookup function that is not embedded of a stateful monad. The library's type-class interface is well designed when the entire computation is wrapped in a state monad, but this design is unsuitable for my use-case.
是否存在其他一些定义类型和函数的库，这些库可以构造不可变的常量访问查询O(1) 关联数组，该数组未嵌入有状态的 monad?
Does there exist some other library which defines types and functions which can construct an immutable constant access query O(1) associative array that is not embedded in a stateful monad?
是否存在某种方法来包装或修改这些现有的基于散列的库以生成不嵌入在有状态 monad 中的不可变常量访问查询 O(1) 关联数组?
Does there exist some way to wrap or modify these existing hashing-based libraries to produce an immutable constant access query O(1) associative array that is not embedded in a stateful monad?
推荐答案
你想要的库是... unordered-containers.或者只是简单的旧 Data.Map 来自 containers，如果你愿意的话.
The library you want is… unordered-containers. Or just plain old Data.Map from containers, if you’d prefer.
unordered-containers 文档 解释了为什么您不必担心查找的 O(log n) 时间复杂度:
The note in the unordered-containers documentation explains why you shouldn’t worry about the O(log n) time complexity for lookups:
许多操作的平均情况复杂度为 O(log n).该实现使用较大的基数(即 16)，因此在实践中这些操作是常数时间.
Many operations have a average-case complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.
这是某些函数数据结构的常见做法，因为它允许良好的共享属性，同时也具有良好的时间复杂性.即使对于非常大的 n，log16 仍然会产生 非常小的 数，因此您几乎总是可以将这些复杂性视为有效的恒定时间".
This is a common practice with certain kinds of functional data structures because it allows good sharing properties while also having good time complexities. log16 still produces very small numbers even for very large n, so you can almost always treat those complexities as "effectively constant time".
如果这曾经是您的应用程序的瓶颈，当然可以使用其他方法，但我认为这不太可能.毕竟，log16(1,000,000) 略低于 5，因此您的查找时间不会很快增长.处理所有这些数据将花费比查找开销更多的时间.
If this is ever a bottleneck for your application, sure, go with something else, but I find that highly unlikely. After all, log16(1,000,000) is a little under 5, so your lookup time is not going to grow very quickly. Processing all that data is going to take up much more time than the overhead of the lookup.
一如既往:个人资料优先.如果您有一个绝对需要世界上最快的哈希映射的问题，您可能需要一个命令式哈希映射，但对于我曾经遇到的每种情况，功能性的都可以正常工作.
As always: profile first. If you somehow have a problem that absolutely needs the fastest possible hash map in the world, you might need an imperative hash map, but for every case I’ve ever had, the functional ones work just fine.
这篇关于是否存在有用的 Haskell HashMap/HashTable/Dictionary 库?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
