c++ - 在一组 27 个浮点值中选择中位数的最快代码 C/C++

Question

这是众所周知的选择算法。见 http://en.wikipedia.org/wiki/Selection_algorithm .

我需要它来找到一组 3x3x3 体素值的中值。由于体积由十亿体素组成，并且算法是递归的，所以最好快一点。 一般来说，可以预期值是比较接近的。

迄今为止我尝试过的最快的已知算法使用快速排序分区函数。我想知道有没有更快的。

我已经“发明”了一个使用两个堆的快 20% 的堆，但预期使用散列的一个更快。在实现此之前，我想知道是否已经存在 Blitz 快速解决方案。

我使用 float 这一事实并不重要，因为在反转符号位后它们可以被视为无符号整数。订单将被保留。

编辑:基准和源代码按照建议移到单独的答案中 戴维兰德曼。请参阅下面的 chmike 的答案。

编辑:Boojum 在下面引用了迄今为止最有效的算法，作为到 Fast Median and Bilateral Filtering 的链接。这篇论文现在是这个问题的答案。这种方法的第一个聪明的想法是使用基数排序，第二个是对共享大量像素的相邻像素进行中值搜索。

Answer 1

选择算法是线性时间(O(n))。在复杂性方面，你不能比线性时间做得更好，因为读取所有数据需要线性时间。所以你不可能做出更快的复杂性的东西。也许你有一些在某些输入上更快的常数因子？我怀疑这会产生很大的不同。

C++ 已经包含线性时间选择算法。为什么不直接使用呢？

std::vector<YourType>::iterator first = yourContainer.begin();
std::vector<YourType>::iterator last = yourContainer.end();
std::vector<YourType>::iterator middle = first + (last - first) / 2;
std::nth_element(first, middle, last); // can specify comparator as optional 4th arg
YourType median = *middle;

编辑:从技术上讲，这只是奇数长度容器的中位数。对于偶数长度之一，它将获得“上”中位数。如果您想要偶数长度的中位数的传统定义，您可能需要运行两次，对于 first + (last - first)/2 和 的两个“中间值”中的每一个运行一次first + (last - first)/2 - 1 然后平均它们或其他东西。