チェンジリストの効率的な横断

Question

リストに対する変更のリストがあります-追加と削除。リストは膨大になる可能性があります-たとえば、10'000個のアイテム。

変更後のリストの状態を知りたい9'000。

リストを最初から歩いて、9'000を変更できました。それは私には少し時間がかかりそうです。

アイテムのリストを保持して、追加時と削除時を記録し、このリストを歩いて特定の変更でリストにあるものを確認します。追加と削除が同様に発生する可能性がある場合、ウォークスルーする必要があるリスト要素の数を半分にします...

しかし、ビッグO表記法では、問題のサイズを半分にしても、物事が効率的になるわけではありません（正しく理解できていれば）。

100回または1000回の変更ごとにリストの状態をキャッシュできますが、繰り返しますが、大きなOは、アイテム数を「n」で割っても効率は良くないと言います。

では、これを行う効率的な方法は何ですか？これを行う効率的な方法はありますか？

詳細： 具体的には、カスタムアロケータでメモリ割り当て/割り当て解除を追跡しています。各割り当て/割り当て解除は、リスト内のイベントです。各割り当てには一意のIDがあります。 （たとえば）9'000イベントの後に現在割り当てられているものを知りたい。

最初のアイデアは、各IDに対して、割り当てられたイベントと割り当て解除されたイベントを保存することでした。次に、このリストをallocイベントが9000を超える最初の割り当てまで歩きます。しかし、先ほど言ったように、これは歩き回る必要のあるアイテムの数を半分にするだけです。

マイクFによるポイントが好きです-一番近い100番目のアイテムから歩いているのは一定の時間です...

Answer 1

X番目の変更ごとにリストの状態をキャッシュする場合、バイナリチョップを実行して、探している変更の境界となる2つのキャッシュされた状態に移動し、最大Xアイテムを歩いてアイテムに到達できます自体。それはO（log N）、多かれ少なかれです。

しかし、より一般的には、大きなOの複雑さを減らすことが手段であり、終わりではありません。リストが通常10,000アイテムの場合、複雑さを軽減するか、単に高速化するかどうかにかかわらず、N = 10,000でリストを高速化することを心配する必要があります。

編集：おっと、あなたの質問をもっと注意深く読みました。 100個のアイテムごとに状態をキャッシュする場合、検索しないので、バイナリチョップを行う必要もありません。最も近いキャッシュ状態に直接ジャンプし、最大100個のアイテムを歩いてアイテムに到達します。自体。それは一定時間のアルゴリズムですか？

Answer 2

どのような構造で作業していますか？一般的なデータ構造を効率的に調べる方法はありませんが、数千の最適化方法と特定の構造の効率的な方法があります。

そして、はい、O（n）時間の複雑さのアルゴリズムがある場合、アイテムの数を半分にしてもO（n）の複雑さから変更されることはありません...元々の効果。 Big O表記法はアルゴリズムを分類する良い方法ですが、膨大な数を除いて実際には効率になりません（1つの良い例は並べ替えです。最悪の場合、クイックソートはマージソートよりも複雑です...数百万のアイテムのソートを処理するアプリケーション以外のほとんどすべてのアプリケーションで、mergesortよりも効率的です）

Answer 3

「タイムスタンプ」または各挿入と削除をマークすると、変更を見つけるために単純な走査が必要になります（O（n））。