4

ある時点で、N数値のコレクションがあり、中央値の要素がわかっているとしますM。これで、新しい値 が与えられたXので、 を更新する必要があるかもしれませんM。(むしろ、扱っている数値がすべて一意であると仮定する必要があります。また、すべてのサンプルは連続して受信されるため、同時実行性の問題はありません。)

新しい平均の計算は簡単です。古い平均を取り、 を足しX、 を掛けN、 で割りN + 1ます。(これは、N 個の要素の平均がどのように定義されているかを調べれば明らかです。今のところ、数値についてはあまり心配していません。)

私の質問は次のとおりです。中央値を更新するという問題に、創造的/斬新な（またはおそらく最適な）アプローチを提案できる人はいますか? 以下に例 (私自身の設計の簡単なアイデア) を示し、少し分析します。

このサンプルではstd::forward_list、​​C++ 11 が最近これに遭遇した場所であるため、を使用します。std::forward_list<T> sorted;一般性を失うことなく、これを正しい方法で行っていると仮定します: これまでに 遭遇した要素 (タイプ T) の順序付けられたリストを維持しますT x;。

sorted.merge(std::forward_list<T> {{ x }});

ところで、誰かがこれのためのより良い（より効率的/エレガントな）方法を持っているかどうか興味があります. 不満は大歓迎です。

Xは の一部になりました。私sortedの考えを簡単に説明すると、次のようになります。

auto it = sorted.begin(), itend = sorted.end();
typename std::forward_list<T>::size_type count = std::distance(it, itend);
for (const auto &e : sorted) {
    if (it == itend || ++it == itend) {
        M = (count % 2) ? e : (e + M) / 2;
        break;
    } else { ++it; }
}

ここで起こる良いこと (多少見づらくない場合) は、次のとおりです。イテレータを 2 回前方に移動するため (そして安全に、2 回の比較の代償を払って追加することもできます)、 にend()到達すると、適切な（中央値）値になります。奇数の要素Mがある場合は、そのサンプルだけです。そうでない場合は、この要素と古い (押し出された) 中央値の平均です。奇数と偶数が入れ替わるため、古いものと新しいもののどちらかMが実際にコレクションに含まれます。この推論は正しいですよね？

私の O(3n) メソッドがゴミだと思うなら、コメントする必要はありません。出発点として提案しているだけです。

4

2 に答える 2

7

配列は、最小部分または配列の同じサイズの 2 つのヒープツリーに分割でき、最大部分であり、それらの上部には最大要素と最小要素が含まれます。次のように構成された配列を言います。IS1, 2, 4, 4, 5, 5, 7, 8, 8, 8

 1 4
 \ /
  4   2
   \ /
    5  <--- I's top

    5  <--- S's top
   / \
  7   8
 / \
 8 8

要素の数が偶数の場合、中央値 = top(S)+top(I) であり、奇数の場合、ヒープの 1 つが他の要素より 1 つ大きく、中央値が大きい方の上にあることに注意してください。

これが完了したら、中央値の更新は簡単です。要素をヒープの 1 つに追加し、top(S) が top(I) よりも小さくなった場合はそれらの top を交換する必要があります。

于 2013-06-13T11:53:16.230 に答える