1

double d のセットが多数 (数十万、m) あり、長さは ~5-10 (n、constant small ) です。これらの double は、基本的にランダムに分散されます。各セットの中央値を取得する必要があります: m が非常に大きいため、中央値をかなり迅速に計算する必要があります...これらのセットはかなり小さいですが、方法を選択する際に重要な役割を果たすと思います中央値。nth_elementを使用して、選択アルゴリズムを使用して O(n) の中央値を取得できることはわかっていますが、これは複雑ではありません。ただし、定数 n が小さいため、単純にオーバーヘッドが最も小さい方法を探しているのでしょう。

中央値を実行するさまざまな方法を見つけましたが（以下）、ここで使用する「正しい」方法を誰かが知っていれば、単なる好奇心です。

最小最大ヒープ(O(n) ビルド時間、一定のアクセス、おそらくオーバーヘッドが多すぎる)

This question from 2010 which may be out of date (新しい STL/Boost コードは既にこのようなものを実装している可能性があります) も、オーバーヘッドよりも時間の複雑さに重点を置いています。

4

2 に答える 2

1

これはデータ サイズにうまく対応できない場合がありますが、これは私が見つけた (場所を思い出せない) コード スニペットであり、画像処理関数で使用して 9 個の unsigned char ピクセルの中央値を取得します。

// optimised median search on 9 values
#define PIX_SWAP(a, b) { unsigned char uTemp = (a); (a) = (b); (b) = uTemp; }
#define PIX_SORT(a, b) { if ((a) > (b)) PIX_SWAP((a), (b)); }

unsigned char GetMedian9(unsigned char *pNine)
{
    // nb - this is theoretically the fastest way to get the median of 9 values
    PIX_SORT(pNine[1], pNine[2]); PIX_SORT(pNine[4], pNine[5]); PIX_SORT(pNine[7], pNine[8]); 
    PIX_SORT(pNine[0], pNine[1]); PIX_SORT(pNine[3], pNine[4]); PIX_SORT(pNine[6], pNine[7]); 
    PIX_SORT(pNine[1], pNine[2]); PIX_SORT(pNine[4], pNine[5]); PIX_SORT(pNine[7], pNine[8]); 
    PIX_SORT(pNine[0], pNine[3]); PIX_SORT(pNine[5], pNine[8]); PIX_SORT(pNine[4], pNine[7]); 
    PIX_SORT(pNine[3], pNine[6]); PIX_SORT(pNine[1], pNine[4]); PIX_SORT(pNine[2], pNine[5]); 
    PIX_SORT(pNine[4], pNine[7]); PIX_SORT(pNine[4], pNine[2]); PIX_SORT(pNine[6], pNine[4]); 
    PIX_SORT(pNine[4], pNine[2]); return(pNine[4]);
}

#undef PIX_SWAP
#undef PIX_SORT

編集- わかりました、この回答でも参照されています

于 2013-03-27T16:26:14.433 に答える
0

std::set の場合 (BoBTFish に応答しませんでした)、既にソートされています。したがって、n/2 まで繰り返すことで中央値が得られます。これは、常に O(n) よりも優れているか、等しいです。通常は O(ld n) である必要があります。ここでは n 番目の要素は役に立ちません。

于 2013-03-27T17:49:34.153 に答える