10

私はすぐにそれを取得します - 他の命令型言語の配列と同じように、Haskell で動的にサイズ変更された定数時間アクセス データ構造を持つ方法はありますか?

魔法のようにこれを行うモジュールがどこかにあると確信していますが、機能的な方法でこれを行う方法の一般的な説明を望んでいます:)

私が知る限りMap、二分木表現を使用しているため、O(log(n))アクセス時間があり、リストにはもちろんO(n)アクセス時間があります。

それに、イミュータブルにすればピュアじゃないですか。

これについてどうすればよいか（Array = Array { one :: Int, two :: Int, three :: Int ...}テンプレートHaskellなどのようなものを超えて）何かアイデアはありますか？

4

4 に答える 4

8

キーが に同形である場合は、ほとんどの操作がであるため、IntMapIntを使用できます。個々の操作は定数に収束します。O(min(n,W))nWInt

于 2013-11-07T09:42:12.003 に答える
2

他の良い答えに加えて、次のように言うと役立つ場合があります。

代数データ型と純粋性に制限されている場合、動的にサイズ設定されたすべてのデータ構造には、少なくとも対数の最悪の場合のアクセス時間が必要です。

個人的には、これを純潔の代償と呼んでいます。

Haskell は、これを回避する 3 つの主な方法を提供します。

  • 問題の変更: ハッシュまたはプレフィックス ツリーを使用します。
  • 一定時間の読み取りには、純粋なArrayまたは最新のVectorを使用します。それらはADTではなく、コンパイラのサポート/内部の隠しIOが必要です。元のデータ構造を変更することは純度によって禁止されているため、一定時間の書き込みは不可能です。
  • 一定時間の書き込みIOにはorSTモナドを使用し、ST外部から見える副作用を回避できる場合を優先します。これらのモナドはコンパイラに実装されています。
于 2014-03-01T03:05:51.453 に答える