15

モナドを使用しない定数アクセス クエリ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

不足している 2 つの候補ライブラリがあるようです。

unordered-containers

unordered-containersタイプの厳密なバリアントと遅延バリアントの両方が含まれますHashMap。関数によって文書化されているように、両方HashMapの s にはO(log n)クエリがありlookupます。このクエリ アクセス時間は、 O(log n)機能HashMapを可能にする内部ツリー構造を持つ型の構築によるものと思われます。多くのユースケースで理解できるデザインのトレードオフですが、変更可能なものは必要ないため、このトレードオフが私のユースケースを妨げています。 insertHashMap

hashtables

hashtablesHashTableタイプクラスと、さまざまなテーブル構築戦略を持つ 3 つのインスタンス タイプが含まれています。このライブラリの型クラスは一定時間のO(1) lookup関数定義を定義しますが、それはSTモナドに永遠に埋め込まれています。HashTableステートフルな実装を「凍結」してlookup、ステートフルなモナドに埋め込まれていない関数を持つ方法はありません。ライブラリの型クラス インターフェイスは、計算全体がステート モナドにラップされている場合は適切に設計されていますが、この設計は私のユース ケースには適していません。

ステートフル モナドに埋め込まれていない不変の定数アクセス クエリO(1)連想配列を構築できる型と関数を定義する他のライブラリは存在しますか?

これらの既存のハッシュ ベースのライブラリをラップまたは変更して、ステートフル モナドに埋め込まれていない不変の定数アクセス クエリO(1)連想配列を生成する方法はありますか?

4

3 に答える 3

15

あなたが欲しいライブラリは…ですunordered-containers。Data.Mapまたは、必要に応じて、からの単純な古いものcontainers。

unordered-containersドキュメントの注記では、ルックアップのO (log n ) 時間の複雑さについて心配する必要がない理由が説明されています。

多くの演算の平均的なケースの複雑さはO (log n ) です。実装では大きなベース (つまり 16) を使用するため、実際にはこれらの操作は一定時間です。

これは、特定の種類の関数型データ構造では一般的な方法です。これは、優れた共有プロパティが可能でありながら、時間の複雑性も優れているためです。log 16は、非常に大きなnに対しても非常に小さな数値を生成するため、ほとんどの場合、これらの複雑さを「実質的に一定の時間」として扱うことができます。

これがアプリケーションのボトルネックになる場合は、確かに別のものを使用してください。結局、ログ16 (1,000,000) は 5 を少し下回っているため、ルックアップ時間はそれほど急速には伸びません。そのすべてのデータを処理するには、ルックアップのオーバーヘッドよりもはるかに多くの時間がかかります。

いつものように、最初にプロフィールを。世界で可能な限り最速のハッシュ マップが絶対に必要な問題が何らかの形で発生した場合、命令型のハッシュ マップが必要になる可能性がありますが、これまでに経験したすべてのケースで、関数型のハッシュ マップは問題なく機能します。

于 2016-08-31T00:41:44.547 に答える
11

Alexis の提案に従い、 を使用する必要がありますunordered-containers。sを持つことが保証されているものが本当に必要な場合は、 を使用してΘ(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 に答える