サブジェクトが巨大なコンテナである場合、オブザーバー パターンを効率的に実装するにはどうすればよいでしょうか?

Question

私たちは皆知っています 観察者パターン:状態の変化をオブザーバーのリストに通知して更新できるサブジェクトがあります。ここで、観察したい対象がコンテナであり、コンテナ自体を観察したいとします。要素の追加と削除、および含まれる要素、すなわちコンテナ要素の状態の更新。

コンテナに大量のオブジェクトを格納する場合、要素の挿入と削除を高速に行うには、更新メカニズムをどのように実装しますか?特に、

• オブザーバーのローカル コピーで同じタイプのコンテナを使用しますか?
• オブザーバーが使用すべきコンテナの賢明な選択はあるのでしょうか?(たとえば、リンクされたリストを観察している場合でも、常にバランスの取れたツリーを使用した方が速いでしょうか?)
• イテレータを監視対象のコンテナに、イテレータをオブザーバのコンテナに素早く変換するにはどうすればよいでしょうか?(配列の場合は簡単ですが、リンクされたリストの場合は困難ですか?)

たとえば、コンテナーがリンク リストの場合は、一定時間で要素を挿入できます。m 人のオブザーバーが n 個の要素を含むリストを反復処理する必要がある場合、更新には O(n * m) の予想時間がかかります。

コンテナーが配列の場合、要素の変更には一定の時間がかかり、m 個のオブザーバーを更新するには、要素のインデックスを渡す場合は O(m)、オブザーバーが配列を反復処理する必要がある場合は O(n * m) かかります。

それが役立つ場合は、次の例を検討してください。

例1.あなたはオペレーティング システムを作成しています。観察したい対象は、ファイルシステムとそのファイルです。ビューは、ファイル エクスプローラー、インデクサー、およびその他のアプリケーションです。ファイルが追加、削除、または変更されたときにオブザーバーを更新したいと考えています。

例2。あなたは、ニューヨークほどの規模の都市を処理できるアドレス帳アプリケーションを作成しているとします。あなたが観察したい主題は、あなたの記録のコンテナです (住所、電話番号、電子メールなどを持つ人物)。オブザーバーは複数のビューであり、レコードを追加、削除、または変更すると自動的に更新されます。(1 つのビューには 53 番地に住んでいる人々のリストが含まれており、もう 1 つは姓が Doe である各人について地図上に点を描画していることをイメージできます)。

完全なディレクトリ サブツリーが削除された場合、または「53rd St」の名前が「Dijkstra St」に変更された場合はどのように処理しますか?

Answer 1

何らかの方法で、コンテナを主題に変える必要があります。

ここでの主な問題は、変化に気づく効率的な方法を見つけることです。ほとんどの場合、この問題に遭遇するのは、 なぜなら あなたが観察したいものは、効率的な通知メカニズムを提供していません (おそらく、そのものが書かれたときにオブザーバーの設計パターンが発明されていないためです)。

[編集] 効率的な方法を求めているので、一般的な答えは「状況による」です。デザイン パターンには、「万能の」ソリューションはありません。これらは、問題に対処するための一般的なルールです。特定の状況でルールをどのように実装する必要があるかは、その状況に陥ったときに解決するものです。

