2

o(1) イベント/データを n 個のアイテムに発行できるようにするデータ構造/言語/アルゴリズム/オペレーティング システムなどはありますか? 通常、pubsub が実装されているのを見ると、サブスクライバーのリストをトラバースし、それらに対して関数を起動する必要があります。

n個のアイテムへのより即時の通知を可能にするプラットフォーム/言語はありますか? OSレベルでも、これを実現する手段はありますか?

私はそれが不可能だと信じがちですが、OS/ハードウェアの知識が限られているため、これを可能にする「ボンネットの下」に何かがあるかどうか疑問に思っています.

私の質問の理由

私はこれが少し「そこにある」ことを知っています--しかし、脳細胞/ニューロンについて少し読んで、ニューロンが電荷を介して軸索を介してn個の受信機に電気/情報を送ることができるという事実を読んで、それは理にかなっていますこれは、ハードウェア レベルで o(1) pub を n サブスクライバーに提供するために、OS がそれをスケジュールするなどして模倣できると思います。

だから私は、それが現代のハードウェア/OSのどこかで何らかの形で起こるかどうか、特にカスタムコールバックでフックできるものかどうか疑問に思っていました.

4

4 に答える 4

3

サブスクライバーにパブリッシュさせることで、O(log(n)) 通知を行うこともできます。パブリッシャーは 2 つのサブスクライバーに通知し、それぞれが 2 つのサブスクライバーに通知し、それぞれが 2 つのサブスクライバーに通知します。

O(1) の「通知」を行うことはできますが、それにはサブスクライバーのポーリングが含まれており、おそらくあなたが求めているものではありません。パブリッシャーは共有配列に書き込み、サブスクライバーは array[i] をポーリングします。パブリッシャーが配列 [i] に書き込むと、サブスクライバーはデータを読み取り、配列 [i+1] をポーリングします。サブスクライバーが配列 [i] を読み取ったときにパブリッシャーに通知することもできます。パブリッシャーは、すべてのサブスクライバーから通知を受け取ったときに array[i] でデータを解放できます。これにより、継続的に増加する配列の代わりに循環バッファーを使用できます。(サブスクライバーをポーリングする代わりに array[i] でブロックすることもできますが、その後、各サブスクライバーのパブリッシャー コールバックを使用してブロックを終了することに戻ります。)

于 2013-06-08T19:35:24.640 に答える
1

ここに私が考えることができる方法があります..

1. 線形: O(n)合計時間 ~ シングル プロセッサのマシンでの線形実行

2. 並列: O(n/k)合計時間 ~ k 個のプロセッサを搭載したマシンでの並列実行

3. 分散階層: 階層 O(m)内の各ノードの時間、O(n) 合計時間。ここで、m はプロセッサの M-ary 階層を表します

4. 並列分散階層: 階層 O(1)内の各ノードの時間、O(m^h - mh)合計時間 (基本的に非リーフ ノードの数)。ここで、h は階層の高さで、階層内の各ノードには m 個のプロセッサがあります

于 2013-06-09T04:50:28.513 に答える
0

ここでかなりの混乱を招いたと思います。N 人のサブスクライバーに通知する漸近的な時間の複雑さは、少なくとも O(N) になります。これは、N 人のサブスクライバーがあり、それらすべてに通知する必要があるためです。

(@Zim-Zam が提案したように) 並列処理を行うことで実世界の時間を節約できますが、漸近的な時間の複雑さは変わりません。

人間の脳も同じで、500万個のニューロンに通知しようと思っても、一気にはできない…。

于 2013-06-08T22:03:43.967 に答える
0

ネットワーク上のハードウェア マルチキャストは、マルチキャストをリッスンしているネットワーク上のすべてのマシンに発行される O(1) イベントです。すべてのイーサネットネットワークがこれをサポートしています。

ネットワーク設計によっては、O(log(n)) に近いIP マルチキャストもあります。

IP マルチキャストは、ネットワーク内の IP インフラストラクチャを介した 1 対多および多対多のリアルタイム通信のための技術です。これは、受信者の身元に関する事前の知識も、受信者の数に関する事前の知識も必要としないため、より多くの受信者集団に対応できます。マルチキャストは、多数の受信者に配信する必要がある場合でも、送信元がパケットを 1 回だけ送信することを要求することで、ネットワーク インフラストラクチャを効率的に使用します。ネットワーク内のノード (通常はネットワーク スイッチとルーター) は、メッセージがネットワークの各リンクを介して 1 回だけ送信されるように、複数の受信者に到達するようにパケットを複製します。

したがって、各サブスクライバーが異なるコンピューター上にある場合は実行できます。各サブスクライバーが同じコンピューター内の異なる CPU 上にある場合は、コンピューターの内部設計に依存します。

于 2014-03-01T15:57:48.353 に答える