15

我正在寻找一个无 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

unordered-containers包含 type 的严格和惰性变体HashMap。两个HashMaps 都有函数记录的O(log n)查询lookup。这个查询访问时间似乎是由于HashMap类型的构造，它们具有允许O(log n) insert功能的内部树结构。对于许多用例来说，一个可以理解的设计权衡，但由于我不需要可变的HashMap这种权衡阻碍了我的用例。

hashtables

hashtables包含一个HashTable类型类和三个具有不同表构造策略的实例类型。这个库的类型类定义了一个常数时间O(1) lookup函数定义，但它永远嵌入在STmonad 中。没有办法“冻结”有状态的HashTable实现并拥有一个lookup没有嵌入有状态单子的函数。当整个计算包装在一个状态单子中时，库的类型类接口设计得很好，但这种设计不适合我的用例。

是否存在其他一些定义类型和函数的库，这些库可以构造不可变的常量访问查询O(1)关联数组，该数组未嵌入有状态的单子中？

是否存在某种方法来包装或修改这些现有的基于散列的库以生成不嵌入在有状态单子中的不可变常量访问查询O(1)关联数组？

4

3 回答 3

15

你想要的图书馆是unordered-containers…… 或者只是简单的旧Data.Map，containers如果你愿意的话。

unordered-containers文档中的注释解释了为什么您不应该担心查找的O (log n ) 时间复杂度：

许多操作的平均复杂度为O (log n )。该实现使用较大的基数（即 16），因此在实践中这些操作是常数时间。

这是某些功能数据结构的常见做法，因为它允许良好的共享属性，同时也具有良好的时间复杂性。即使对于非常大的n ， log 16仍然会产生非常小的数字，因此您几乎总是可以将这些复杂性视为“有效的恒定时间”。

如果这曾经是您的应用程序的瓶颈，当然，请使用其他方法，但我发现这不太可能。毕竟，日志16（1,000,000）略低于 5，因此您的查找时间不会很快增长。处理所有这些数据将占用比查找开销更多的时间。

一如既往：简介第一。如果您有一个绝对需要世界上最快的哈希映射的问题，您可能需要一个命令式哈希映射，但对于我曾经遇到的每种情况，功能性的都可以正常工作。

于 2016-08-31T00:41:44.547 回答
11

您应该遵循 Alexis 的建议并使用unordered-containers. 如果你真的想要保证有 s 的东西，你可以从usingΘ(1) lookup定义你自己的任何散列表类型的冻结版本，但这不是很优雅。例如：hashtablesunsafePerformIO

module HT
    ( HT
    , fromList
    , lookup
    ) where

import qualified Data.HashTable.IO as H
import Data.Hashable (Hashable)
import Data.Foldable (toList)
import System.IO.Unsafe (unsafePerformIO)
import Prelude hiding (lookup)

newtype HT k v = HT (H.BasicHashTable k v)

fromList :: (Foldable t, Eq k, Hashable k) => t (k, v) -> HT k v
fromList = HT . unsafePerformIO . H.fromList . toList

lookup :: (Eq k, Hashable k) => HT k v -> k -> Maybe v
lookup (HT h) k = unsafePerformIO $ H.lookup h k

以上的两种用法都unsafePerformIO应该是安全的。HT因为将导出为抽象类型至关重要。

于 2016-08-31T00:58:21.187 回答
2

是否存在其他一些定义类型和函数的库，这些库可以构造不嵌入在有状态单子中的不可变常量访问查询 O(1) 关联数组？

在这个时间点上，答案仍然是否定的。

截至 2019 年底，有一个IO基于高效的hashtable软件包，具有不错的基准。

你所描述的似乎是可行的，就像纯粹的、不可变Data.Array的构造是可能的一样。看看Data.Array.Base这是如何通过unsafe*运营商实现的。AData.Array是有界定义的，我最初的想法是，如果允许无界增长，那么纯的、不可变的哈希表可能会出现 GC 问题。

于 2019-11-19T12:21:11.690 回答