開始時間と終了時間によって特徴付けられる大規模な (~10 9 ) イベントのセットがあります。与えられた時間で、その時点で進行中だったイベントの数を見つけたいと思います。
この状況では、どのような種類のデータ構造が役立つでしょうか? 高速にする必要がある操作は次のとおりです。
{start: 100000 milliseconds, end: 100010 milliseconds}。更新: 誰かがこれに計算幾何学のフラグを立てたので、計算幾何学の観点からこれを言い換える必要があると思います。1 次元の間隔のセットがあり、それらの間隔のうち、特定の点と交差する数を計算したいと考えています。新しい間隔の挿入は高速でなければなりません。
インターバル ツリーを探しています。
O(n log n)、nは間隔の数O(m+log n)、ここmで、 はクエリ結果nの数、 は間隔の数ですO(n)他の回答に追加するだけで、時間の長さと必要な粒度に応じて、単純にカウンターの配列を持つことができます。たとえば、時間の長さが 24 時間で、目的の粒度が 1 ミリ秒の場合、配列には 86,400,000 個のセルが存在します。セルごとに 1 つの 4 バイト int (10^9 を保持するのに十分) を使用すると、少なくとも (8+8+4+4)*10^ を必要とするツリーベースのソリューションに対して、700 MB 未満の RAM になります。 9 = 2 つのポインター用に 24 GB の RAM と、ツリー ノードごとに 2 つの ints (32 ビットのアドレス指定可能なメモリでは不十分なため、ポインターごとに 64 ビットが必要です)。スワップを使用できますが、一部のクエリが大幅に遅くなります。
たとえば、配列を循環バッファーとして使用することにより、過去 24 時間のデータのみを気にする場合にも、このソリューションを使用できます。時間と粒度の制限に加えて、もう 1 つの欠点は、間隔の挿入時間が間隔の長さに比例することです。そのため、間隔の長さに制限がない場合、問題が発生する可能性があります。一方、クエリは単一の配列ルックアップです。
(tskuzzy と Snowball による回答の拡張)
バランスの取れた二分探索木は理にかなっていますが、メモリ要件がデータ セットに対して過剰になる場合があります。Bツリーは、ライブラリを使用できない限り、より複雑ではありますが、はるかにメモリ効率が高くなります。
開始時刻と終了時刻の 2 つのツリーを保持します。イベントを挿入するには、開始時刻を開始時刻のツリーに追加し、終了時刻を終了時刻のツリーに追加します。時間 T におけるアクティブなイベントの数を照会するには、開始時間ツリーを検索して T 未満の開始時間がいくつあるかを調べ、終了時間ツリーを検索して T 未満の終了時間がいくつあるかを調べます。開始回数から終了回数、それがアクティブなイベントの数です。
挿入とクエリは両方とも O(log N) 時間かかるはずです。
いくつかのコメント:
質問の表現方法では、どのイベントがアクティブであったかではなく、アクティブなイベントの数だけを気にします。これは、開始時刻と終了時刻を追跡する必要がないことを意味します。これにより、以前の回答で引用されたクエリで「+ M」という用語を回避しやすくなります。
クエリの正確なセマンティクスに注意してください。特に、イベントが時間 T に開始された場合、そのイベントは時間 T でアクティブであると見なされますか? 時間 T で終了する場合は? これらの質問に対する答えは、特定の場所で < または <= を使用するかどうかに影響します。
ほとんどの場合、重複を許可してカウントする必要があるため、「セット」データ構造を使用しないでください。つまり、複数のイベントが同時に開始および/または終了する可能性があります。セットは通常、重複を無視します。代わりに探しているのは「マルチセット」(「バッグ」と呼ばれることもあります) です。
多くの二分探索木は、そのままでは「要素数 < T」クエリをサポートしていません。ただし、各ノードにサイズを格納することで、この機能を簡単に追加できます。
N個の要素を持つソートされたセット（たとえば、平衡二分探索木またはスキップリスト）のデータ構造があるとします。さらに、ソートされたセットにO（log N）検索時間、O（log N）挿入時間、およびO（N）スペース使用量があるとします（これらは妥当な仮定です。たとえば、赤黒木を参照してください）。
1つの可能性は、2つのソートされたセット、bystartおよびbyendをそれぞれイベントの開始時刻と終了時刻でソートすることです。
時間内に進行中のイベントの数を見つけるには、終了時間がO（log N）検索操作よりも大きい最初の間隔をt要求します。この間隔の開始時刻を呼び出します。ここで、開始時間が。以上である間隔の数を求めます。これはO（log N + M）です。ここで、Mはそのような間隔の数です。したがって、検索の合計時間はO（log N + M）です。byendtleftbystartleftt
ソートされたセットの挿入はO（log N）でした。これは、ソートされたセットごとに1回実行する必要があります。これにより、挿入操作の合計時間がO（log N）になります。
この構造を最初から構築するのはN回の挿入操作だけなので、構築の合計時間はO（N log N）です。
ソートされたセットごとのスペース使用量はO（N）であるため、合計スペース使用量はO（N）です。
概要：