9
可能な限り高速な機能更新を備えた配列のようなデータ構造が必要です。私は、このプロパティ（ブラウン、ランダムアクセスリスト）を私に提供する柔軟な配列のいくつかの異なる実装を見てきましたが、私が追加または前置詞に興味がない場合に特別に最適化された実装があるのだろうかと思います - ちょうど更新。機能更新機能を備えた配列の最も効率的な実装は何ですか？
A
答えて
13
ジャンクリストフFilliâtreが永続的配列のa very nice implementationを有し、それは（約永続組合見つけ、永続的なアレイは、コア構成要素であるからである）、同じページにリンクされthe paperに記載されています。コードは直接ご利用いただけますthere。
アイデアは、配列の「最後のバージョンは」O(1)アクセスと更新操作で、通常の配列として表現されており、以前のバージョンでは、この最後のバージョン、プラス差異のリストとして表現されていることです。以前のバージョンの構造体にアクセスしようとすると、配列は "rerooted"され、相違点のリストが適用され、効率的な表現が再び表示されます。
これはもちろん、関連のないバージョンの構造に常にアクセスして変更する場合は、再ルーティングコストを頻繁に支払うことになりますが、主に1つのバージョンで作業する共通のワークフローでは、そして時には "最後のバージョン"になって更新を取得する古いバージョンにバックトラックすることは非常に効率的です。観察可能な純粋なインターフェースの下に隠された非常に使い易い変更可能性。
2
あなたはどの言語を使用していますか？ハスケルでは、状態モナドにmutable arraysを使用することができ、水銀では、IO状態をスレッド化することによって可変配列を使用することができます。 Ocamlには配列モジュールもありますが、あいにく、参照透過性は維持されません。
+1
OCamlを使用しています。私はこれらの事柄に関するコミュニティの知識を活用するために、ハスケルという質問にタグを付けました。 Btw、私は古いコピーを効率的に利用できるようにしながら、STArrayが配列の更新を使うという私の問題をどのように解決するのかよくわかりません。 – rgrinberg
+1
OCaml配列は変更可能ですが、永続性はありません。不可能ではないにしても、更新と永続性を備えた常時アクセスが難しいようです。だから、地図はおそらくあなたが望むものです（上記のように）。 –
+0
マップベースの実装にはさまざまなものがありますが、私のユースケースに最適なものを探しています。たとえば、バランスの取れたBSTは、このアプリケーションではひどいでしょう。漸近性能は同じですが。 – rgrinberg
4
1
私はまた機能的な配列が必要で、このSOの質問を数日前に感じました。 Gascheが提案した解決策には満足できませんでした。新しい配列を作成するのはコストのかかる操作であり、古いバージョンの配列に頻繁にアクセスする必要があります（配列上でAIアルファ/ベータの実装を行うために使用する予定です）。
（私はコストが高いと言いますが、最悪の場合、1つのセルしか繰り返し更新されず、それぞれの更新リスト全体を調べる必要があるため、hは履歴サイズです私はまた、配列を再ルーティングする必要があるときに、ほとんどの細胞が更新されないと予想しています）。
これが私が別のアプローチを提案している理由で、ここでフィードバックを得ることができます。私の考えは、B-Treeのような配列を格納することです。ただし、可変ではないため、索引によって任意の値にアクセスして更新することができます。
私はプロジェクトのリポジトリに小さな紹介：https://github.com/shepard8/ocaml-ptarrayを書きました。順序はツリーの深さと序列が均等になるように選択されるので、get/set操作の順序、つまりO（k^2）だけに依存して素敵な複雑さを得ることができます。
k = 10の場合、10^10までの値を保存できます。実際には、私の配列は200以上の値を含むべきではありませんが、これは私のソリューションがどれほど頑強であるかを示すためです。
アドバイス歓迎！
確かにある種の地図ですか？ –
@ DominicBou-Samra不変のマップですか？配列よりもコストがかかりませんか？ –
Dominic、マップ、Braun、およびRALはすべてツリーベースです。純粋なツリーベースのデータ構造を打ち負かすことができる命令型配列（それは突然変異していない）と巧妙な組み合わせがあるかどうかを調べたいと思っています。 – rgrinberg