効率的な優先度更新を可能にする優先度キュー？

https://stackoverflow.com/questions/450180

19-08-2019
|

質問

更新：ハッシュタイミングホイールの実装です。パフォーマンスと同時実行性を改善するためのアイデアがあれば教えてください。（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);
    }
}

更新：階層型およびハッシュ型タイミングホイール。（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）でした。フィボナッチヒープのような一部のヒープにはO（1）のreduceKey（）およびmin（）操作がありますが、少なくとも必要なのは高速のincrementKey（）およびmin（）（または減少キー（）および最大（））。

この特定のユースケース向けに高度に最適化されたデータ構造を知っていますか？私が考えている戦略の1つは、すべてのタスクをハッシュテーブルに保存し、すべてのタスクを1秒ごとに繰り返すことですが、それほど美しくはありません。

解決

エラーが発生したケースから迅速に完了する通常のケースの処理を分離しようとするのはどうですか？

ハッシュテーブルと優先度キューの両方を使用します。タスクが開始されると、ハッシュテーブルに入れられ、すぐに終了するとO（1）時間で削除されます。

1秒ごとにハッシュテーブルをスキャンし、長時間（たとえば.75秒）だったタスクを優先キューに移動します。優先キューは常に小さく、扱いやすいものでなければなりません。これは、1秒が探しているタイムアウト時間よりもはるかに短いことを前提としています。

ハッシュテーブルのスキャンが遅すぎる場合は、2つのハッシュテーブルを使用できます。1つは本質的に偶数秒、もう1つは奇数秒です。タスクが開始されると、現在のハッシュテーブルに入れられます。毎秒、すべてのタスクを非現在のハッシュテーブルから優先度キューに移動し、ハッシュテーブルをスワップして、現在のハッシュテーブルが空になり、非現在のテーブルに1〜2秒前に開始されたタスクが含まれるようにします。

これらのオプションは、優先度キューを使用するよりもはるかに複雑ですが、安定しているはずの非常に簡単に実装できます。

他のヒント

私の知る限り（過去の結果も確認した新しい優先度キューについての論文を書きました）、優先度キューの実装は、フィボナッチヒープの境界と一定時間の増加キーを取得しません。

文字通りそれを取得することには小さな問題があります。 O（1）で増加キーを取得できる場合、O（1）で削除を取得できます-キーを+ infinityに増やすだけです（標準の償却テクニックを使用して、多くの+ infinityでいっぱいのキューを処理できます））。ただし、find-minもO（1）の場合、delete-min = find-min + deleteはO（1）になります。比較ベースの優先度キューでは不可能です。なぜなら、並べ替えの境界は（すべてを挿入してから、1つずつ削除する）ことを意味するためです

n * insert + n * delete-min <！> gt; n log n。

ここでのポイントは、優先キューでO（1）の増加キーをサポートする場合、次のペナルティのいずれかを受け入れる必要があることです。

比較ベースではありません。実際、これは物事を回避するためのかなり良い方法です。 vEBツリー。
挿入ではO（log n）を受け入れ、make-heapではO（n log n）を受け入れます（n個の開始値が与えられます）。これは最悪です。
find-minでO（log n）を受け入れます。これは、find-minを実際に do 実行しない（削除を伴わない）場合は完全に受け入れられます。

しかし、私の知る限り、最後のオプションを実行した人はいません。私はこれをデータ構造の非常に基本的な領域での新しい結果の機会と常に考えてきました。

ハッシュタイミングホイールを使用-Google 'Hashed Hierarchical詳細については、「タイミングホイール」を参照してください。ここで人々が行った答えの一般化です。階層的なタイミングホイールよりも大きなホイールサイズのハッシュタイミングホイールを使用したいです。

ハッシュとO（logN）構造のいくつかの組み合わせは、あなたが求めることをするべきです。

私は、あなたが問題を分析している方法に困惑したいと思っています。上記のコメントで、あなたは言う

更新は非常に頻繁に行われるため。接続ごとにM個のメッセージを送信すると、全体の時間はO（MNlogN）になります。これはかなり大きいです。 <！>＃8211; Trustin Lee（6時間前）

これは完全に正しいです。しかし、私が知っているほとんどの人は、メッセージごとのコストに集中するでしょう。あなたのアプリがやるべき仕事が増えるにつれて、明らかにより多くのリソースが必要になるという理論に。

アプリケーションで10億個のソケットが同時に開いている場合（同時に（そうですか？）、挿入コストは1メッセージあたり約60比較です。

