わかりました。皆さんの回答に感謝します。非常に興味深く、役に立ちます。:)
PriorityQueue は間違いなく私が探していた正しい用語です - ありがとうございます。いよいよ実装です。
これが私が思うことです：
N をキューのサイズ、M を処理時のタイムスタンプ (いわば「同時」イベント) あたりのイベントの平均量とします (イベントの密度は均等に分散されず、「遠い将来」はかなり大きくなります)。まばらですが、時間が経つにつれて、この時間の領域ははるかに密になります（実際、最大密度は4〜12時間後のどこかにあると思います））。私は、かなり大きな M に対して適切に機能するスケーラブルなソリューションを探しています。目標は、これらの M 期日イベントを 1 秒以内に実際に処理することです。
- 何度か提案されているように、単純なツリーアプローチを使用すると、O(log N) の挿入が行われます。これは非常に優れていると思います。1 つのタイムスタンプを処理するコストは、私が正しければ O(M*log N) になり、もはやあまり良くありません。
- 別の方法は、単一のイベントの代わりにイベントのリストを持つツリーを持つことです。リストが存在しない場合にツリーを 2 回下るよりも少し高速な getlistForGivenStampAndCreateIfNoneExists 操作を実装することが実行可能であるはずです。とにかく、M が成長するにつれて、これはあまり問題にならないはずです。挿入は前回同様 O(log N)、処理は O(M+log N) となり、これも良いと思います。
- イベントのリストのハッシュアプローチは、私が定式化したものです。これには O(1) の挿入と O(M) の処理コストも必要ですが、これはハッシュではそれほど簡単ではありません。実際、クールですね。または、何か不足していますか？もちろん、ハッシュをうまく機能させるのはそれほど簡単ではありませんが、それ以外に何か問題はありますか? それともハッシュが問題ですか？ウィキペディアは次のように述べています。
「適切な次元のハッシュ テーブルでは、各ルックアップの平均コスト (命令数) は、テーブルに格納されている要素の数とは無関係です。多くのハッシュ テーブル設計では、キーと値のペアを任意に挿入および削除することもできます。 、操作あたりの一定の平均 (実際には、償却された) コストです。」
簡単なベンチマークでは、私のプラットフォームの標準実装がこれと一致しているように見えることが示されました。
- DVK によって提供されるイベントのリストの配列アプローチ。これには O(1) 挿入があります。これでいいです。しかし、私が正しく理解していれば、O(M+T) の処理コストがかかります。T は配列のサイズ (場合によってはタイムスロットの数) です。配列からの削除には線形コストがかかるためです。また、これは最大時間オフセットがある場合にのみ機能します。
実際には、配列アプローチについて説明したいと思います。O(M+T) はよくありません。全くない。しかし、私はそれにいくつかの頭脳を入れました。これが私が思いついたものです:
最初のアイデア: 怠惰
O(T) は、任意の要因によって縮小される可能性があり、少し怠惰になりますが、最終的には O(T) のままになります。しかし、それはどれほど悪いことですか？T=2419200 としましょう。これは 28 日です。そして、1日1回、クリーンアップします（できれば低負荷が予想される間）。これにより、配列の 5% 未満が無駄になります。私のターゲット プラットフォームでは、かなり古い 2GHz コアでコピー操作に 31 ミリ秒かかるため、それほど悪い考えではないように思えます。
2 番目のアイデア: チャンク
少し考えた後、私はこの解決策を考えました: 間隔のハッシュ、間隔 (つまり、指定された時間枠) は、イベントのリストの配列です。間隔はすべて同じサイズで、できれば数日または数時間などの単純なものです。
挿入については、ハッシュを介して適切な間隔を検索し (存在しない場合は作成します)、その間隔で適切なイベントのリストを検索し (存在しない場合は再度作成します)、それを挿入します。これは O(1) です。
処理については、単純に現在の間隔を取得し、現在予定されているイベントのリストを処理して破棄することで、予定されているイベントを処理します。配列は一定の長さのままなので、O(M) になります (これは、M 要素を処理するために得られる最高のものです)。現在の間隔が完全に処理されると (つまり、間隔が「過去」を表している場合)、単純に O(1) で破棄します。現在の間隔への追加の参照を保持できるため、それを調べる必要がなくなりますが、これでは目立った改善は得られないと思います.
私には、2 番目の最適化は高速で制約がないため、実際には最適なソリューションのように思えます。間隔に適切なサイズを選択すると、メモリ オーバーヘッドとハッシュ ルックアップ オーバーヘッドを最適化できます。ハッシュのルックアップ時間を気にする必要があるかどうかはわかりません。高いMの場合、それは本当に問題にならないはずです。したがって、間隔サイズ 1 を選択すると、アプローチ番号 3 に戻ります。
私はそれについての意見があれば本当にうれしいです。