問題タブ [median]

中央値5は、アルゴリズム設計の演習として使用されることがあり、 6つの比較のみを使用して計算できることが知られています。

この「6つの比較を使用した5つの中央値」をC＃で実装するための最良の方法は何ですか？私のすべての試みは厄介なコードをもたらすようです:(まだ6つの比較だけを使用しながら、私は素晴らしくて読みやすいコードが必要です。

注：ここでも「アルゴリズム」を提供する必要があると思います。

Azerealがフォーラムの投稿で行ったように、アルゴリズムを明確に説明できないことに気づきました。そこで、ここで彼の投稿を参照します。http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085から

さて、私は自分の課題の1つでこの問題を提起され、このフォーラムに助けを求めましたが、ここには助けがありませんでした。私は最終的にそれを行う方法を見つけました。

1. 最初の4つの要素でマージソートを開始し、各ペアを並べ替えます（2つの比較）

2. 各ペアの下の2つを比較し、可能性から最も低いものを除外します（3つの比較）

3. ペアのない数に取っておいた5番目の数を追加し、2つを比較します（4つの比較）

4. 2つの新しいペアのうち最も低い2つのペアを比較し、下のペアを削除します（5つの比較）

5. 1つだけを比較し、最後のペアの小さい方を比較します。小さい方の数値が中央値です。

   可能な中央値は括弧内にあります

（54321）

5：4 3：22比較

（4 <5 2 <3 1）

4：23比較

2（4 <5 3 1）

1：34比較

2（4 <5 1 <3）

4：15比較

1,2（4 <5 3）

4：36比較

1,2（3）4,5

3つは中央値です

これは、中央値5を見つけるために私が書いたC++コードです。その厄介さを気にしないでください：

もっとコンパクトなはずですね。

@pablitoが彼の回答で指摘したように、ビルトインList.Sort()は最大13の比較を使用するため、この要件を満たすことはできません：]

本とその本に関する複数の価格を含むテーブルがあります (これは非常に単純化されたサンプルです)。

私は簡単に平均を計算していますが、中央値を計算する良い方法があるはずですか?

現在の SQL:

結果：

次のようなグラフの条件付き中央値を計算しようとしています。

MS Excel 2007を使用しています。AVERAGEIF（）ステートメントを認識していますが、Medianに相当するものはありません。主なトリックは、上記の4番目の「a」のようにデータのない行があることです。この場合、計算でこの行をまったく考慮したくありません。

グーグルは次のことを提案しましたが、Excelは数式形式を受け入れません（おそらく2007年だからですか？）

Excelは、数式に問題があるというエラーを表示します（条件の*に関係があります）。次のことも試しましたが、計算では空白のセルが0としてカウントされます。

これらの数式はExcelの「配列」を返すことを認識しています。つまり、正しく機能させるには「Ctrl-shift-enter」を入力する必要があります。

空白のセルを考慮せずに条件付き評価を行うにはどうすればよいですか？

Java で LinkedList として保存されている数値のリストの中央値をどのように見つけますか? ウィキペディアで言及されている選択アルゴリズムがわかりません。それを説明できればボーナスポイント。

一連の値の中央値、モード、歪度、および/または尖度を推定するアルゴリズムはありますが、すべての値を一度にメモリに保存する必要はありませんか?

基本的な統計を計算したい：

• mean: 算術平均
• 分散: 平均からの二乗偏差の平均
• 標準偏差: 分散の平方根
• 中央値: 数値の大きい方の半分と小さい方の半分を分ける値
• モード: セットで見つかった最も頻繁な値
• 歪度: tl; 博士
• 尖度: tl; 博士

これらのいずれかを計算するための基本的な公式は小学校の算数であり、私はそれらを知っています. それらを実装する多くの統計ライブラリもあります。

私の問題は、私が処理しているセット内の多数 (数十億) の値です。Python で作業していると、数十億の要素でリストやハッシュを作成することはできません。これを C で書いたとしても、10 億要素の配列はあまり実用的ではありません。

データはソートされていません。他のプロセスによって、オンザフライでランダムに生成されます。各セットのサイズは非常に可変であり、サイズは事前にわかりません。

セット内の各値を任意の順序で反復して、平均と分散を適切に処理する方法をすでに理解しています。(実際、私の場合、生成された順序でそれらを取得します。) これが私が使用しているアルゴリズムです。

• 3 つの変数を初期化します: count、sum、および sum_of_squares
• 各値について:
  • 増分カウント。
  • 合計に値を追加します。
  • 値の 2 乗を sum_of_squares に追加します。
