c++ - C++中小数据集的高效中值计算

Question

我有很多(数十万，m)组 double d，~5-10 (n, constant small) 长。这些替身基本上是随机分布的。我需要得到每个集合的中位数:因为 m 非常大，我们需要非常快速地计算中位数……虽然这些集合非常小，所以我认为这将在选择如何做方面发挥重要作用中位数。我知道我可以使用 nth_element使用选择算法获得 O(n) 的中位数，我知道我不会在复杂性上击败它。但是，由于常量 n 很小，我可能正在寻找开销最小的方法。

我发现了很多不同的方法来计算中位数(如下)，但如果有人知道这里使用的“正确”方法，我只是好奇。

Min max heaps (O(n) 构建时间，持续访问，可能开销太大)

This question from 2010这可能已经过时(新的 STL/Boost 代码可能已经实现了这些东西)，也更多地关注时间复杂度而不是开销。

Answer 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

编辑 - 好的，它也被引用 in this answer too