Data.Hashtable 的算法复杂度
Algorithmic complexity of Data.Hashtable
我正在尝试编写一个利用散列的函数(用于 A* 的实现)。
经过一番研究,我发现事实上的标准是Data.Map
。
然而,在阅读API文档时,我发现:O(log n). Find the value at a key.
https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html
事实上,文档通常建议大 O 时间明显低于标准哈希的 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) 是否有更好的库满足我的数据结构需求?
Data.HashTable
已弃用,您不会在当前 base
.
中找到它
它已被弃用,因为它与 hashtables
相比表现不佳。
然而,hashtables
和 Data.HashTable
都是可变的实现,而 Data.Map
and Data.HashMap
是不可变的。
Haskell 中的可变哈希映射类似于 array-of-buckets 或其他语言中的开放寻址解决方案。不可变映射基于树或尝试。通常,不可变的关联容器不能通过 O(1) 修改来实现。
那么为什么要使用不可变映射?
首先,API 在 Haskell 中更方便。我们不能在纯函数中使用可变映射,只能在 IO 或 ST 操作中使用。
其次,不可变映射可以在线程之间安全共享,这通常是一个关键特性。
第三,在实践中,可变映射和不可变映射之间的性能差异可能微不足道,即。 e.它不会显着影响整体程序性能。 O(log n) 也受到可用内存的限制,因此与 O(1) 相比,我们不会得到显着的渐近差异。特别是,Data.HashMap
使用 16 分支的 trie,因此 trie 深度实际上不能超过 6 或 7。
第四,由于我不完全理解的原因(更优化的库?更好的 GHC 优化?),不可变映射可以更快;我已经尝试过几次用 hashtables
中的可变映射替换 Data.HashMap
,但之后性能总是有点差。
Why would I ever want to use Data.Map given its inefficiency?
它可能效率不高,但它支持带有 Ord 实例的任何类型的键,即使是那些不能散列为整数的键。
Is O(lookupInDataHashTable) = O(1)?
一般是的。 "lookupInDataHashTable"的工作流程以及在big-O表示法中对应的表现是:
- 散列密钥。对于整数:O(1),对于字符串:O(字符串长度)
- 使用散列访问一个 IOArray,得到一个包含所有具有相同散列的 key-value 对的列表。 O(1)
- 在列表中查找密钥。 O(列表长度)
所以除非你有很长的字符串作为键,否则查找函数保证 O(1) 性能。
Is there a better library for my data structure needs?
这取决于您的密钥类型。对于不同的整数 Data.IntMap 最好,对于其他 hash-able 类型 Data.HashMap 表现不错,否则你别无选择,只能 Data.Map.
我正在尝试编写一个利用散列的函数(用于 A* 的实现)。
经过一番研究,我发现事实上的标准是Data.Map
。
然而,在阅读API文档时,我发现:O(log n). Find the value at a key.
https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html
事实上,文档通常建议大 O 时间明显低于标准哈希的 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) 是否有更好的库满足我的数据结构需求?
Data.HashTable
已弃用,您不会在当前 base
.
它已被弃用,因为它与 hashtables
相比表现不佳。
然而,hashtables
和 Data.HashTable
都是可变的实现,而 Data.Map
and Data.HashMap
是不可变的。
Haskell 中的可变哈希映射类似于 array-of-buckets 或其他语言中的开放寻址解决方案。不可变映射基于树或尝试。通常,不可变的关联容器不能通过 O(1) 修改来实现。
那么为什么要使用不可变映射?
首先,API 在 Haskell 中更方便。我们不能在纯函数中使用可变映射,只能在 IO 或 ST 操作中使用。
其次,不可变映射可以在线程之间安全共享,这通常是一个关键特性。
第三,在实践中,可变映射和不可变映射之间的性能差异可能微不足道,即。 e.它不会显着影响整体程序性能。 O(log n) 也受到可用内存的限制,因此与 O(1) 相比,我们不会得到显着的渐近差异。特别是,Data.HashMap
使用 16 分支的 trie,因此 trie 深度实际上不能超过 6 或 7。
第四,由于我不完全理解的原因(更优化的库?更好的 GHC 优化?),不可变映射可以更快;我已经尝试过几次用 hashtables
中的可变映射替换 Data.HashMap
,但之后性能总是有点差。
Why would I ever want to use Data.Map given its inefficiency?
它可能效率不高,但它支持带有 Ord 实例的任何类型的键,即使是那些不能散列为整数的键。
Is O(lookupInDataHashTable) = O(1)?
一般是的。 "lookupInDataHashTable"的工作流程以及在big-O表示法中对应的表现是:
- 散列密钥。对于整数:O(1),对于字符串:O(字符串长度)
- 使用散列访问一个 IOArray,得到一个包含所有具有相同散列的 key-value 对的列表。 O(1)
- 在列表中查找密钥。 O(列表长度)
所以除非你有很长的字符串作为键,否则查找函数保证 O(1) 性能。
Is there a better library for my data structure needs?
这取决于您的密钥类型。对于不同的整数 Data.IntMap 最好,对于其他 hash-able 类型 Data.HashMap 表现不错,否则你别无选择,只能 Data.Map.