問題タブ [median-of-medians]

(注: この例では、配列を 5 つの要素を含むサブ配列に分割しています)

median-of-medians アルゴリズムは n 入力配列を floor(n/5) グループに分割し、追加のグループを含む (n)mod5 要素を使用してから、並べ替えられた各グループの中央値要素 (3 番目の要素) を見つけることを理解しています。 5 つの要素を持つグループ) など。

私の質問は、グループの 1 つに 2 つまたは 4 つの要素がある場合、どの要素がそのグループの中央値として選択されるかということです (グループが既にソートされていると仮定します)。

shapeと typeのnumpy配列を想定します。の行は、要素ごとの平均の中央値計算を通過する必要があります。具体的には、行インデックスは「バケット」に分割され、それぞれにそのようなインデックスが含まれます。次に、各バケット内で平均を計算し、結果の平均全体で最終的な中央値の計算を行います。Xm x nfloat64Xmbm/b

それを明確にする例は

このプログラムは、インデックスを等分に分割し、配列が 2D 配列であるため、b除算の場合は問題なく動作します。mnp.array_split()buckets

ただし、 をb割らないとうまくいきませんm。その場合、np.array_split()は引き続きバケットに分割されますbが、サイズが等しくないため、私の目的には問題ありません。たとえばb = 3、インデックス {0,1,...,9} を [0 1 2 3]、[4 5 6]、および [7 8 9] に分割する場合。これらの配列は互いに積み重ねることができないため、配列bucketsは 2D 配列ではなく、インデックスに使用できませんX_bucketed。

サイズが等しくないバケットに対してこれを機能させるにはどうすればよいですか。つまり、プログラムに各バケット内の平均を (サイズに関係なく) 計算させてから、バケット全体の中央値を計算させるにはどうすればよいですか?

マスクされた配列を完全に把握できず、ここで使用できるかどうかわかりません。