1

日付を持つオブジェクトがたくさんあり、2 つの任意の日付の間にあるすべてのオブジェクトを定期的に検索したいとします。これにはどのようなデータ構造が適していますか?

4

5 に答える 5

4

ソート済みと言うときに日付を意味すると仮定すると、配列がそれを行います。

二分検索を実行して、開始日以上のインデックスを見つけます。次に、別の検索を実行して、<= 終了日であるインデックスを見つけて、アイテムのオフセットとカウントを残すか、とにかくそれらを処理する場合は、終了日を超えるまでリストを繰り返します。

于 2009-04-02T22:49:13.663 に答える
4

二分探索木は、探しているもののように聞こえます。これを使用して、O(log(N) + K) 内のすべてのオブジェクトを見つけることができます。ここで、N はオブジェクトの総数であり、K は実際にその範囲内にあるオブジェクトの数です。（バランスが取れている場合）。挿抜はO(log(N))です。

ほとんどの言語には、これの組み込み実装があります。

範囲の下限を (log(n) で) 見つけて、上限に達するまでそこから繰り返すことができます。

于 2009-04-02T23:20:57.800 に答える
0

ランダム アクセスの変更を行う必要がある場合: v3 の回答のように、ツリー。ルックアップで範囲の下限を見つけてから、上に数えます。ノードの挿入または削除は O(log N) です。stbuton は、重複を許可したい場合 (日付がスタンプされたイベントではもっともらしく思われるため)、ツリーベースのセットは必要ないことを強調しています。

ランダム アクセスの変更を行う必要がない場合: 並べ替えられた配列 (またはベクトルなど)。バイナリ チョップで範囲の開始位置を見つけ、上に数えます。挿入または削除は、途中で O(N) です。複製は簡単です。

ルックアップのアルゴリズム パフォーマンスは、どちらの場合も同じで、O(M + log N) です。ここで、M は範囲のサイズです。ただし、配列はエントリごとに使用するメモリが少なく、範囲をカウントする方が高速になる可能性があります。これは、バイナリ チョップの後は、ポインターをたどるのではなく、順方向の順次メモリ アクセスであるためです。

どちらの場合も、最後に挿入して (償却) O(1) にすることができます。ツリーの場合、先頭にある終了要素の記録を保持すると、O(1) バウンドが得られます。配列の場合、指数関数的に成長すると、償却された O(1) になります。これは、変更が常に、またはほぼ常に「現在の時間で新しいイベントを追加する」場合に役立ちます。これは、時間は (希望どおり) 減少しない量であるためです。システム時刻を使用している場合は、時計が逆方向にリセットされたときの事故を避けるために、もちろん確認する必要があります。

別の答え: SQL テーブルを使用し、データベースが必要に応じて最適化できるようにします。また、Google の BigTable 構造は、クエリの結果が常に事前に準備されたインデックスからの連続したシーケンスになるようにすることで、クエリを高速化するように特別に設計されています :-)

于 2009-04-02T23:48:30.137 に答える
-1

新しいオブジェクトを挿入または削除するたびにオブジェクトを日付順に並べ替え、特定の日付より前または後のすべてのオブジェクトのセグメントの境界を簡単に見つけることができる構造が必要です。

ヒープは完璧な候補のようです。実際のアプリケーションでは、ヒープは単純に配列で表され、すべてのオブジェクトが順番に格納されます。ソートされた配列をヒープと見なすことは、新しいオブジェクトの挿入と削除を適切な場所で O(log(n)) で行うための単純な方法です。

日付 A (除外) と B (含まれる) の間のすべてのオブジェクトを検索する必要がある場合は、A の位置 (または挿入位置、つまり A より後の要素の前の位置) と B の位置を検索します。 (または B の挿入位置)、それらの位置の間のすべてのオブジェクトを返します (これは単に配列/ヒープ内のそれらの位置の間のセクションです)

于 2009-04-02T22:54:27.130 に答える