最快的code C / C ++，以一组27个浮点值选择位 [英] Fastest code C/C++ to select the median in a set of 27 floating point values

问题描述

这是众所周知的选择算法。看<一href="http://en.wikipedia.org/wiki/Selection_algorithm">http://en.wikipedia.org/wiki/Selection_algorithm.

This is the well know select algorithm. see http://en.wikipedia.org/wiki/Selection_algorithm.

我需要找到一套3x3x3的像素值的中值。由于卷是由一个十亿像素，算法是递归的，它最好是有点快。 通常，可以预期值相对接近。

I need it to find the median value of a set of 3x3x3 voxel values. Since the volume is made of a billion voxels and the algorithm is recursive, it better be a little bit fast. In general it can be expected that values are relatively close.

目前最快的算法，我已经尝试了迄今为止使用快速排序的分区功能。我想知道是否有一个更快的。

The fastest known algorithm I have tried out so far uses the quick sort partition function. I would like to know if there is a faster one.

我发明一个快20％的一种使用两个堆，但预期更快的一个使用的哈希值。实施这个之前，我想知道，如果一个闪电战快速的解决方案已经存在在那里。

I've "invented" a 20% faster one using two heaps, but expected an even faster one using a hash. Before implementing this, I'd like to know if a blitz fast solution already exist out there.

这是我用浮漂不应该的问题，因为他们可以反转符号位后，被视为无符号整数的事实。该命令将preserved。

The fact that I'm using floats shouldn't matter since they can be considered as unsigned integer after inverting the sign bit. The order will be preserved.

编辑：基准源$ C ​​$ C移动到一个单独的答案所建议的 戴维·兰德曼。请参阅下面的由chmike答案。

benchmark and source code moved into a separate answer as suggested by Davy Landman. See below for the answer by chmike.

修改：那么远低于被引用的Boojum为纽带，以快速中值的最有效的算法和双边滤波文件，该文件是现在这个问题的答案。这种方法的第一个聪明的想法是使用基数排序，二是要结合位搜索相邻的像素谁分享了很多像素的。

EDIT: The most efficient algorithm so far was referenced below by Boojum as a link to the Fast Median and Bilateral Filtering paper which is now the answer to this question. The first smart idea of this method is to use radix sort, the second is to combine median search of adjacent pixels who share a lot of pixels.

推荐答案

因为它听起来就像你在一个大阵的数据量进行中值滤波，你可能想看看在的Fast中位数从2006年SIGGRAPH该文章论述了2D图像处理双边滤波纸，但您可能能够适应算法的3D卷。如果不出意外，它可能给你如何退一步看问题从一个稍微不同的角度的一些想法。

Since it sounds like you're performing a median filter on a large array of volume data, you might want to take a look at the Fast Median and Bilateral Filtering paper from SIGGRAPH 2006. That paper deals with 2D image processing, but you might be able to adapt the algorithm for 3D volumes. If nothing else, it might give you some ideas on how to step back and look at the problem from a slightly different perspective.

这篇关于最快的code C / C ++，以一组27个浮点值选择位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！