1

我有很多（数十万，m）组双打 d，~5-10（n，常数小）长。这些双打基本上是随机分布的。我需要得到每组的中位数：因为 m 非常大，我们需要很快地计算出中位数......虽然这些组非常小，所以我认为这将在选择如何做时发挥重要作用中位数。我知道我可以使用nth_element通过选择算法获得 O(n) 中的中位数，我知道我不会在复杂性上击败它。但是，由于常数 n 很小，我可能正在寻找开销最小的方法。

我找到了一堆不同的方法来做中位数（下），但如果有人知道在这里使用的“正确”方法，我只是好奇。

最小最大堆（O(n) 构建时间，持续访问，可能开销太大）

这个 2010 年的问题可能已经过时（新的 STL/Boost 代码可能已经实现了这些东西），也更关注时间复杂度而不是开销。

4

2 回答 2

1

这可能无法很好地适应您的数据大小，但它是我找到的一个代码片段（不记得在哪里）并在我的图像处理函数中使用以获得 9 个无符号字符像素的中位数。

// 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 回答