2

EventsManager外部ソースからイベントを受け取るがあります。AnEventには atypeと aがありvalueます。

リスナーを に登録してEventsManager、特定のタイプのイベントの連続する値を通知することができます。

は、特定のタイプのイベントに対して次の 2 つのEventsManagerことを約束します。

  • 同じ値が続けて 2 回送信されることはありません (リスナーが通知を受け取ると、受信する値が前の通知とは異なる値であることが保証されます)。
  • 特定のタイプのイベントについて、外部ソースから値を受け取る順序を保持する必要があります。

動作するsynchronizedバージョンがありますが、スループットを改善したいと考えています。

典型的な用途: < 1k リスナー、< 10k イベント タイプ、< 1M イベント/秒 (ただし、そのタイプのイベントに登録されたリスナーがないか、値が変更されていないため、ほとんどは破棄されます)。

  • その動作を実装するための最も効率的な戦略は何でしょうか (たとえば、イベント タイプごとに 1 つのキュー/ロックを使用し、それらを ConcurrentMap に保持できますが、10k のキューを持つことは良い考えのようには思えません)。
  • スケーラブルな並行構造を使用してそのようなことを行う既存のライブラリはありますか?

例: リスナーが次lst1のタイプのイベントをリッスンしたいtype1
場合 EventsManager は次を受け取ります。

event: type2, value: 2
event: type1, value: 1
event: type1, value: 1 //no change => discard
event: type3, value: 4
event: type1, value: 7

lst1次の順序で受信する必要があります: 1(1 回のみ) then 7.

4

2 に答える 2

1

この回答は、コメントが追加されると変更されます。

外部ソースを制御できる場合、最も迅速な改善は、そのソースが破棄/無視されることが保証されているメッセージを送信しないようにすることです。たとえば、外部ソースは、Map迅速なルックアップと更新を可能にする、またはその他のデータ構造を保持できます。外部ソースは、あなたに送信する必要のある情報を決定することができますEventQueue

外部ソースを制御しないEvent場合は、元の投稿で述べたように、キューがジェネリックを保持する可能性があります。Radix Treeから供給されるを追加することをお勧めしますQueue。つまり、キューが生成する値を基数ツリー内に格納するということです。これにより、次のことが可能になります。

バランスの取れたツリーとは異なり、基数ツリーでは、O（log n）ではなくO（k）時間でのルックアップ、挿入、および削除が可能です。通常はk≥lognであるため、これは利点とは思えませんが、バランスの取れたツリーでは、すべての比較はO（k）の最悪の場合の時間を必要とする文字列比較であり、その多くは長い共通プレフィックスのために実際には低速です（比較が文字列の先頭から始まる場合）。トライでは、すべての比較に一定の時間が必要ですが、長さmの文字列を検索するにはm回の比較が必要です。基数木は、より少ない比較でこれらの操作を実行でき、必要なノードがはるかに少なくなります。

アップデート

質問：

基数木のスレッドセーフな実装を知っていますか？

並行ツリー はこれらをテストしていません！

API：ConcurrentRadixTree

于 2012-12-14T12:28:43.440 に答える
1

このイベントフローを実装しようと思います

  1. すべての着信イベントは初期EventQueueに入れられます
  2. EventDispatcherThreadは EventQueue を読み取り、イベントをフィルタリングして、タイプごとに適切なEventQueueにルーティングします (キューの単純なマップ)。
  3. EventListernerThreadの複数のインスタンスが、そのタイプの適切な EventQueue を読み取っています...

ロック/同期は必要ありません

于 2012-12-14T12:54:31.323 に答える