純粋関数型言語でハッシュ テーブルを効率的に実装する方法はありますか? ハッシュ テーブルを変更するには、元のハッシュ テーブルのコピーを作成する必要があるようです。何か見落としているに違いありません。ハッシュ テーブルは非常に重要なデータ構造であり、ハッシュ テーブルがなければプログラミング言語は制限されてしまいます。
ベストアンサー1
純粋関数型言語でハッシュテーブルを効率的に実装する方法はありますか?
ハッシュテーブルは、抽象的な「辞書」または「連想配列」データ構造の具体的な実装です。したがって、純粋に関数型の効率性についてお聞きになりたいと思います。辞書命令型ハッシュテーブルと比較して。
ハッシュ テーブルを変更するには、元のハッシュ テーブルのコピーを作成する必要があるようです。
はい、ハッシュテーブルは本質的に命令型であり、純粋に機能的な同等のものはありません。おそらく最も類似した純粋に機能的な辞書型はハッシュです。トライしかし、割り当てと間接参照のため、ハッシュ テーブルよりも大幅に遅くなります。
何か見落としているに違いありません。ハッシュ テーブルは非常に重要なデータ構造であり、ハッシュ テーブルがなければプログラミング言語は制限されてしまいます。
辞書は非常に重要なデータ構造です (ただし、1990 年代に Perl が普及するまでは主流ではあまり見られなかったため、人々は何十年もの間辞書の恩恵を受けずにコードを書いていたことは注目に値します)。ハッシュ テーブルも重要であることには同意します。なぜなら、ハッシュ テーブルははるかに効率的な辞書であることが多いからです。
純粋に機能的な辞書は数多くあります。
バランスのとれたツリー (赤黒、AVL、重みバランス、フィンガーツリーなど) (例:
MapOCaml、F#、Data.MapHaskell)。ハッシュ試みるたとえば、
PersistentHashMapClojure など。
しかし、これらの純粋に機能的な辞書はすべて多くの適切なハッシュ テーブル (.NET などDictionary) よりも低速です。
ハッシュテーブルと純粋関数型辞書を比較するHaskellベンチマークでは、純粋関数型辞書の方がパフォーマンスが優れていると主張していますが、注意してください。正しい結論は、Haskellのハッシュテーブルは非常に非効率で、純粋関数型辞書とほぼ同じくらい遅いということです。たとえば、.NETと比較すると、.NETはDictionaryHaskellのハッシュテーブルより26倍高速です！
Haskell のパフォーマンスについてあなたが結論を出そうとしていることを本当に結論付けるには、より多くの操作をテストし、馬鹿げたキー型ではないもの (キーとしても機能する、何ですか?) を使用し、
-N8理由もなく使用せず、Java のようなパラメトリック型をボックス化する第 3 言語 (Java はほとんどの場合許容できるパフォーマンスを発揮するため) と比較して、それがボックス化の一般的な問題なのか、GHC ランタイムのより深刻な欠陥なのかを確認する必要があると思います。これらベンチマークこれらに沿っています (現在のハッシュテーブル実装よりも約 2 倍高速です)。
これはまさに私が言及していた種類の誤った情報です。この文脈では Haskell のハッシュ テーブルには注意を払わず、最速のハッシュ テーブル (つまり Haskell ではないもの) と最速の純粋に機能的な辞書のパフォーマンスだけを見てください。