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.