更新:これが Hashed Timing Wheels の私の実装です。パフォーマンスと同時実行性を改善するアイデアがあれば教えてください。(2009 年 1 月 20 日)
// Sample usage:
public static void main(String[] args) throws Exception {
Timer timer = new HashedWheelTimer();
for (int i = 0; i < 100000; i ++) {
timer.newTimeout(new TimerTask() {
public void run(Timeout timeout) throws Exception {
// Extend another second.
timeout.extend();
}
}, 1000, TimeUnit.MILLISECONDS);
}
}
更新: Hierarchical and Hashed Timing Wheelsを使用してこの問題を解決しました。(2009 年 1 月 19 日)
タイムアウト処理用に最適化された特別な目的のタイマーを Java で実装しようとしています。たとえば、ユーザーは期限のあるタスクを登録でき、タイマーは期限が過ぎたときにユーザーのコールバック メソッドに通知できます。ほとんどの場合、登録されたタスクは非常に短い時間内に完了するため、ほとんどのタスクはキャンセルされるか (例: task.cancel())、将来に再スケジュールされます (例: task.rescheduleToLater(1, TimeUnit.SECOND))。 .
このタイマーを使用して、アイドル状態のソケット接続を検出し (たとえば、10 秒以内にメッセージが受信されない場合に接続を閉じる)、書き込みタイムアウトを検出します (たとえば、書き込み操作が 30 秒以内に終了しない場合に例外を発生させます)。異常なネットワークの問題がない限り、タイムアウトは発生せず、クライアントはメッセージを送信し、応答が送信されます。
java.util.Timer または java.util.concurrent.ScheduledThreadPoolExecutor は、ほとんどのタスクがタイムアウトになると想定しているため、使用できません。タスクがキャンセルされた場合、キャンセルされたタスクは、ScheduledThreadPoolExecutor.purge() が呼び出されるまで内部ヒープに格納されます。これは非常にコストのかかる操作です。(O(NlogN) もしかして?)
CSクラスで学んだ従来のヒープまたは優先度キューでは、要素の優先度の更新は高価な操作でした（多くの場合、要素を削除して再挿入することによってのみ達成できるため、O（logN）新しい優先度値. フィボナッチヒープのようないくつかのヒープには、reduceKey() と min() 操作の O(1) 時間がありますが、少なくとも私が必要としているのは、高速な increaseKey() と min() (または reduceKey() と max()) です。 .
この特定のユースケースに対して高度に最適化されたデータ構造を知っていますか? 私が考えている戦略の 1 つは、すべてのタスクをハッシュ テーブルに保存し、すべてのタスクを 1 秒ごとに反復処理することですが、それほど美しいものではありません。