0

ブログ Web サイトを作成しているとしましょう。複数の著者による最近のブログ投稿を「優先度」でソートして表示します。優先度が一番上。優先度は、以下を含む公式によって決定されます。

  1. 投稿が公開されたのはいつですか
  2. どれだけのコメントを集めたか

注文は常にリアルタイムで正確でなければなりません。

優先順位によるソートは簡単です。問題は、私たちのウェブサイトが非常に人気があり、1 分あたり数百の割合でコメントが飛び交っているとしましょう。彼らは何十もの投稿に飛び込みます。

このシナリオを処理するパターンはありますか? 言い換えれば、投稿にコメントがあるたびに優先度フィールドを更新し、ページが読み込まれるたびに投稿を並べ替えるよりも良いことはありますか? 大量のユーザー アクティビティによって順序が頻繁に変更されるため、ポスト オーダーのキャッシュはあまり役に立ちません。

「パターン」については、コードとデータベース スキーマの両方の観点から話しています。

4

1 に答える 1

0

バランスの取れたバイナリ ツリー (赤黒ツリーなど) を使用して、並べ替えられたインデックスを格納できます。これにより、インデックス全体を毎回並べ替える場合よりも更新が速くなります。

Javaっぽい疑似コードを使用すると、これは次のようになります

Tree tree;

Node {
    int priority;

    incrementPriority() {
        priority = priority + 1;
        if(priority > tree.nextHighestNode(this)) {
            tree.remove(this);
            tree.add(this);
        }
    }

    decrementPriority() {
        priority = priority - 1;
        if(priority < tree.nextLowestNode(this)) {
            tree.remove(this);
            tree.add(this);
        }
    }
}

ノードの優先度を変更することで、そのノードが無効なツリーの場所にあることを意味する場合 (つまり、次に高いノードであるべきものよりも高いか、次に低いノードであるべきものよりも低いことを意味します)、そのノードは削除され、再度実行されます。ツリーに追加されます (リバランス自体を処理します)。挿入は O(log(n)) ですが、通常 (挿入/削除がない場合) 優先度の更新は一定時間の操作です。

赤黒木はバランスの取れた二分木が通常どのように実装されるかですが、代替手段があります。たとえば、Tango 木はオンライン実装であるため、ここではおそらくより適切です。最大の問題は同時実行性にあります。理想的には、ある種の AtomicInteger (アトミック インクリメントとデクリメントを許可します。かなりの数の言語がこのようなものを持っています) を使用して、ノードの優先度フィールドを実装できるようにする必要があります。フィールドを変更するたびにロックする必要はありませんが、優先度を隣接ノードの優先度とアトミックに比較することは困難です。

別の方法として、配列または連結リストにすべてを格納し、優先順位が変更されたときに隣接する要素を交換することができます。要素はO(log(n))であり、隣接する2つの配列/リスト要素を交換するのは一定時間です。唯一の問題は、配列のすべての要素をシフトする必要があるため、まったく新しい要素を追加すると配列にコストがかかることです。アイテムを挿入する正しい場所が見つかるまでリストをトラバースする必要があるため、リストでも O(n) になりますが、隣接するものをシフトする必要がないため、これはおそらく配列よりも望ましいです要素 (これにより、必要なロックの量が減ります)。

于 2013-04-25T02:25:20.823 に答える