可能な限り最速の機能更新を備えた配列のようなデータ構造が必要です。このプロパティ（ブラウン、ランダムアクセスリスト）を提供する柔軟な配列のいくつかの異なる実装を見てきましたが、追加または追加に関心がない場合に特に最適化された実装があるかどうか疑問に思っています-更新するだけです。
1468 次
4 に答える
13
Jean-CristopheFilliâtreには、永続配列の非常に優れた実装があります。これは、同じページにリンクされているペーパー（永続配列がコアコンポーネントである永続的なunion-findに関するもの）で説明されています。コードはそこで直接入手できます。
O(1)アレイの「最後のバージョン」は、アクセスおよび更新操作を伴う通常のアレイとして表され、以前のバージョンは、この最後のバージョンと相違点のリストとして表されるという考え方です。以前のバージョンの構造にアクセスしようとすると、配列が「ルート変更」されて、相違点のリストが適用され、効率的な表現が再び表示されます。
もちろん、これはすべてのワークフローでO（1）になるわけではありません（構造の無関係なバージョンに絶えずアクセスして変更する場合は、ルート変更のコストを頻繁に支払うことになります）が、主に1つのバージョンで作業し、場合によっては再び「最後のバージョン」になり、更新を取得する古いバージョンでは、これは非常に効率的です。観察的に純粋なインターフェースの下に隠された可変性の非常に優れた使用法。
于 2013-02-05T09:22:56.877 に答える
2
どの言語を使用していますか？Haskellでは、状態モナドで可変配列を使用でき、Mercuryでは、IO状態をスレッド化することで可変配列を使用できます。Ocamlには配列モジュールもありますが、それがあなたが求めているものである場合、残念ながら参照透過性を維持しません。
于 2013-02-05T03:56:22.877 に答える
1
また、機能的な配列が必要で、数日前にこのSOの質問を感じました。新しいアレイの作成はコストのかかる操作であり、古いバージョンのアレイに頻繁にアクセスする必要があるため、Gascheによって提案されたソリューションに満足しませんでした（アレイで再生するAIアルファ/ベータ実装にこれを使用する予定です）。
（コストがかかると言うと、O（n * h）だと思います。hは履歴サイズです。最悪の場合、1つのセルだけが繰り返し更新され、各セルの更新リスト全体を調べる必要があるためです。私もアレイを再ルーティングする必要があるときに、ほとんどのセルが更新されないことを期待してください）。
これが私が別のアプローチを提案する理由です、多分私はここでいくつかのフィードバックを得ることができます。私の考えは、配列をBツリーのように格納することです。ただし、配列は変更できないため、インデックスによって任意の値に非常に簡単にアクセスして更新できます。
プロジェクトのリポジトリに簡単な紹介を書きました：https ：//github.com/shepard8/ocaml-ptarray 。順序は、ツリーの深さと順序が均等になるように選択されるため、get / set操作の順序、つまりO（k ^ 2）のみに応じて、非常に複雑になります。
k = 10の場合、最大10^10の値を格納できます。実際、私の配列には200を超える値を含めるべきではありませんが、これは私のソリューションがどれほど堅牢であるかを示すためのものです。
アドバイスは大歓迎です！
于 2016-12-30T13:34:28.433 に答える