質問: 逐次的に平均値を求めるアルゴリズムは指数平滑平均として知られていますが、同様に逐次的に中央値を求めるアルゴリズムはありませんか?
回答: 正確な中央値を逐次的に割り出したければ、全ての要素が復元可能な情報をどこかに蓄積しておかなければなりません。通常の方法で中央値をピックするには: > > 「全ての要素を順に並べたリストを作りつつ、中央の値を取得する」 > > > とするのがよいです。効率の良いものは、クイックソートを途中までやって諦める方法でしょう。リニアになりますが、ピックの時間が、O(n)~O(1)で行えます。("median of medians" とかで検索してみてください) 質問にあるような状況で、逐次的に処理したく、かつ、全てのデータを蓄積してよいなら: > > 「順に並べたリストに新しい要素を追加し、中央の値を取得する」 > > > ことになるでしょう。今度は挿入のコストを考える必要があります。効率の良いものは、二分木に値を追加し、中央値を探索する方法です。中央値取得のみを目的にしたデータ構造ではないのですが、Order statistic tree が使えます。二分探索木のノードにランク/深さデータを付加したもので、最適な状態(平衡木であれば)、追加及び探索コストが、それぞれ O(log(n))に近くなり良い感じです。Python だと、 blist に実装があります。 情報を蓄積せずに中央値を割り出したいとなれば: > > 「入力データから逐次割り出していた統計値から、中央値を点推定する」 > > > こととなりますが、中央値は分布によって大きく傾く値なので、データの種類によってやり方が異なってきそうです。確認はしていないのですが、KoRoN さんの提示された方法は入力データの偏り情報も保持しておくことで、不正確さを小さくできる方法の一つでしょう。データの大きさが未知であるストリーミングに良い方法だと思います。