部分的に変化する配列の時系列を保存する最も効率的なデータ構造は何ですか?

Question

私の問題は、サイズ N のオブジェクトの配列があることです。毎回 (t+1) 以降、配列の値の一部は変更される場合と変更されない場合があります。したがって、t+1 インデックス 15 は変更されますが、その他はすべて同じままだとします。

もちろん配列の配列を用意する以外に、このようなものを (メモリに) 格納する最も効率的な方法は何でしょうか?可能な限り最も効率的な方法で、いつでも配列のすべての値、たとえば getValues(long time) を取得できるようにしたいと考えています。

4 つの配列の場合

時間1ヌルヌルヌルxyz

時間2 null null abc xyz

(ここでは abc のみが変更されていることに注意してください) ただし、時間 1 からの最後のインデックスの値はまだ保持されています。

Answer 1

あなたが求めているものは、学術CS分野では「部分永続配列」として知られています。永続性の詳細については、次を参照してください。 カプラン社の調査.

1 つの簡単な解決策は、配列の代わりに検索ツリーを使用することです。純粋に機能的にバランスの取れた検索ツリーを使用すると、各読み取りまたは書き込みに O(1) 時間ではなく O(lg n) (n は配列のサイズ) の最悪の場合の時間がかかることを保証できます。(タイムスタンプ付きのバージョンを拡張可能な配列に保持する場合、新しいバージョンの追加は O(1) で償却され、古いバージョンへのアクセスは最悪の場合でも O(1) になります。)

純粋に機能的な検索ツリーに慣れていない場合は、以下を読んでください。 Clojure の永続配列の概要. 。これらは固定幅の整数 (トライ形式) にインデックス付けされた純粋な関数ツリーであるため、固定の深さを持ちます。これは、最悪の場合でも現実世界でも、問題に対する最速の解決策となる可能性があります。

私が知っている他の唯一の部分的に永続的な配列は、最悪の場合、さらに時間がかかる可能性があります。さまざまな制限された方法で配列にアクセスする場合、償却された複雑さがより優れたものや、予想される複雑さがより優れたものもあります。