一般に、観察者が小さな変化を識別する必要がある場合 (つまり、属性の変更や要素の追加など）、通知メッセージにはこれを効率的に実行できる十分な情報が含まれている必要があります。したがって、大きなリストと挿入がある場合は、リストと新しい要素のインデックスと「挿入された項目」を送信します。

属性変更に関しては、2 つの解決策があります。1 つは、リスト内のすべての要素にオブザーバーを追加することです。これは時間がかかり、大量の RAM を必要とする可能性がありますが、同じリストに複数のタイプを追加できることを意味します。

あるいは、「リスト内の項目を変更するサービス」を使用することもできます。これは、項目を直接変更することは禁止されており、常にサービスを使用する必要があることを意味します。その後、サービスはサブジェクトとして機能し、項目、古い値と変更された値、および場合によってはリスト内のインデックスを含む通知を送信できます。

[編集 2] 一般的なルールは、変更に関するできるだけ多くの情報を収集し、それをオブザーバーに渡すことです。しかし、それは実際にはあなたの特定の問題によって異なります。観察者がリモート マシンに座っているとします。この場合、リスト全体を送信する効率的な方法はありません。「アイテム X が挿入されました」と送信するだけで十分だと思います。コンテナーが変更 (Web サイト上の新しい Web ページなど) に気づく方法がない場合、コンテナーはサイト全体を何度も走査して変更を見つけ、その変更を効率的にオブザーバーに伝える必要があります。

繰り返しますが、詳細は実際には特定の状況によって異なります。Google は数千の Web スパイダーを実行しており、毎時間何百万もの Web ページにアクセスします。長い間、これは (「唯一の方法」のように) 「効率的」でした。少し前に、管理者が Web サイトを Google オブザーバーに変更を伝えることができるサブジェクトに変えることができる「サイトマップ」プロトコルが実装されました。

したがって、何をする必要があるのか​​、より具体的な例を示していただけない限り、より具体的な回答はできません。デザインパターンでは、座って実際の問題に取り組み、頭を働かせる必要があるポイントがあります。

[編集 3] オブザーバー パターンの使用例をいくつか示します。

• 多くの UI フレームワークは、このパターンを使用してイベントを関係者に広めます。Qt には、すべてのサブジェクトがシグナル (送信する通知) を登録でき、オブザーバーがサブジェクトにアタッチできる中心的なスポットがあります。これは、すべての接続が 1 か所で管理されることを意味します。利点は、このデータ構造をすべてのオブジェクトに追加する必要がないことです。また、外部のオブジェクト (非 Qt オブジェクト) もメッセージを送受信できます。すべてが 1 か所にあるため、このデータ構造は簡単に最適化できます。欠点は、この構造が非常に大きくなる可能性があるため、関与する関係者が増えると (まったく関係のない関係者であっても)、メッセージの送信に時間がかかることです。

• Google はサイトマップ プロトコルを使用して Web サイトをサブジェクトに変換します。これは、URL の最終変更時刻 (HTTP GET ではなく HTTP HEAD) のみを要求する場合でも、サイト全体を何度も走査するよりもはるかに効率的であるためです。

• Windows および Linux のファイルシステムは、新しいファイルまたは削除されたファイルについてアプリケーションに通知する通知を提供します。ここでの主な問題は、アプリケーションが実行されていないときにファイルが変更された場合に何が起こるかということです。ディレクトリ内のファイルのチェックサムを管理するアプリがあるとします。アプリがダウンしているときの変更について知りたいのは明らかですが、その場合、通知サービスは最後に送信した変更を追跡する必要があります。したがって、ここでは、アプリは起動時にツリー全体を読み取って見逃した可能性のあるものを確認する必要があり、実行中に発生する変更にはオブザーバー パターンを使用する必要があります。

• メールクライアントはオブザーバーです。これは、最後に見た電子メールの ID をメール サーバーに伝え、サーバーは新しい電子メールについても通知します。

• 複雑なモデルで多数の属性変更がある場合、通常は、すべての変更を一元管理し (単一の場所で実行させる)、そこにオブザーバーをアタッチする (M 個の個別のオブジェクトに N 個のオブザーバーをアタッチするのではなく) ことが唯一の方法です。この実装では、観察者は「どこの変更にも興味があります」、「任意の主題のフィールド X の変更」、または「主題 Y のあらゆる変更」と言うことができます (最後のものは通常「フィールドの変更」を兼ねています)サブジェクト Y の X" - オブザーバーはフィールドへの変更を単に無視します != X)。

Answer 2

なぜオブザーバーパターンそのもの？

対象は興味深いイベントについての観察者に通知する必要があります。そして、観察者は、利害関係者（加入者）にそれを派遣するものとする。

対象の性質は、ここに重要ではありません。 （私は間違ったあなたの質問を理解していない限り）。