РЕДАКТИРОВАТЬ: я должен извиниться. Код ниже был НЕПРАВИЛЬНЫМ. У меня есть фиксированный код, но мне нужно найти компилятор 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: полная сортировка последовательности с использованием сортировки кучи и выбора среднего значения. Наивная реализация с использованием индексного доступа.
Быстрая сортировка: полная последовательность сортировки по месту с использованием быстрой сортировки и выбора среднего значения. Наивная реализация с использованием индексного доступа.
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 с и stdDev 0,159537 с теми же 1000 случайными последовательностями. Таким образом, HeapMedian3 в 33 раза быстрее, чем функция nth_element stl. Каждое возвращаемое медианное значение проверяется по медианному значению, возвращенному heapSort, и все они совпадают. Я сомневаюсь, что метод, использующий хэш, может быть значительно быстрее.
EDIT 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;
}
}
}
}