1

リストへの変更のリストがあります-追加と削除。リストは非常に大きくなる可能性があります。たとえば、10,000 アイテムです。

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

リストを最初から9'000に変更するまで歩くことができました。それは私には少し長すぎるようです。

アイテムのリストを保持し、アイテムが追加されたときと削除されたときに記録し、このリストをたどって、特定の変更でリストに何があるかを確認できます。Adds と Deletes の可能性が同じである場合、実行する必要があるリスト要素の数は半分になります...

しかし、Big O 表記法では、問題のサイズを半分にしても効率が良くなることはありません (私の理解が正しければ)。

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

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

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

私の最初のアイデアは、IDごとに、割り当てられたイベントと割り当て解除されたイベントを保存することでした。次に、割り当てイベントが 9000 より大きい最初の割り当てまで、このリストをたどります。

私はマイク F が指摘した点が好きです - 最も近い 100 番目のアイテムから歩くのは一定の時間です...

4

3 に答える 3

1

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

しかし、より一般的に言えば、big O の複雑さを軽減することは手段であり、目的ではありません。リストが通常 10,000 項目である場合、複雑さを軽減するか、単に高速化するかによって、N=10,000 の場合に高速化することに注意する必要があります。

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

于 2008-10-14T13:38:05.240 に答える
0

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

于 2008-10-14T13:52:20.673 に答える
0

どのような構造で働いていますか？一般的なデータ構造を処理する効率的な方法はありませんが、特定の構造に対する最適化方法と効率的な方法は何千もあります。

はい、O(n) 時間の複雑さのアルゴリズムを使用している場合、アイテムの数を半分にしても O(n) の複雑さから変化しません...しかし、新しいアイテムごとに半分の効果しかないことを意味します元々持っていた。Big O表記はアルゴリズムを分類する良い方法ですが、膨大な数を除いて実際には効率化されていません（良い例の1つはソートです。最悪の場合、クイックソートはマージソートよりも複雑です...しかし、クイックソートを実装できます何百万ものアイテムのソートを扱うアプリケーション以外のほとんどすべてのアプリケーションで、マージソートよりも効率的です)

于 2008-10-14T13:36:36.540 に答える