• 合計をカウントで割り、変数の平均として保存します。
• sum_of_squares をカウントで割り、変数 mean_of_squares として格納します。
• 二乗平均、square_of_mean として保存します。
• mean_of_squares から square_of_mean を引き、分散として保存します。
• 平均と分散を出力します。

この「オンライン」アルゴリズムには弱点があります (たとえば、sum_of_squares が整数の範囲や float の精度よりも急速に大きくなるため、精度の問題が発生するなど)、基本的には、各セットにすべての値を格納する必要がなく、必要なものが得られます。

しかし、追加の統計 (中央値、モード、歪度、尖度) を推定するための同様の手法が存在するかどうかはわかりません。N 個の値を処理するために必要なメモリが O(N) よりも大幅に少ない限り、偏った推定器や、精度をある程度損なう方法を使用することもできます。

ライブラリにこれらの操作の1つ以上を「オンライン」で計算する関数がある場合、既存の統計ライブラリを指すことも役立ちます。

まず、DB2 for i5/OS V5R4 を実行しています。ROW_NUMBER()、RANK()、および共通テーブル式があります。TOP n PERCENT または LIMIT OFFSET がありません。

私が扱っている実際のデータ セットを説明するのは難しいので、列が である気象履歴テーブルがあるとしましょう(city, temperature, timestamp)。各グループの中央値と平均値を比較したい(city)。

これは、テーブル全体の集計の中央値を取得するために見つけた最もクリーンな方法でした。私はここのIBM Redbookからそれを適応させました：

これは、単一の行を戻すにはうまく機能しますが、グループ化するにはうまくいかないようです。概念的には、これが私が望むものです：

私を愚かに見せる答えがあるかもしれませんが、私はメンタルブロックを抱えており、これは今私が取り組むべき一番のことではありません. 可能だと思われますが、非常に複雑なものは使用できません。これは大きなテーブルであり、集計される列をカスタマイズする機能が必要です。

ここで、myData が中央値より上か下かを示す新しい列を作成します

正常に動作します。ここで、同じことを行いたいのですが、myFactor の各レベル内の分割の中央値を計算します。

私はこれを思いついた：

byOutput には、私が欲しいものが含まれています。因子 A、B、および C の各要素を正しく分類します。ただし、新しく計算された中央分割を示す新しい列 myDataFrame$FactorLevelMedianSplit を作成したいと思います。

「by」コマンドの出力を有用なデータフレーム列に変換するにはどうすればよいですか?

おそらく「by」コマンドは、これを行うRのような方法ではないと思います...

更新：

factor() を巧みに使用する方法のティエリーの例と、スペクターの本で「ave」関数を発見したとき、追加のパッケージを必要としないこのソリューションを見つけました。

MySQL で中央値を計算する最も簡単な (そしてできれば遅すぎない) 方法は何ですか? 私はAVG(x)平均を見つけるために使用しましたが、中央値を計算する簡単な方法を見つけるのに苦労しています. 今のところ、すべての行を PHP に返し、並べ替えを行ってから中央の行を選択していますが、単一の MySQL クエリでそれを行う簡単な方法がきっとあるはずです。

サンプルデータ:

でソートするとvalが得られる2 2 3 4 7 8 9ため、中央値は であり4、対SELECT AVG(val)which ==5です。

私は現在、C でローリング メディアン フィルター (ローリング ミーン フィルターに類似) を実装するアルゴリズムに取り組んでいます。文献を検索したところ、合理的に効率的な方法が 2 つあるようです。1 つ目は、値の最初のウィンドウを並べ替え、バイナリ検索を実行して新しい値を挿入し、各反復で既存の値を削除することです。

2 つ目 (Hardle と Steiger、1995 年、JRSS-C、アルゴリズム 296 から) は、一方の端に maxheap、もう一方の端に minheap、中央に中央値を持つ両端ヒープ構造を構築します。これにより、O(n log n) のアルゴリズムではなく、線形時間アルゴリズムが得られます。

これが私の問題です。前者を実装することは可能ですが、これを何百万もの時系列で実行する必要があるため、効率が非常に重要です。後者は、実装が非常に難しいことがわかっています。R の stats パッケージのコードの Trunmed.c ファイルにコードが見つかりましたが、かなり判読できません。

線形時間ローリング メディアン アルゴリズムの適切に作成された C 実装を知っている人はいますか?

編集: Trunmed.c コードへのリンクhttp://google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c