これは時期尚早な最適化であることにお金を賭けます。CodeAnalystやVTuneなどのパフォーマンス分析ツールを使用して、システムのボトルネックを実際に測定したことはありません。

とにかく、たった1つの構造で望みのことをやらないと判断した後、さまざまなアルゴリズムの長所と短所の組み合わせが必要になったら、あなたが求めることを行う方法はおそらく無限にあります。

1つの可能性は、ソケットドメインNをサイズBのいくつかのバケットに分割し、各ソケットをそれらの（N / B）バケットの1つにハッシュすることです。そのバケットには、O（log B）更新時間のあるヒープ（または何でも）があります。 Nの上限が事前に固定されておらず、変化する可能性がある場合、より多くのバケットを動的に作成できます。これにより、少し複雑になりますが、確かに実行可能です。

最悪の場合、ウォッチドッグタイマーは期限切れのキュー（N / B）を検索する必要がありますが、ウォッチドッグタイマーは特定の順序でアイドルソケットを強制終了する必要はありません！ つまり、最後のタイムスライスで10個のソケットがアイドル状態になった場合、最初にタイムアウトしたドメインをそのドメインで検索し、それを処理してから、2番目にタイムアウトしたドメインを見つける必要はありません。バケットの（N / B）セットをスキャンし、すべてのタイムアウトを列挙する必要があります。

バケットの線形配列に満足できない場合は、キューの優先キューを使用できますが、すべてのメッセージでそのキューを更新したり、開始した場所に戻ったりしたくない場合があります。代わりに、実際のタイムアウトよりも短い時間を定義します。（その3/4または7/8と言います）そして、最長時間がそれを超える場合にのみ、低レベルキューを高レベルキューに入れます。

そして明白なことを述べるリスクがあるので、キューが経過時間をキーにしたくないのです。キーは start 時間でなければなりません。キュー内の各レコードについて、経過時間を絶えず更新する必要がありますが、各レコードの開始時間は変更されません。

O p>

通常のFIFOキューを作成して、10秒でタイムアウトするすべてのタスクを保持します。すべてのタスクのタイムアウト期間は同一であるため、最後まで挿入して最初から削除するだけで、キューのソートを維持できます。
タイムアウト時間が30秒のタスク用に別のFIFOキューを作成します。他のタイムアウト期間のキューをさらに作成します。
キャンセルするには、アイテムをキューから削除します。キューがリンクリストとして実装されている場合、これはO（1）です。
両方の操作がO（1）であるため、キャンセルは挿入として再スケジュールできます。タスクは別のキューに再スケジュールできることに注意してください。
最後に、すべてのFIFOキューを単一の全体的な優先度キューに結合するには、すべてのFIFOキューの先頭を通常のヒープに参加させます。このヒープの先頭は、すべてのタスクのうちタイムアウトが最も早く終了するタスクになります。

m個の異なるタイムアウト期間がある場合、構造全体の各操作の複雑さはO（log m）です。どのキューに挿入するかを検索する必要があるため、挿入はO（log m）です。 Remove-minは、ヒープを復元するためのO（log m）です。キャンセルはO（1）ですが、キューの先頭をキャンセルする場合は最悪の場合O（log m）です。 mは小さな固定数であるため、O（log m）は本質的にO（1）です。タスクの数に比例しません。

あなたの特定のシナリオは、私に循環バッファを示唆しています。最大の場合タイムアウトは30秒で、少なくとも10分の1秒ごとにソケットを取得し、その期間の1/10秒ごとに1つずつ、300の二重リンクリストのバッファーを使用します。エントリの 'increaseTime'を設定するには、そのエントリをリストから削除し、新しい10秒間（両方の定数時間操作）のエントリに追加します。ピリオドが終了したら、現在のリストに残っているものを刈り取り（リーパースレッドにフィードするなど）、現在のリストポインターを進めます。

キュー内のアイテム数に厳しい制限があります-TCPソケットには制限があります。

したがって、問題は限定されます。巧妙なデータ構造は、組み込み型を使用するよりも遅くなると思います。

java.lang.PriorityQueueを使用しない正当な理由はありますか？ remove（）は、log（N）時間でキャンセル操作を処理しませんか？次に、キューの先頭にあるアイテムまでの時間に基づいて独自の待機を実装します。

すべてのタスクをリストに保存し、それらを繰り返し処理するのが最善だと思います。

このコストが重要となる限界に達するには、かなり頑丈なマシンでサーバーを実行する必要がありますか？

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow