Самый быстрый код C/C++ для выбора медианы в ряде 27 значений с плавающей точкой

Если есть 3x3x3 = 27 возможных значений (если так, почему поплавки?), Можете ли вы создать массив из 27 элементов и считать каждую возможность за один проход данных?

Я держу пари, что вы можете рассчитать их для нулевой стоимости - в отдельном потоке при загрузке с диска (или как они сгенерировано).

Что я действительно говорю, так это то, что «скорость» не будет происходить из-за небольшого сложения, потому что 27 значений недостаточно, чтобы нотация Big O была реальным фактором.

Если вы хотите увидеть алгоритмы, посмотрите книги Дональда Кнута.

PS. Если вы думаете, что изобрели что-то лучшее, то вы должны показать, что сложность аналогична или лучше сложности известных алгоритмов. Что для вариаций, основанных на ведре и основании, равно O (n), с другой стороны, быстрая сортировка - только O (n.log (n)). Метод, который на 20% быстрее, по-прежнему O (n.log (n)), пока вы не сможете показать алгоритм: -)

Я полагаю, что вам лучше всего взять существующий алгоритм сортировки и попытаться выяснить, можете ли вы его адаптировать так, чтобы набор не нуждался в полной сортировке. Для определения медианы вам потребуется не более половины отсортированных значений, достаточно будет либо нижней, либо верхней половины:

original:              | 5 | 1 | 9 | 3 | 3 |
sorted:                | 1 | 3 | 3 | 5 | 9 |
lower half sorted:     | 1 | 3 | 3 | 9 | 5 |
higher half sorted:    | 3 | 1 | 3 | 5 | 9 |

Другая половина будет набором несортированных значений, которые просто разделяют свойство быть больше / меньше или равны наибольшее / наименьшее отсортированное значение.

Но у меня нет готового алгоритма для этого, это просто идея того, как вы могли бы сократить путь при сортировке.

+1 для всех, кто упомянул nth_element, но этот вид кода - то, где рукописный алгоритм лучше, чем STL, потому что вы хотите сгенерировать наиболее эффективный код для этого одного компилятора, работающего на одном CPU с конкретным набором данных. Например, для некоторой комбинации CPU / компилятор std :: swap (int, int) может быть медленнее, чем рукописный своп с использованием XOR (прежде чем ответить, я знаю, что это, вероятно, верно 20 лет назад, но не больше). Иногда производительность достигается за счет написания кода ассемблера, специфичного для вашего процессора. Если вы планируете использовать потоковые процессоры GPU, возможно, вам придется соответствующим образом спроектировать свой алгоритм.

Вы упомянули, что использовали 2 кучи и следите за медианой при вставке. Это то, что я сделал некоторое время назад в проекте. Я изменил массив на месте и использовал только одну кучу. Я не мог придумать более быстрый алгоритм, но я хотел бы предупредить вас об использовании памяти, в частности, кэш-памяти процессора. Вы хотите быть осторожным с доступом к памяти. Кэш-память ЦП переставляется на страницу, поэтому вы хотите, чтобы ваш алгоритм касался памяти, которая находится близко друг к другу, чтобы минимизировать потерю кэш-памяти ЦП.

Алгоритм выбора - линейное время (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;

Редактировать: Технически, это всего лишь медиана для контейнера нечетной длины. Для одной четной длины он получит «верхнюю» медиану. Если вам нужно традиционное определение медианы для четной длины, вам, возможно, придется выполнить его дважды, по одному для каждой из двух «середин».

The most likely algorithm to use in your first attempt is just nth_element; it pretty much gives you what you want directly. Just ask for the 14th element.

On your second attempt, the goal is to take advantage of the fixed data size. You do not wnat to allocate any memory at all duing your algorithm. So, copy your voxel values to a pre-allocated array of 27 elements. Pick a pivot, and copy it to the middle of a 53 element array. Copy the remaining values to either side of the pivot. Here you keep two pointers (float* left = base+25, *right=base+27). There are now three possibilities: the left side is larger, the right side is larger, or the both have 12 elements. The last case is trivial; your pivot is the median. Otherwise, call nth_element on either the left side or the right side. The exact value of Nth depends on how many values were larger or smaller than the pivot. For instance, if the division is 12/14, you need the smallest element bigger than the pivot, so Nth=0, and if the division was 14/12, you need the biggest element smaller the pivot, so Nth=13. The worst cases are 26/0 and 0/26, when your pivot was an extreme, but those happen only in 2/27th of all cases.

The third improvement (or the first, if you have to use C and do not have nth_element) replaces nth_element entirely. You still have the 53 element array, but this time you fill it directly from the voxel values (saving you an interim copy into a float[27]). The pivot in this first iteration is just voxel[0][0][0]. For subsequent iterations, you use a second pre-allocated float[53] (easier if both are the same size) and copy floats between the two. The basic iteration step here is still: copy the pivot to the middle, sort the rest to the left and the right. At the end of each step, you'll know whether the median is smaller or larger than the current pivot, so you can discard the floats bigger or smaller than that pivot. Per iteration, this eliminates between 1 and 12 elements, with an average of 25% of the remaining.

The final iteration, if you still need more speed, is based on the observation that most of your voxels overlap significantly. You pre-calculate for every 3x3x1 slice the median value. Then, when you need an initial pivot for your 3x3x3 voxel cube, you take the median of the the three. You know a priori that there are 9 voxels smaller and 9 voxels larger than that median of medians (4+4+1). So, after the first pivotting step, the worst cases are a 9/17 and a 17/9 split. So, you'd only need to find the 4th or 13th element in a float[17], instead of the 12th or 14th in a float[26].

---

Background: The idea of copying first a pivot and then the rest of a float[N] to a float[2N-1], using left and right pointers is that you fill a float[N] subarray around the pivot, with all elements smaller than the pivot to the left (lower index) and higher to the right (higher index). Now, if you want the Mth element, you might find yourself lucky and have M-1 elements smaller than the pivot, in which case the pivot is the element you need. If there are more than (M-1) elements smaller than the pivot, the Mth element is amongst them, so you can discard the pivot and anything bigger than the pivot, and seacrh for the Mth element in all the lower values. If there are less than (M-1) elements smaller than the pivot, you're looking for a value higher than the pivot. So, you'll discard the pivot and anything smaller than it. Let the number of elements less than the pivot, i.e. to the left of the pivot be L. In the next iteration, you want the (M-L-1)th element of the (N-L-1)floats that are bigger than the pivot.

This kind of nth_element algorithm is fairly efficient because most of the work is spent copying floats between two small arrays, both of which will be in cache, and because your state is most of the time represented by 3 pointers (source pointer, left destination pointer, right destination pointer).

To show the basic code:

float in[27], out[53];
float pivot = out[26] = in[0];     // pivot
float* left = out+25, right = out+27
for(int i = 1; i != 27; ++1)
if((in[i]<pivot)) *left-- = in[i] else *right++ = in[i];
// Post-condition: The range (left+1, right) is initialized.
// There are 25-(left-out) floats <pivot and (right-out)-27 floats >pivot

Новая книга Алексея Степанова Элементы программирования подробно рассказывает о поиске статистики заказов с использованием минимального числа средних сравнений при минимизации накладных расходов времени выполнения. К сожалению, значительный объем кода необходим только для вычисления медианы из 5 элементов, и даже в этом случае он дает в качестве проекта поиск альтернативного решения, которое использует долю сравнения в среднем меньше, поэтому я бы не стал мечтать о его расширении. рамки для нахождения медианы 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

Значительный объем кода необходим только для того, чтобы вычислить медиану из 5 элементов, и даже тогда он дает в качестве проекта поиск альтернативного решения, которое использует долю сравнения в среднем меньше, поэтому я бы не стал мечтать о расширении этой инфраструктуры до найти медиану из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

Значительный объем кода необходим только для того, чтобы вычислить медиану из 5 элементов, и даже тогда он дает в качестве проекта поиск альтернативного решения, которое использует долю сравнения в среднем меньше, поэтому я бы не стал мечтать о расширении этой инфраструктуры до найти медиану из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

и даже тогда он приводит в качестве проекта нахождение альтернативного решения, которое использует долю сравнения в среднем меньше, поэтому я бы не мечтал о расширении этой основы для нахождения медианы из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

и даже тогда он приводит в качестве проекта нахождение альтернативного решения, которое использует долю сравнения в среднем меньше, поэтому я бы не мечтал о расширении этой основы для нахождения медианы из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

поэтому я не мечтал бы расширить эту структуру, чтобы найти медиану из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

поэтому я не мечтал бы расширить эту структуру, чтобы найти медиану из 27 элементов. И книга даже не будет доступна до 15 июня 2009 года. Дело в том, что, поскольку это проблема фиксированного размера, существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм выполняется не один раз в отдельности, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

Существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм запускается не один раз, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

Существует метод прямого сравнения, который доказуемо оптимален.

Кроме того, существует тот факт, что этот алгоритм запускается не один раз, а скорее много раз, и между большинством прогонов изменится только 9 из 27 значений. Это означает, что в теории часть работы уже сделана. Однако я не слышал о каких-либо алгоритмах медианной фильтрации при обработке изображений, которые бы использовали этот факт.

Как уже говорили другие: возвращаемое значение, а не выходное значение.

Могу ли я порекомендовать вам книгу "Руководство по разработке структуры" (2-е изд)? Страницы 184-185 раскрывают причины, по которым следует избегать использования параметров. Вся книга будет направлять вас в правильном направлении по всем видам проблем кодирования .NET.

В сочетании с Руководствами по проектированию платформы используется инструмент статического анализа FxCop. Вы найдете это на сайтах Microsoft для бесплатной загрузки. Запустите это на своем скомпилированном коде и посмотрите, что он говорит. Если он жалуется на сотни и сотни вещей ... не паникуйте! Посмотрите спокойно и внимательно на то, что говорится о каждом конкретном случае. Не спешите исправлять вещи как можно скорее. Учитесь на том, что это говорит вам. Вы попадете на путь мастерства.

как вы наверняка знаете

Поэтому ваш подход попробовать пару из них кажется достаточно хорошим. И да, быстрая сортировка должна быть довольно быстрой. Если вы этого не сделали, вы можете попробовать сортировку вставок, которая часто работает лучше для небольших наборов данных. Это сказало, просто выбирайте алгоритм сортировки, который делает работу достаточно быстро. Как правило, вы не получите в 10 раз быстрее, просто выбрав «правильный» алгоритм.

Чтобы получить существенное ускорение, лучше часто использовать больше структур. Некоторые идеи, которые работали для меня в прошлом с крупномасштабными проблемами:

• Можете ли вы эффективно предварительно рассчитать при создании вокселей и хранить 28 вместо 27 поплавков?

• Достаточно ли приблизительное решение? Если Вы можете попробовать сортировку вставками, которая часто работает лучше для небольших наборов данных. Это сказало, просто выбирайте алгоритм сортировки, который делает работу достаточно быстро. Как правило, вы не получите в 10 раз быстрее, просто выбрав «правильный» алгоритм.

  Чтобы получить существенное ускорение, лучше часто использовать больше структур. Некоторые идеи, которые работали для меня в прошлом с крупномасштабными проблемами:

  • Можете ли вы эффективно предварительно рассчитать при создании вокселей и хранить 28 вместо 27 поплавков?

  • Достаточно ли приблизительное решение? Если Вы можете попробовать сортировку вставками, которая часто работает лучше для небольших наборов данных. Это сказало, просто выбирайте алгоритм сортировки, который делает работу достаточно быстро. Как правило, вы не получите в 10 раз быстрее, просто выбрав «правильный» алгоритм.

    Чтобы получить существенное ускорение, лучше часто использовать больше структур. Некоторые идеи, которые работали для меня в прошлом с крупномасштабными проблемами:

    • Можете ли вы эффективно предварительно рассчитать при создании вокселей и хранить 28 вместо 27 поплавков?

    • Достаточно ли приблизительное решение? Если Некоторые идеи, которые работали для меня в прошлом с крупномасштабными проблемами:

      • Можете ли вы эффективно предварительно рассчитать при создании вокселей и хранить 28 вместо 27 поплавков?

      • Достаточно ли приблизительное решение? Если Некоторые идеи, которые работали для меня в прошлом с крупномасштабными проблемами:

        • Можете ли вы эффективно предварительно рассчитать при создании вокселей и хранить 28 вместо 27 поплавков?

        • Достаточно ли приблизительное решение? Если так что, просто посмотрите на медиану, скажем, 9 значения, так как "в целом это может быть Ожидается, что значения относительно закрыть. "Или вы можете заменить его среднее до тех пор, пока значения относительно близко.

        • Вам действительно нужна медиана для всех? миллиарды вокселей? Может быть, у вас есть легко проверить, нужно ли вам Медиана, а затем может только рассчитать для соответствующего подмножества.

        • Если больше ничего не помогает: посмотрите на ASM-код, который генерирует компилятор. Вы могли бы написать код asm, который существенно быстрее (например, делая все вызовы с использованием регистров).

        Редактировать: Для чего бы я ни приложил (частично) код вставки, указанный в комментарии ниже (полностью не проверено). Если numbers [] является массивом размером N , и вы хотите, чтобы наименьшее число P было отсортировано в начале массива, вызовите partal_insertionsort < N, P, число с плавающей запятой> (числа); . Следовательно, если вы позвоните partal_insertionsort <27, 13, float> (числа); , числа [13] будет содержать медиану. Чтобы получить дополнительную скорость, вам также придется развернуть цикл while. Как уже говорилось выше, чтобы получить очень быстро, вы должны использовать свои знания о данных (например, данные уже частично отсортированы? Знаете ли вы свойства распределения данных? Я думаю, вы получаете дрейф).

        template <long i> class Tag{};
        
        template<long i, long N, long P, typename T>
        inline void partial_insertionsort_for(T a[], Tag<N>, Tag<i>)
        {   long j = i <= P+1 ? i : P+1;  // partial sort
            T temp = a[i];
            a[i] = a[j];       // compiler should optimize this away where possible
            while(temp < a[j - 1] && j > 0)
            { a[j] = a[j - 1];
              j--;}
            a[j] = temp;
            partial_insertionsort_for<i+1,N,P,T>(a,Tag<N>(),Tag<i+1>());}
        
        template<long i, long N, long P, typename T>
        inline void partial_insertionsort_for(T a[], Tag<N>, Tag<N>){}
        
        template <long N, long P, typename T>
        inline void partial_insertionsort(T a[])
         {partial_insertionsort_for<0,N,P,T>(a, Tag<N>(), Tag<0>());}
        

You might want to have a look at Knuth's Exercise 5.3.3.13. It describes an algorithm due to Floyd that finds the median of n elements using (3/2)n+O(n^(2/3) log n) comparisons, and the constant hidden in the O(·) seems not to be too large in practice.

РЕДАКТИРОВАТЬ: Я должен извиниться. Код ниже был НЕПРАВИЛЬНЫМ. У меня есть фиксированный код, но мне нужно найти компилятор icc , чтобы повторить измерения.

Результаты тестов алгоритмов, рассмотренных до сих пор

Протокол и краткое описание алгоритмов см. Ниже. Первое значение - это среднее время (секунды) для 200 различных последовательностей, а второе - stdDev.

HeapSort     : 2.287 0.2097
QuickSort    : 2.297 0.2713
QuickMedian1 : 0.967 0.3487
HeapMedian1  : 0.858 0.0908
NthElement   : 0.616 0.1866
QuickMedian2 : 1.178 0.4067
HeapMedian2  : 0.597 0.1050
HeapMedian3  : 0.015 0.0049 <-- best

Протокол: сгенерируйте 27 случайных чисел с использованием случайных битов, полученных из rand (). Примените каждый алгоритм 5 миллионов раз подряд (включая предыдущее копирование массива) и вычислите среднее значение и stdDev для 200 случайных последовательностей. Код C ++, скомпилированный с помощью icc -S -O3 и работающий на Intel E8400 с 8 ГБ памяти DDR3.

Алгоритмы:

HeapSort: полная сортировка последовательности с использованием сортировки кучи и выбора среднего значения. Наивная реализация с использованием индексного доступа.

QuickSort: полная последовательность сортировки с использованием быстрой сортировки и выбора среднего значения. Наивная реализация с использованием индексного доступа.

QuickMedian1: алгоритм быстрого выбора с заменой. Наивная реализация с использованием доступа по индексу.

HeapMedian1: на месте метод сбалансированной кучи с предварительным обменом. Наивная реализация с использованием доступа через индекс.

NthElement: использует алгоритм STL nth_element. Данные копируются в вектор с использованием memcpy (vct.data (), rndVal, ...);

QuickMedian2: использует алгоритм быстрого выбора с указателями и копирование в два буфера, чтобы избежать подкачки. Основано на предложении MSalters.

HeapMedian2: вариант моего изобретенного алгоритма с использованием двойных куч с общими головками. Левая куча имеет наибольшее значение как голова, правая имеет наименьшее значение как голова. Инициализируйте с первым значением в качестве общей головы и первым предположением среднего значения. Добавляйте последующие значения в левую кучу, если она меньше, чем head, иначе в правую кучу, пока одна из куч не заполнится. Он полон, когда содержит 14 значений. Тогда рассмотрим только полную кучу. Если это правильная куча, для всех значений больше, чем голова, выдвиньте голову и вставьте значение. Игнорируйте все другие ценности. Если это левая куча, для всех значений, меньших, чем голова, выдвиньте голову и вставьте ее в кучу. Игнорируйте все другие ценности. Когда все значения получены, общая голова является медианным значением. Он использует целочисленный индекс в массиве. Версия с использованием указателей (64 бита) оказалась почти в два раза медленнее (~ 1 с).

HeapMedian3: тот же алгоритм, что и HeapMedian2, но оптимизированный. Он использует индекс без знака, избегает подмены значений и других мелочей. Средние значения и значения stdDev вычисляются для более 1000 случайных последовательностей. Для nth_element я измерил 0. 508 с и стандартное отклонение 0,159537 с теми же 1000 случайных последовательностей. Таким образом, HeapMedian3 в 33 раза быстрее функции nth_element stl. Каждое возвращенное медианное значение проверяется по медианному значению, возвращенному heapSort, и все они совпадают. Я сомневаюсь, что метод, использующий хэш, может быть значительно быстрее.

РЕДАКТИРОВАТЬ 1: Этот алгоритм может быть дополнительно оптимизирован. Первая фаза, где элементы отправляются в левой или правой куче на основе результата сравнения, не требует куч. Достаточно просто добавить элементы к двум неупорядоченным последовательностям. Фаза 1 останавливается, как только одна последовательность заполнена, что означает, что она содержит 14 элементов (включая медианное значение). Второй этап начинается с накапливания полной последовательности, а затем продолжается, как описано в алгоритме HeapMedian3. Я предоставлю новый код и тест как можно скорее.

РЕДАКТИРОВАТЬ 2: я реализовал и протестировал оптимизированный алгоритм. Но нет никакой значительной разницы в производительности по сравнению с heapMedian3. Это даже немного медленнее в среднем. Показанные результаты подтверждены. Там может быть с гораздо большими наборами. Также обратите внимание, что я просто выбираю первое значение в качестве начального среднего значения. Как и предполагалось, можно извлечь пользу из того факта, что мы ищем медианное значение в «перекрывающихся» наборах значений. Использование алгоритма медианы медианы помогло бы выбрать более правильное предположение о начальном медианном значении.

---

Исходный код HeapMedian3

// return the median value in a vector of 27 floats pointed to by a
float heapMedian3( float *a )
{
   float left[14], right[14], median, *p;
   unsigned char nLeft, nRight;

   // pick first value as median candidate
   p = a;
   median = *p++;
   nLeft = nRight = 1;

   for(;;)
   {
       // get next value
       float val = *p++;

       // if value is smaller than median, append to left heap
       if( val < median )
       {
           // move biggest value to the heap top
           unsigned char child = nLeft++, parent = (child - 1) / 2;
           while( parent && val > left[parent] )
           {
               left[child] = left[parent];
               child = parent;
               parent = (parent - 1) / 2;
           }
           left[child] = val;

           // if left heap is full
           if( nLeft == 14 )
           {
               // for each remaining value
               for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
               {
                   // get next value
                   val = *p++;

                   // if value is to be inserted in the left heap
                   if( val < median )
                   {
                       child = left[2] > left[1] ? 2 : 1;
                       if( val >= left[child] )
                           median = val;
                       else
                       {
                           median = left[child];
                           parent = child;
                           child = parent*2 + 1;
                           while( child < 14 )
                           {
                               if( child < 13 && left[child+1] > left[child] )
                                   ++child;
                               if( val >= left[child] )
                                   break;
                               left[parent] = left[child];
                               parent = child;
                               child = parent*2 + 1;
                           }
                           left[parent] = val;
                       }
                   }
               }
               return median;
           }
       }

       // else append to right heap
       else
       {
           // move smallest value to the heap top
           unsigned char child = nRight++, parent = (child - 1) / 2;
           while( parent && val < right[parent] )
           {
               right[child] = right[parent];
               child = parent;
               parent = (parent - 1) / 2;
           }
           right[child] = val;

           // if right heap is full
           if( nRight == 14 )
           {
               // for each remaining value
               for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
               {
                   // get next value
                   val = *p++;

                   // if value is to be inserted in the right heap
                   if( val > median )
                   {
                       child = right[2] < right[1] ? 2 : 1;
                       if( val <= right[child] )
                           median = val;
                       else
                       {
                           median = right[child];
                           parent = child;
                           child = parent*2 + 1;
                           while( child < 14 )
                           {
                               if( child < 13 && right[child+1] < right[child] )
                                   ++child;
                               if( val <= right[child] )
                                   break;
                               right[parent] = right[child];
                               parent = child;
                               child = parent*2 + 1;
                           }
                           right[parent] = val;
                       }
                   }
               }
               return median;
           }
       }
   }
} 

Сеть сортировки, созданная с использованием алгоритма Бозе-Нельсона, найдет медианное значение напрямую без циклов / рекурсии с использованием 173 сравнений. Если у вас есть возможность выполнять сравнения параллельно, такие как использование векторно-арифметических инструкций, вы можете сгруппировать сравнения всего в 28 параллельных операций.

Если вы уверены, что числа с плавающей запятой нормализованы, а не ( qs) NaN, то вы можете использовать целочисленные операции для сравнения чисел с плавающей запятой IEEE-754, которые могут работать более эффективно на некоторых процессорах.

Прямое преобразование этой сети сортировки в C (gcc 4.2) дает наихудший случай 388 тактовых циклов. на моем Core i7.

Сортировочные сети