Самый быстрый вид массива с фиксированной длиной 6 int
Отвечая на другой вопрос переполнения стека ( этот), я наткнулся на интересную подзадачу. Какой самый быстрый способ сортировки массива в 6 дюймов?
Как вопрос очень низкого уровня:
- мы не можем предполагать, что библиотеки доступны (и сам вызов имеет свою стоимость), только простой C
- чтобы избежать опустошения конвейера команд (который имеет очень высокую стоимость), мы, вероятно, должны минимизировать переходы, скачки и любые другие виды прерывания потока управления (например, те, которые скрыты за точками последовательности в
&&или же||). - пространство ограничено, и минимизация регистров и использование памяти является проблемой, в идеале сортировка на месте, вероятно, лучше всего.
На самом деле этот вопрос - своего рода гольф, цель которого не в том, чтобы минимизировать длину источника, а во время выполнения. Я называю это "кодом Зенинга", как он используется в названии книги "Оптимизация кода Zen " Майкла Абраша и ее продолжений.
Что касается того, почему это интересно, есть несколько слоев:
- пример прост и легок для понимания и измерения, не требующий много навыков
- это показывает эффекты выбора хорошего алгоритма для проблемы, но также эффекты компилятора и основного оборудования.
Вот моя эталонная (наивная, не оптимизированная) реализация и мой набор тестов.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}
Необработанные результаты
Поскольку число вариантов становится большим, я собрал их все в наборе тестов, который можно найти здесь. Благодаря Кевину Сток, используемые тесты немного менее наивны, чем показанные выше. Вы можете скомпилировать и выполнить его в своей среде. Мне весьма интересно поведение на разных целевых архитектурах / компиляторах. (Хорошо, ребята, вставьте это в ответы, я буду +1 каждому вкладчику нового набора результатов).
Я дал ответ Даниэлю Штутцбаху (для игры в гольф) год назад, поскольку он был источником самого быстрого решения в то время (сортировка сетей).
Linux 64 бит, gcc 4.6.1 64 бит, Intel Core 2 Duo E8400, -O2
- Прямой вызов функции библиотеки qsort: 689,38
- Наивная реализация (вставка сортировки): 285.70
- Сортировка вставок (Даниэль Штутцбах): 142,12
- Развернутая сортировка вставок: 125.47
- Порядок ранга: 102.26
- Ранг Порядок с регистрами: 58.03
- Сортировка сетей (Даниэль Штутцбах): 111,68
- Сортировка сетей (Paul R): 66,36
- Сортировка сетей 12 с быстрой заменой: 58,86
- Сортировка сетей 12 переупорядоченный своп: 53,74
- Сортировка сетей 12 переупорядочен Простая замена: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой V2: 33,63
- Сортированный пузырь (Паоло Бонзини): 48,85
- Развернутая сортировка вставок (Паоло Бонзини): 75,30
Linux 64 бит, gcc 4.6.1 64 бит, Intel Core 2 Duo E8400, -O1
- Прямой вызов функции библиотеки qsort: 705,93
- Наивная реализация (вставка сортировки): 135.60
- Сортировка вставок (Даниэль Штутцбах): 142,11
- Развернутая сортировка вставок: 126,75
- Порядок ранга: 46.42
- Порядок ранжирования с регистрами: 43,58
- Сортировка сетей (Даниэль Штутцбах): 115,57
- Сортировка сетей (Paul R): 64,44
- Сортировка сетей 12 с быстрой заменой: 61,98
- Сортировка сетей 12 переупорядоченный своп: 54,67
- Сортировка сетей 12 переупорядочен Простая замена: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой: 31,24
- Переупорядоченная сеть сортировки с быстрой заменой V2: 33,07
- Сортированный пузырь (Паоло Бонзини): 45,79
- Развернутая сортировка вставок (Паоло Бонзини): 80,15
Я включил результаты как -O1, так и -O2, потому что неожиданно для нескольких программ O2 менее эффективен, чем O1. Интересно, какая специфическая оптимизация имеет этот эффект?
Комментарии к предлагаемым решениям
Сортировка вставок (Даниэль Штутцбах)
Как и ожидалось, минимизация веток действительно хорошая идея.
Сортировка сетей (Даниэль Штутцбах)
Лучше, чем сортировка вставок. Я задавался вопросом, не был ли главный эффект от избегания внешнего цикла. Я проверил развернутой сортировкой вставки, чтобы проверить, и действительно мы получаем примерно одинаковые цифры (код здесь).
Сортировка сетей (Пол R)
Лучшее пока. Фактический код, который я использовал для тестирования, находится здесь. Пока не знаю, почему это почти в два раза быстрее, чем в другой сети сортировки. Передача параметров? Быстро макс?
Сортировка сетей 12 SWAP с быстрой заменой
По предложению Даниэля Штутцбаха, я объединил его сеть сортировки с 12 свопами и быстрый обмен без ответвлений (код здесь). Это действительно быстрее, лучше всего с небольшим запасом (примерно 5%), как и следовало ожидать, используя 1 своп меньше.
Интересно также отметить, что обмен без ответвлений, по-видимому, намного (в 4 раза) менее эффективен, чем простой, используемый в архитектуре PPC.
Вызов библиотеки qsort
Чтобы дать еще одну контрольную точку, я также попытался, как предлагалось, просто вызвать библиотеку qsort (код здесь). Как и ожидалось, он намного медленнее: в 10-30 раз медленнее... как стало очевидно с новым набором тестов, основная проблема, похоже, заключается в начальной загрузке библиотеки после первого вызова, и она не так плохо сравнивается с другими версия. Это только в 3-20 раз медленнее в моем Linux. В некоторых архитектурах, используемых для тестирования другими, это кажется даже быстрее (я действительно удивлен тем, что библиотека qsort использует более сложный API).
Порядок ранга
Рекс Керр предложил другой совершенно другой метод: для каждого элемента массива вычисляют непосредственно его конечную позицию. Это эффективно, потому что порядок вычисления не требует ветвления. Недостаток этого метода состоит в том, что он занимает в три раза больше памяти массива (одна копия массива и переменные для хранения ранговых порядков). Результаты производительности очень удивительны (и интересны). На моей эталонной архитектуре с 32-битной ОС и Intel Core2 Quad E8300 число циклов было чуть ниже 1000 (как в случае сортировки сетей с разветвленной ветвью). Но когда он был скомпилирован и выполнен на моем 64-битном компьютере (Intel Core2 Duo), он работал намного лучше: он стал самым быстрым до сих пор. Я наконец выяснил истинную причину. Мой 32-битный бокс использует gcc 4.4.1 и мой 64-битный бокс gcc 4.4.3, и последний, кажется, намного лучше оптимизирует этот конкретный код (для других предложений было очень мало различий).
обновление:
Как видно из опубликованных выше рисунков, этот эффект все еще усиливался в более поздних версиях gcc, и ранговый порядок стал в два раза быстрее, чем в любой другой альтернативе.
Сортировка сетей 12 с переупорядоченным свопом
Удивительная эффективность предложения Rex Kerr с gcc 4.4.3 заставила меня задуматься: как может программа, использующая в 3 раза больше памяти, работать быстрее, чем сети без ветвей сортировки? Моя гипотеза состояла в том, что у него было меньше зависимостей типа чтения после записи, что позволяло лучше использовать планировщик суперскалярных команд в x86. Это дало мне идею: изменить порядок перестановок, чтобы минимизировать зависимости чтения после записи. Проще говоря: когда вы делаете SWAP(1, 2); SWAP(0, 2); Вы должны дождаться завершения первого обмена, прежде чем выполнять второй, потому что оба имеют доступ к общей ячейке памяти. Когда вы делаете SWAP(1, 2); SWAP(4, 5);процессор может выполнять оба параллельно. Я попробовал, и все работает как положено, сортировочные сети работают примерно на 10% быстрее.
Сортировка сетей 12 с помощью простого обмена
Через год после первоначального поста Стейнар Х. Гандерсон предложил не пытаться перехитрить компилятор и сохранить простой код подкачки. Это действительно хорошая идея, поскольку полученный код работает примерно на 40% быстрее! Он также предложил обмен, оптимизированный вручную с использованием встроенного кода сборки x86, который может сэкономить еще несколько циклов. Самое удивительное (в нем говорится о психологии программиста), что год назад никто из бывших в употреблении не пробовал эту версию свопинга. Код, который я использовал для тестирования, находится здесь. Другие предлагали другие способы написания быстрого свопинга на C, но он дает те же характеристики, что и простой с приличным компилятором.
"Лучший" код теперь выглядит следующим образом:
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
Если мы считаем, что наш набор тестов (и, да, он довольно плохой, просто преимущество в том, что он короткий, простой и легкий для понимания того, что мы измеряем), среднее число циклов полученного кода для одного вида будет ниже 40 циклов (Выполнено 6 тестов). Это означает, что каждый своп в среднем составляет 4 цикла. Я называю это удивительно быстро. Возможны ли другие улучшения?
26 ответов
Для любой оптимизации всегда лучше всего тестировать, тестировать, тестировать. Я бы попробовал хотя бы сортировку сетей и сортировку вставок. Если бы я делал ставки, я бы положил свои деньги на вставку, основываясь на прошлом опыте.
Вы знаете что-нибудь о входных данных? Некоторые алгоритмы будут работать лучше с определенными видами данных. Например, сортировка вставкой работает лучше для отсортированных или почти отсортированных данных, поэтому она будет лучшим выбором, если вероятность почти отсортированных данных выше среднего.
Алгоритм, который вы опубликовали, похож на сортировку вставкой, но похоже, что вы свели к минимуму количество свопов за счет большего количества сравнений. Сравнения намного дороже, чем свопы, потому что ветки могут привести к остановке конвейера команд.
Вот реализация сортировки вставкой:
static __inline__ int sort6(int *d){
int i, j;
for (i = 1; i < 6; i++) {
int tmp = d[i];
for (j = i; j >= 1 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
Вот как я бы построил сортировочную сеть. Во-первых, используйте этот сайт для создания минимального набора макросов SWAP для сети соответствующей длины. Завершение этого в функции дает мне:
static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(4, 5);
SWAP(3, 5);
SWAP(3, 4);
SWAP(0, 3);
SWAP(1, 4);
SWAP(2, 5);
SWAP(2, 4);
SWAP(1, 3);
SWAP(2, 3);
#undef SWAP
}
Вот реализация с использованием сортировки сетей:
inline void Sort2(int *p0, int *p1)
{
const int temp = min(*p0, *p1);
*p1 = max(*p0, *p1);
*p0 = temp;
}
inline void Sort3(int *p0, int *p1, int *p2)
{
Sort2(p0, p1);
Sort2(p1, p2);
Sort2(p0, p1);
}
inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
Sort2(p0, p1);
Sort2(p2, p3);
Sort2(p0, p2);
Sort2(p1, p3);
Sort2(p1, p2);
}
inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
Sort3(p0, p1, p2);
Sort3(p3, p4, p5);
Sort2(p0, p3);
Sort2(p2, p5);
Sort4(p1, p2, p3, p4);
}
Вам действительно нужен очень эффективный безответный min а также max реализации для этого, так как это эффективно то, что этот код сводится к - последовательность min а также max операции (всего 13 штук). Я оставляю это как упражнение для читателя.
Обратите внимание, что эта реализация легко поддается векторизации (например, SIMD - в большинстве SIMD ISA есть инструкции min/max для вектора), а также к реализациям на графических процессорах (например, CUDA - без разветвлений нет проблем с расхождением деформации и т. Д.).
Смотрите также: Быстрая реализация алгоритма для сортировки очень маленького списка.
Поскольку это целые числа, а сравнение быстрое, почему бы не вычислить порядок ранжирования каждого из них напрямую:
inline void sort6(int *d) {
int e[6];
memcpy(e,d,6*sizeof(int));
int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
int o5 = 15-(o0+o1+o2+o3+o4);
d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
Похоже, я попал на вечеринку год спустя, но здесь мы идем...
Глядя на сборку, сгенерированную gcc 4.5.2, я заметил, что загрузка и сохранение выполняются для каждого свопа, который действительно не нужен. Было бы лучше загрузить 6 значений в регистры, отсортировать их и сохранить в памяти. Я приказал, чтобы грузы в магазинах были как можно ближе к тому месту, где регистры сначала нужны и в последний раз используются. Я также использовал макрос SWAP Штейнара Х. Гандерсона. Обновление: я переключился на макрос SWAP Паоло Бонзини, который превращает gcc во что-то похожее на макрос Гандерсона, но gcc может лучше упорядочить инструкции, поскольку они не представлены как явная сборка.
Я использовал тот же порядок свопинга, что и для переупорядоченной сети свопов, указанной как наиболее эффективный, хотя может быть и лучший порядок. Если я найду больше времени, я сгенерирую и протестирую несколько перестановок.
Я изменил код тестирования, чтобы рассмотреть более 4000 массивов и показать среднее количество циклов, необходимых для сортировки каждого из них. На i5-650 я получаю ~34,1 циклов / сортировку (с использованием -O3), по сравнению с исходной переупорядоченной сеткой сортировки, получающей ~65,3 циклов / сортировку (с использованием -O1, бьет -O2 и -O3).
#include <stdio.h>
static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
register int x0,x1,x2,x3,x4,x5;
x1 = d[1];
x2 = d[2];
SWAP(x1, x2);
x4 = d[4];
x5 = d[5];
SWAP(x4, x5);
x0 = d[0];
SWAP(x0, x2);
x3 = d[3];
SWAP(x3, x5);
SWAP(x0, x1);
SWAP(x3, x4);
SWAP(x1, x4);
SWAP(x0, x3);
d[0] = x0;
SWAP(x2, x5);
d[5] = x5;
SWAP(x1, x3);
d[1] = x1;
SWAP(x2, x4);
d[4] = x4;
SWAP(x2, x3);
d[2] = x2;
d[3] = x3;
#undef SWAP
#undef min
#undef max
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
return x;
}
void ran_fill(int n, int *a) {
static int seed = 76521;
while (n--) *a++ = (seed = seed *1812433253 + 12345);
}
#define NTESTS 4096
int main() {
int i;
int d[6*NTESTS];
ran_fill(6*NTESTS, d);
unsigned long long cycles = rdtsc();
for (i = 0; i < 6*NTESTS ; i+=6) {
sort6_fast(d+i);
}
cycles = rdtsc() - cycles;
printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);
for (i = 0; i < 6*NTESTS ; i+=6) {
if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
printf("d%d : %d %d %d %d %d %d\n", i,
d[i+0], d[i+1], d[i+2],
d[i+3], d[i+4], d[i+5]);
}
return 0;
}
Я изменил модифицированный набор тестов, чтобы также сообщать о часах для каждой сортировки и запускать больше тестов (функция cmp была обновлена, чтобы также обрабатывать целочисленное переполнение), вот результаты на некоторых различных архитектурах. Я пытался провести тестирование на процессоре AMD, но rdtsc не надежен на имеющейся у меня X6 1100T.
Clarkdale (i5-650)
==================
Direct call to qsort library function 635.14 575.65 581.61 577.76 521.12
Naive implementation (insertion sort) 538.30 135.36 134.89 240.62 101.23
Insertion Sort (Daniel Stutzbach) 424.48 159.85 160.76 152.01 151.92
Insertion Sort Unrolled 339.16 125.16 125.81 129.93 123.16
Rank Order 184.34 106.58 54.74 93.24 94.09
Rank Order with registers 127.45 104.65 53.79 98.05 97.95
Sorting Networks (Daniel Stutzbach) 269.77 130.56 128.15 126.70 127.30
Sorting Networks (Paul R) 551.64 103.20 64.57 73.68 73.51
Sorting Networks 12 with Fast Swap 321.74 61.61 63.90 67.92 67.76
Sorting Networks 12 reordered Swap 318.75 60.69 65.90 70.25 70.06
Reordered Sorting Network w/ fast swap 145.91 34.17 32.66 32.22 32.18
Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function 870.01 736.39 723.39 725.48 721.85
Naive implementation (insertion sort) 503.67 174.09 182.13 284.41 191.10
Insertion Sort (Daniel Stutzbach) 345.32 152.84 157.67 151.23 150.96
Insertion Sort Unrolled 316.20 133.03 129.86 118.96 105.06
Rank Order 164.37 138.32 46.29 99.87 99.81
Rank Order with registers 115.44 116.02 44.04 116.04 116.03
Sorting Networks (Daniel Stutzbach) 230.35 114.31 119.15 110.51 111.45
Sorting Networks (Paul R) 498.94 77.24 63.98 62.17 65.67
Sorting Networks 12 with Fast Swap 315.98 59.41 58.36 60.29 55.15
Sorting Networks 12 reordered Swap 307.67 55.78 51.48 51.67 50.74
Reordered Sorting Network w/ fast swap 149.68 31.46 30.91 31.54 31.58
Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function 559.97 451.88 464.84 491.35 458.11
Naive implementation (insertion sort) 341.15 160.26 160.45 154.40 106.54
Insertion Sort (Daniel Stutzbach) 284.17 136.74 132.69 123.85 121.77
Insertion Sort Unrolled 239.40 110.49 114.81 110.79 117.30
Rank Order 114.24 76.42 45.31 36.96 36.73
Rank Order with registers 105.09 32.31 48.54 32.51 33.29
Sorting Networks (Daniel Stutzbach) 210.56 115.68 116.69 107.05 124.08
Sorting Networks (Paul R) 364.03 66.02 61.64 45.70 44.19
Sorting Networks 12 with Fast Swap 246.97 41.36 59.03 41.66 38.98
Sorting Networks 12 reordered Swap 235.39 38.84 47.36 38.61 37.29
Reordered Sorting Network w/ fast swap 115.58 27.23 27.75 27.25 26.54
Nehalem (Xeon E5640)
====================
Direct call to qsort library function 911.62 890.88 681.80 876.03 872.89
Naive implementation (insertion sort) 457.69 236.87 127.68 388.74 175.28
Insertion Sort (Daniel Stutzbach) 317.89 279.74 147.78 247.97 245.09
Insertion Sort Unrolled 259.63 220.60 116.55 221.66 212.93
Rank Order 140.62 197.04 52.10 163.66 153.63
Rank Order with registers 84.83 96.78 50.93 109.96 54.73
Sorting Networks (Daniel Stutzbach) 214.59 220.94 118.68 120.60 116.09
Sorting Networks (Paul R) 459.17 163.76 56.40 61.83 58.69
Sorting Networks 12 with Fast Swap 284.58 95.01 50.66 53.19 55.47
Sorting Networks 12 reordered Swap 281.20 96.72 44.15 56.38 54.57
Reordered Sorting Network w/ fast swap 128.34 50.87 26.87 27.91 28.02
Я наткнулся на этот вопрос от Google несколько дней назад, потому что мне также нужно было быстро отсортировать массив фиксированной длины из 6 целых чисел. В моем случае, однако, мои целые числа составляют только 8 бит (вместо 32), и у меня нет строгого требования использовать только C. Я думал, что в любом случае поделюсь своими результатами, если они кому-нибудь пригодятся...
Я реализовал вариант сетевой сортировки в сборке, который использует SSE для максимально возможной векторизации операций сравнения и обмена. Требуется шесть "проходов", чтобы полностью отсортировать массив. Я использовал новый механизм для непосредственного преобразования результатов PCMPGTB (векторизованное сравнение) в переменные параметры для PSHUFB (векторизованный обмен), используя только PADDB (векторизованное добавление), а в некоторых случаях также инструкцию PAND (побитовое И).
У этого подхода также был побочный эффект, заключающийся в том, что он по- настоящему давал ответвления. Там нет никаких инструкций прыжка вообще.
Похоже, что эта реализация примерно на 38% быстрее, чем реализация, которая в настоящее время помечена как самая быстрая опция в вопросе ("Сортировка сетей 12 с помощью простой замены"). Я изменил эту реализацию, чтобы использовать char элементы массива во время моего тестирования, чтобы сделать сравнение справедливым.
Следует отметить, что такой подход может применяться к любому размеру массива до 16 элементов. Я ожидаю, что относительное преимущество в скорости перед альтернативами будет расти для больших массивов.
Код написан на MASM для процессоров x86_64 с SSSE3. Функция использует "новое" соглашение о вызовах Windows x64. Вот...
PUBLIC simd_sort_6
.DATA
ALIGN 16
pass1_shuffle OWORD 0F0E0D0C0B0A09080706040503010200h
pass1_add OWORD 0F0E0D0C0B0A09080706050503020200h
pass2_shuffle OWORD 0F0E0D0C0B0A09080706030405000102h
pass2_and OWORD 00000000000000000000FE00FEFE00FEh
pass2_add OWORD 0F0E0D0C0B0A09080706050405020102h
pass3_shuffle OWORD 0F0E0D0C0B0A09080706020304050001h
pass3_and OWORD 00000000000000000000FDFFFFFDFFFFh
pass3_add OWORD 0F0E0D0C0B0A09080706050404050101h
pass4_shuffle OWORD 0F0E0D0C0B0A09080706050100020403h
pass4_and OWORD 0000000000000000000000FDFD00FDFDh
pass4_add OWORD 0F0E0D0C0B0A09080706050403020403h
pass5_shuffle OWORD 0F0E0D0C0B0A09080706050201040300h
pass5_and OWORD 0000000000000000000000FEFEFEFE00h
pass5_add OWORD 0F0E0D0C0B0A09080706050403040300h
pass6_shuffle OWORD 0F0E0D0C0B0A09080706050402030100h
pass6_add OWORD 0F0E0D0C0B0A09080706050403030100h
.CODE
simd_sort_6 PROC FRAME
.endprolog
; pxor xmm4, xmm4
; pinsrd xmm4, dword ptr [rcx], 0
; pinsrb xmm4, byte ptr [rcx + 4], 4
; pinsrb xmm4, byte ptr [rcx + 5], 5
; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer. Same on extract
; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
movd xmm4, dword ptr [rcx]
pinsrw xmm4, word ptr [rcx + 4], 2 ; word 2 = bytes 4 and 5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass1_shuffle]
pcmpgtb xmm5, xmm4
paddb xmm5, oword ptr [pass1_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass2_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass2_and]
paddb xmm5, oword ptr [pass2_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass3_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass3_and]
paddb xmm5, oword ptr [pass3_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass4_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass4_and]
paddb xmm5, oword ptr [pass4_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass5_shuffle]
pcmpgtb xmm5, xmm4
pand xmm5, oword ptr [pass5_and]
paddb xmm5, oword ptr [pass5_add]
pshufb xmm4, xmm5
movdqa xmm5, xmm4
pshufb xmm5, oword ptr [pass6_shuffle]
pcmpgtb xmm5, xmm4
paddb xmm5, oword ptr [pass6_add]
pshufb xmm4, xmm5
;pextrd dword ptr [rcx], xmm4, 0 ; benchmarked with this
;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
;pextrb byte ptr [rcx + 5], xmm4, 5
movd dword ptr [rcx], xmm4
pextrw word ptr [rcx + 4], xmm4, 2 ; x86 is little-endian, so this is the right order
ret
simd_sort_6 ENDP
END
Вы можете скомпилировать это в исполняемый объект и связать его с вашим C-проектом. Инструкции о том, как сделать это в Visual Studio, вы можете прочитать в этой статье. Вы можете использовать следующий прототип C для вызова функции из вашего кода C:
void simd_sort_6(char *values);
Тестовый код довольно плохой; он переполняет исходный массив (люди здесь не читают предупреждения компилятора?), printf выводит неправильные элементы, он использует.byte для rdtsc без веской причины, есть только один прогон (!), нет ничего проверяющего, что конечные результаты на самом деле правильные (поэтому очень легко "оптимизировать" что-то слегка неправильное), включенные тесты очень элементарные (без отрицательных чисел?), и ничто не мешает компилятору просто отбросить всю функцию как мертвый код.
Это, как говорится, также довольно легко улучшить решение битовой сети; просто измените мин / макс / своп вещи на
#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }
и он у меня получается примерно на 65% быстрее (Debian gcc 4.4.5 с -O2, amd64, Core i7).
Хотя мне очень нравится макрос подкачки при условии:
#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }
Я вижу улучшение (которое может сделать хороший компилятор):
#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }
Мы обращаем внимание на то, как работают min и max, и явно извлекаем общее подвыражение. Это полностью исключает минимальные и максимальные макросы.
Никогда не оптимизируйте мин / макс без бенчмаркинга и просмотра фактической сборки, сгенерированной компилятором. Если я позволю GCC оптимизировать min с помощью инструкций условного перемещения, я получу ускорение на 33%:
#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
(280 против 420 циклов в тестовом коде). Выполнение max с?: Более или менее то же самое, почти потеряно в шуме, но вышеупомянутое немного быстрее. Этот SWAP быстрее как с GCC, так и с Clang.
Компиляторы также выполняют исключительную работу по распределению регистров и анализу псевдонимов, эффективно перемещая d[x] в локальные переменные заранее и только копируя обратно в память в конце. На самом деле, они делают это даже лучше, чем если бы вы работали полностью с локальными переменными (например, d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Я пишу это, потому что вы предполагаете сильную оптимизацию и все же пытаетесь перехитрить компилятор на мин / макс.:)
Кстати, я пробовал Clang и GCC. Они выполняют одну и ту же оптимизацию, но из-за различий в расписании у обоих есть некоторые различия в результатах, не могу сказать, что на самом деле быстрее или медленнее. GCC быстрее в сортировочных сетях, Clang - в квадратичных.
Просто для полноты возможна развернутая сортировка пузырьков и вставка. Вот вид пузыря:
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);
и вот сортировка вставки:
//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
int t;
t = d[1]; ITER(0);
t = d[2]; ITER(1); ITER(0);
t = d[3]; ITER(2); ITER(1); ITER(0);
t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);
Такая сортировка вставок выполняется быстрее, чем у Даниеля Штутцбаха, и особенно хороша для графического процессора или компьютера с предопределением, потому что ITER может быть выполнен только с 3 инструкциями (против 4 для SWAP). Например, вот t = d[2]; ITER(1); ITER(0); линия в сборке ARM:
MOV r6, r2
CMP r6, r1
MOVLT r2, r1
MOVLT r1, r6
CMP r6, r0
MOVLT r1, r0
MOVLT r0, r6
Для шести элементов сортировка вставкой является конкурентоспособной с сетью сортировки (12 обменов против 15 итераций балансирует 4 инструкции / обмен против 3 инструкций / итерация); пузырьковый тип, конечно, медленнее. Но это не будет правдой, когда размер увеличивается, так как сортировка вставки - O(n^2), в то время как сеть сортировки - O(n log n).
Я перенес набор тестов на машину с архитектурой PPC, которую не могу идентифицировать (не нужно было трогать код, просто увеличивать итерации теста, использовать 8 тестовых примеров, чтобы избежать загрязнения результатов модами и заменить специфичный для x86 rdtsc):
Прямой вызов функции библиотеки qsort: 101
Наивная реализация (вставка сортировки): 299
Сортировка вставок (Даниэль Штутцбах): 108
Сортировка вставок развернуто: 51
Сортировка сетей (Даниэль Штутцбах): 26
Сортировка сетей (Paul R): 85
Сортировка сетей 12 с быстрой заменой: 117
Сортировка сетей 12 переупорядочено Своп: 116
Порядок ранга: 56
Обмен XOR может быть полезен в ваших функциях обмена.
void xorSwap (int *x, int *y) {
if (*x != *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
If может вызвать слишком большое расхождение в вашем коде, но если у вас есть гарантия, что все ваши целые уникальны, это может быть удобно.
С нетерпением жду возможности попробовать свои силы в этом и учиться на этих примерах, но сначала некоторые моменты из моей 1,5 ГГц PPC Powerbook G4 с 1 ГБ оперативной памяти DDR. (Я заимствовал аналогичный rdtsc-подобный таймер для PPC у http://www.mcs.anl.gov/~kazutomo/rdtsc.html для синхронизации.) Я запускал программу несколько раз, и абсолютные результаты менялись, но последовательно Самым быстрым тестом был "Сортировка вставки (Даниэль Штутцбах)", а "Сортировка вставки развернута" за короткую секунду.
Вот последний набор раз:
**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)** : 85
**Insertion Sort Unrolled** : 97
**Sorting Networks (Daniel Stutzbach)** : 457
**Sorting Networks (Paul R)** : 179
**Sorting Networks 12 with Fast Swap** : 238
**Sorting Networks 12 reordered Swap** : 236
**Rank Order** : 116
Вот мой вклад в эту тему: оптимизированная 1, 4-разрядная оболочка для вектора int из 6 элементов (valp), содержащего уникальные значения.
void shellsort (int *valp)
{
int c,a,*cp,*ip=valp,*ep=valp+5;
c=*valp; a=*(valp+4);if (c>a) {*valp= a;*(valp+4)=c;}
c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}
cp=ip;
do
{
c=*cp;
a=*(cp+1);
do
{
if (c<a) break;
*cp=a;
*(cp+1)=c;
cp-=1;
c=*cp;
} while (cp>=valp);
ip+=1;
cp=ip;
} while (ip<ep);
}
На моем ноутбуке HP dv7-3010so с двухъядерным процессором Athlon M300 @ 2 ГГц (память DDR2) он работает за 165 тактов. Это среднее значение, рассчитанное по времени для каждой уникальной последовательности (всего 6!/720). Скомпилировано в Win32 с использованием OpenWatcom 1.8. Цикл по сути является сортировкой вставки и имеет длину 16 инструкций /37 байт.
У меня нет 64-битной среды для компиляции.
Я знаю, что я опоздал, но мне было интересно поэкспериментировать с разными решениями. Сначала я очистил эту пасту, скомпилировал ее и поместил в репозиторий. Я оставил некоторые нежелательные решения в тупик, чтобы другие не попробовали. Среди них было мое первое решение, которое пыталось гарантировать, что x1>x2 был вычислен один раз. После оптимизации она не быстрее других простых версий.
Я добавил зацикленную версию сортировки по рангу, поскольку мое собственное приложение для этого исследования предназначено для сортировки 2-8 элементов, поэтому, поскольку имеется переменное число аргументов, необходим цикл. По этой же причине я проигнорировал сетевые решения для сортировки.
Тестовый код не проверял правильность обработки дубликатов, поэтому, хотя все существующие решения были правильными, я добавил специальный код в тестовый код, чтобы гарантировать правильную обработку дубликатов.
Затем я написал вид вставки, который целиком находится в регистрах AVX. На моей машине это на 25% быстрее, чем другие типы вставок, но на 100% медленнее, чем порядок ранжирования. Я сделал это исключительно для эксперимента и не ожидал, что это будет лучше из-за разветвлений в сортировке вставок.
static inline void sort6_insertion_sort_avx(int* d) {
__m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
__m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
__m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
__m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
INT_MAX, INT_MAX, INT_MAX, INT_MAX);
__m256i val, gt, permute;
unsigned j;
// 8 / 32 = 2^-2
#define ITER(I) \
val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
gt = _mm256_cmpgt_epi32(sorted, val);\
permute = _mm256_blendv_epi8(index, shlpermute, gt);\
j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
ITER(1);
ITER(2);
ITER(3);
ITER(4);
ITER(5);
int x[8];
_mm256_storeu_si256((__m256i*)x, sorted);
d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}
Затем я написал сортировку по рангу, используя AVX. Это соответствует скорости других решений рангового порядка, но не быстрее. Проблема в том, что я могу рассчитывать индексы только с помощью AVX, а затем мне нужно составить таблицу индексов. Это связано с тем, что расчеты основаны на назначении, а не на источнике. См. Преобразование из исходных индексов в целевые индексы
static inline void sort6_rank_order_avx(int* d) {
__m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
__m256i one = _mm256_set1_epi32(1);
__m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
__m256i rot = src;
__m256i index = _mm256_setzero_si256();
__m256i gt, permute;
__m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
__m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
__m256i srcIx = dstIx;
__m256i eq = one;
__m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
rot = _mm256_permutevar8x32_epi32(rot, ror);\
gt = _mm256_cmpgt_epi32(src, rot);\
index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
_mm256_cmpeq_epi32(src, rot)));\
eq = _mm256_insert_epi32(eq, 0, I)
INC(0);
INC(1);
INC(2);
INC(3);
INC(4);
int e[6];
e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
int i[8];
_mm256_storeu_si256((__m256i*)i, index);
d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}
Репо можно найти здесь: https://github.com/eyepatchParrot/sort6/
Если сортировка вставок здесь достаточно конкурентоспособна, я бы рекомендовал попробовать сортировку оболочек. Боюсь, что 6 элементов, вероятно, слишком мало для того, чтобы быть в числе лучших, но, возможно, стоит попробовать.
Пример кода, непроверенный, отлаженный и т. Д. Вы хотите настроить последовательность inc = 4 и inc -= 3, чтобы найти оптимальный (например, попробуйте inc = 2, inc -= 1).
static __inline__ int sort6(int * d) {
char j, i;
int tmp;
for (inc = 4; inc > 0; inc -= 3) {
for (i = inc; i < 5; i++) {
tmp = a[i];
j = i;
while (j >= inc && a[j - inc] > tmp) {
a[j] = a[j - inc];
j -= inc;
}
a[j] = tmp;
}
}
}
Я не думаю, что это победит, но если кто-то отправит вопрос о сортировке 10 элементов, кто знает...
Согласно Википедии это может даже сочетаться с сортировочными сетями: Pratt, V (1979). Шеллсортировка и сортировочные сети (Выдающиеся диссертации в области компьютерных наук). Garland. ISBN 0-824-04406-1
Этот вопрос становится довольно старым, но на самом деле мне пришлось решать ту же проблему в наши дни: быстрые агорифмы для сортировки небольших массивов. Я подумал, что будет хорошей идеей поделиться своими знаниями. Хотя я впервые начал использовать сортировку сетей, мне, наконец, удалось найти другие алгоритмы, для которых общее число сравнений, выполненных для сортировки каждой перестановки из 6 значений, было меньше, чем с сетками сортировки, и меньше, чем с сортировкой вставками. Я не посчитал количество свопов; Я ожидал бы, что это будет примерно эквивалентно (возможно, немного выше иногда).
Алгоритм sort6 использует алгоритм sort4 который использует алгоритм sort3, Вот реализация в некоторой легкой форме C++ (оригинал является тяжелым шаблоном, чтобы он мог работать с любым итератором с произвольным доступом и любой подходящей функцией сравнения).
Сортировка 3 значений
Следующий алгоритм представляет собой развернутую сортировку вставок. Когда необходимо выполнить два обмена (6 назначений), вместо этого используются 4 назначения:
void sort3(int* array)
{
if (array[1] < array[0]) {
if (array[2] < array[0]) {
if (array[2] < array[1]) {
std::swap(array[0], array[2]);
} else {
int tmp = array[0];
array[0] = array[1];
array[1] = array[2];
array[2] = tmp;
}
} else {
std::swap(array[0], array[1]);
}
} else {
if (array[2] < array[1]) {
if (array[2] < array[0]) {
int tmp = array[2];
array[2] = array[1];
array[1] = array[0];
array[0] = tmp;
} else {
std::swap(array[1], array[2]);
}
}
}
}
Это выглядит немного сложным, потому что сортировка имеет более или менее одну ветвь для каждой возможной перестановки массива, используя 2~3 сравнения и не более 4 присваиваний для сортировки трех значений.
Сортировка 4 значений
Этот называет sort3 затем выполняет развернутую сортировку вставки с последним элементом массива:
void sort4(int* array)
{
// Sort the first 3 elements
sort3(array);
// Insert the 4th element with insertion sort
if (array[3] < array[2]) {
std::swap(array[2], array[3]);
if (array[2] < array[1]) {
std::swap(array[1], array[2]);
if (array[1] < array[0]) {
std::swap(array[0], array[1]);
}
}
}
}
Этот алгоритм выполняет от 3 до 6 сравнений и не более 5 обменов. Развернуть сортировку вставкой легко, но мы будем использовать другой алгоритм для последней сортировки...
Сортировка 6 значений
Этот использует развернутую версию того, что я назвал сортировкой двойной вставки. Название не настолько велико, но оно достаточно наглядно, вот как оно работает:
- Сортировать все, кроме первого и последнего элементов массива.
- Поменяйте местами первое и элементы массива, если первое больше последнего.
- Вставьте первый элемент в отсортированную последовательность спереди, а затем последний элемент сзади.
После перестановки первый элемент всегда меньше последнего, что означает, что при вставке их в отсортированную последовательность не будет более N сравнений для вставки двух элементов в худшем случае: например, если первый элемент был вставлен в 3-ю позицию, затем последний не может быть вставлен ниже 4-й позиции.
void sort6(int* array)
{
// Sort everything but first and last elements
sort4(array+1);
// Switch first and last elements if needed
if (array[5] < array[0]) {
std::swap(array[0], array[5]);
}
// Insert first element from the front
if (array[1] < array[0]) {
std::swap(array[0], array[1]);
if (array[2] < array[1]) {
std::swap(array[1], array[2]);
if (array[3] < array[2]) {
std::swap(array[2], array[3]);
if (array[4] < array[3]) {
std::swap(array[3], array[4]);
}
}
}
}
// Insert last element from the back
if (array[5] < array[4]) {
std::swap(array[4], array[5]);
if (array[4] < array[3]) {
std::swap(array[3], array[4]);
if (array[3] < array[2]) {
std::swap(array[2], array[3]);
if (array[2] < array[1]) {
std::swap(array[1], array[2]);
}
}
}
}
}
Мои тесты на каждую перестановку из 6 значений показывают, что этот алгоритм всегда выполняет от 6 до 13 сравнений. Я не вычислял количество выполненных свопов, но не ожидаю, что оно будет выше 11 в худшем случае.
Я надеюсь, что это поможет, даже если этот вопрос больше не представляет реальной проблемы:)
РЕДАКТИРОВАТЬ: после того, как положить его в предоставленный тест, он будет медленнее, чем большинство интересных альтернатив. Это имеет тенденцию работать немного лучше, чем развернутая сортировка вставок, но это почти так. По сути, это не лучший тип для целых чисел, но он может быть интересен для типов с дорогой операцией сравнения.
Я обнаружил, что, по крайней мере, в моей системе, функции sort6_iterator() а также sort6_iterator_local() определенные ниже, оба выполнялись, по крайней мере, так же быстро, и часто заметно быстрее, чем вышеуказанный текущий рекордсмен:
#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)
template<class IterType>
inline void sort6_iterator(IterType it)
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
const auto b = MAX(*(it + x), *(it + y)); \
*(it + x) = a; *(it + y) = b; }
SWAP(1, 2) SWAP(4, 5)
SWAP(0, 2) SWAP(3, 5)
SWAP(0, 1) SWAP(3, 4)
SWAP(1, 4) SWAP(0, 3)
SWAP(2, 5) SWAP(1, 3)
SWAP(2, 4)
SWAP(2, 3)
#undef SWAP
}
Я прошел эту функцию std::vector Итератор в моем временном коде. Я подозреваю, что использование итераторов дает g++ определенные гарантии относительно того, что может и не может произойти с памятью, на которую ссылается итератор, чего в противном случае у него не было бы, и именно эти гарантии позволяют g++ лучше оптимизировать код сортировки (который, если Я правильно помню, это также одна из причин, почему так много std алгоритмы, такие как std::sort(), как правило, имеют такие непристойно хорошие показатели). Однако во время синхронизации я заметил, что контекст (то есть окружающий код), в котором был сделан вызов функции сортировки, оказал значительное влияние на производительность, что, вероятно, связано с тем, что функция встроена и затем оптимизирована. Например, если программа была достаточно простой, то, как правило, не было большой разницы в производительности между передачей функции сортировки указатель и передачей ей итератора; в противном случае использование итераторов обычно приводило к заметно лучшей производительности и никогда (по моему опыту, по крайней мере, пока) к заметному ухудшению производительности. Я подозреваю, что это может быть потому, что g++ может глобально оптимизировать достаточно простой код.
Более того, sort6_iterator() иногда (опять же, в зависимости от контекста, в котором вызывается функция), последовательно превосходят следующую функцию сортировки:
template<class IterType>
inline void sort6_iterator_local(IterType it)
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
const auto b = MAX(data##x, data##y); \
data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a) auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;
DD2(1,2) SWAP(1, 2)
DD2(4,5) SWAP(4, 5)
DD1(0) SWAP(0, 2)
DD1(3) SWAP(3, 5)
SWAP(0, 1) SWAP(3, 4)
SWAP(1, 4) SWAP(0, 3) CB(0)
SWAP(2, 5) CB(5)
SWAP(1, 3) CB(1)
SWAP(2, 4) CB(4)
SWAP(2, 3) CB(2) CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}
Обратите внимание, что определение SWAP() нижеприведенное иногда приводит к несколько лучшей производительности, хотя в большинстве случаев приводит к несколько меньшей производительности или незначительной разнице в производительности.
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
data##y = MAX(data##x, data##y); \
data##x = a; }
Если вы просто хотите алгоритм сортировки, который gcc -O3 всегда хорошо оптимизирует, тогда, в зависимости от того, как вы передаете ввод, попробуйте один из следующих двух алгоритмов:
template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a) register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a) *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
DD2(1,2) SORT2(1,2)
DD2(4,5) SORT2(4,5)
DD1(0) SORT2(0,2)
DD1(3) SORT2(3,5)
SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
SORT2(1,4) SORT2(0,3) CB1(0)
SORT2(2,4) CB1(4)
SORT2(1,3) CB1(1)
SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
Или же
template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a) register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a) e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
DD2(1,2) SORT2(1,2)
DD2(4,5) SORT2(4,5)
DD1(0) SORT2(0,2)
DD1(3) SORT2(3,5)
SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
SORT2(1,4) SORT2(0,3) CB1(0)
SORT2(2,4) CB1(4)
SORT2(1,3) CB1(1)
SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
Причина использования register Ключевое слово потому, что это один из немногих случаев, когда вы знаете, что вы хотите эти значения в регистрах. Без register компилятор будет выяснять это большую часть времени, но иногда это не так. С использованием register Ключевое слово помогает решить эту проблему. Обычно, однако, не используйте register ключевое слово, так как он скорее замедлит ваш код, чем ускорит его.
Также обратите внимание на использование шаблонов. Это сделано специально, даже если inline Ключевое слово: шаблонные функции, как правило, гораздо более агрессивно оптимизируются с помощью gcc, чем функции vanilla C (это связано с тем, что gcc приходится иметь дело с указателями на функции для функций vanilla C, но не с шаблонными функциями).
Я решил попробовать развёрнутую сортировку слиянием-вставкой Форда-Джонсона, которая обеспечивает минимально возможное количество сравнений (ceil(log2(6!)) = 10) и без свопов. Однако он не конкурирует (я получил немного лучшее время, чем худшее решение для сетей сортировки).
sort6_sorting_network_v1).
Он загружает значения в шесть регистров, затем выполняет от 8 до 10 сравнений, чтобы решить, какое из 720=6! случаи, в которых он находится, затем записывает регистры обратно в соответствующий один из этих 720 заказов (отдельный код для каждого случая). До окончательной обратной записи нет никаких обменов или переупорядочения чего-либо. Я не смотрел на сгенерированный код сборки.
static inline void sort6_ford_johnson_unrolled(int *D) {
register int a = D[0], b = D[1], c = D[2], d = D[3], e = D[4], f = D[5];
#define abcdef(a,b,c,d,e,f) (D[0]=a, D[1]=b, D[2]=c, D[3]=d, D[4]=e, D[5]=f)
#define abdef_cd(a,b,c,d,e,f) (c<a ? abcdef(c,a,b,d,e,f) \
: c<b ? abcdef(a,c,b,d,e,f) \
: abcdef(a,b,c,d,e,f))
#define abedf_cd(a,b,c,d,e,f) (c<b ? c<a ? abcdef(c,a,b,e,d,f) \
: abcdef(a,c,b,e,d,f) \
: c<e ? abcdef(a,b,c,e,d,f) \
: abcdef(a,b,e,c,d,f))
#define abdf_cd_ef(a,b,c,d,e,f) (e<b ? e<a ? abedf_cd(e,a,c,d,b,f) \
: abedf_cd(a,e,c,d,b,f) \
: e<d ? abedf_cd(a,b,c,d,e,f) \
: abdef_cd(a,b,c,d,e,f))
#define abd_cd_ef(a,b,c,d,e,f) (d<f ? abdf_cd_ef(a,b,c,d,e,f) \
: b<f ? abdf_cd_ef(a,b,e,f,c,d) \
: abdf_cd_ef(e,f,a,b,c,d))
#define ab_cd_ef(a,b,c,d,e,f) (b<d ? abd_cd_ef(a,b,c,d,e,f) \
: abd_cd_ef(c,d,a,b,e,f))
#define ab_cd(a,b,c,d,e,f) (e<f ? ab_cd_ef(a,b,c,d,e,f) \
: ab_cd_ef(a,b,c,d,f,e))
#define ab(a,b,c,d,e,f) (c<d ? ab_cd(a,b,c,d,e,f) \
: ab_cd(a,b,d,c,e,f))
a<b ? ab(a,b,c,d,e,f)
: ab(b,a,c,d,e,f);
#undef ab
#undef ab_cd
#undef ab_cd_ef
#undef abd_cd_ef
#undef abdf_cd_ef
#undef abedf_cd
#undef abdef_cd
#undef abcdef
}
TEST(ford_johnson_unrolled, "Unrolled Ford-Johnson Merge-Insertion sort");
Я знаю, что это старый вопрос.
Но я просто написал другое решение, которым хочу поделиться.
Не используя ничего, кроме вложенного MIN MAX,
Это не быстро, так как использует 114 каждого,
может уменьшить его до 75 довольно просто, как это так -> pastebin
Но тогда это уже не просто min max.
Что может работать, так это делать мин / макс на нескольких целых числах одновременно с AVX
#include <stdio.h>
static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
"=A" (x));
return x;
}
#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))
static __inline__ void sort6(int * in) {
const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];
in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );
const int
AB = MAX(A, B),
AC = MAX(A, C),
AD = MAX(A, D),
AE = MAX(A, E),
AF = MAX(A, F),
BC = MAX(B, C),
BD = MAX(B, D),
BE = MAX(B, E),
BF = MAX(B, F),
CD = MAX(C, D),
CE = MAX(C, E),
CF = MAX(C, F),
DE = MAX(D, E),
DF = MAX(D, F),
EF = MAX(E, F);
in[1] = MIN4 (
MIN4( AB, AC, AD, AE ),
MIN4( AF, BC, BD, BE ),
MIN4( BF, CD, CE, CF ),
MIN3( DE, DF, EF)
);
const int
ABC = MAX(AB,C),
ABD = MAX(AB,D),
ABE = MAX(AB,E),
ABF = MAX(AB,F),
ACD = MAX(AC,D),
ACE = MAX(AC,E),
ACF = MAX(AC,F),
ADE = MAX(AD,E),
ADF = MAX(AD,F),
AEF = MAX(AE,F),
BCD = MAX(BC,D),
BCE = MAX(BC,E),
BCF = MAX(BC,F),
BDE = MAX(BD,E),
BDF = MAX(BD,F),
BEF = MAX(BE,F),
CDE = MAX(CD,E),
CDF = MAX(CD,F),
CEF = MAX(CE,F),
DEF = MAX(DE,F);
in[2] = MIN( MIN4 (
MIN4( ABC, ABD, ABE, ABF ),
MIN4( ACD, ACE, ACF, ADE ),
MIN4( ADF, AEF, BCD, BCE ),
MIN4( BCF, BDE, BDF, BEF )),
MIN4( CDE, CDF, CEF, DEF )
);
const int
ABCD = MAX(ABC,D),
ABCE = MAX(ABC,E),
ABCF = MAX(ABC,F),
ABDE = MAX(ABD,E),
ABDF = MAX(ABD,F),
ABEF = MAX(ABE,F),
ACDE = MAX(ACD,E),
ACDF = MAX(ACD,F),
ACEF = MAX(ACE,F),
ADEF = MAX(ADE,F),
BCDE = MAX(BCD,E),
BCDF = MAX(BCD,F),
BCEF = MAX(BCE,F),
BDEF = MAX(BDE,F),
CDEF = MAX(CDE,F);
in[3] = MIN4 (
MIN4( ABCD, ABCE, ABCF, ABDE ),
MIN4( ABDF, ABEF, ACDE, ACDF ),
MIN4( ACEF, ADEF, BCDE, BCDF ),
MIN3( BCEF, BDEF, CDEF )
);
const int
ABCDE= MAX(ABCD,E),
ABCDF= MAX(ABCD,F),
ABCEF= MAX(ABCE,F),
ABDEF= MAX(ABDE,F),
ACDEF= MAX(ACDE,F),
BCDEF= MAX(BCDE,F);
in[4]= MIN (
MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
MIN ( ACDEF, BCDEF )
);
in[5] = MAX(ABCDE,F);
}
int main(int argc, char ** argv) {
int d[6][6] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (int i = 0; i < 6; i++) {
sort6(d[i]);
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
for (int i = 0; i < 6; i++) {
printf("d%d : %d %d %d %d %d %d\n", i,
d[i][0], d[i][1], d[i][2],
d[i][3], d[i][4], d[i][5]);
}
}
РЕДАКТИРОВАТЬ:
Решение по ранговому порядку, вдохновленное Рексом Керром, намного быстрее, чем беспорядок выше
static void sort6(int *o) {
const int
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
BC = B>C, BD = B>D, BE = B>E,
CD = C>D, CE = C>E,
DE = D>E,
a = AB + AC + AD + AE + (A>F),
b = 1 - AB + BC + BD + BE + (B>F),
c = 2 - AC - BC + CD + CE + (C>F),
d = 3 - AD - BD - CD + DE + (D>F),
e = 4 - AE - BE - CE - DE + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}
Я считаю, что на ваш вопрос есть две части.
- Во-первых, определить оптимальный алгоритм. Это делается - по крайней мере, в этом случае - путем обхода каждого возможного порядка (их не так много), который позволяет вычислить точное минимальное, максимальное, среднее и стандартное отклонение сравнений и свопов. Имейте второе место или два удобных также.
- Второе - оптимизировать алгоритм. Многое можно сделать, чтобы преобразовать примеры из учебников в средние и простые алгоритмы. Если вы понимаете, что алгоритм не может быть оптимизирован до необходимой степени, попробуйте получить второе место.
Я бы не стал сильно волноваться по поводу опустошения конвейеров (если предположить, что сейчас x86): предсказание ветвлений прошло долгий путь. То, о чем я бы беспокоился, - это убедиться, что код и данные помещаются в одну строку кэша каждая (возможно, две для кода). Как только время выборки будет очень низким, это компенсирует любую задержку. Это также означает, что ваш внутренний цикл будет состоять из десяти инструкций или около того, что и должно быть (в моем алгоритме сортировки есть два разных внутренних цикла, они 10 инструкций /22 байта и 9/22 длины соответственно). Предполагая, что код не содержит никаких div-ов, вы можете быть уверены, что он будет невероятно быстрым.
Я знаю, что вечеринка прошла более 12 лет назад, но всё же.
Я нашел лучший способ отсортировать несколько элементов, используя параллельную итерацию
shifted = [0 sorted](1 : length(sorted));
shifted = max(shifted, new_value);
sorted = min(sorted, shifted);
Начиная сsorted = ones(1, N) * max_value;
Это будет довольно хорошо SIMDify даже с
using vec4 = int32_t __attribute__((vector_size(16));
int32_t max = 0x7fffffff;
vec4 sorted_lo = { max, max, max, max }, sorted_hi = sorted_lo;
sorted_lo[0] = data[0]; // "pre-sort" the first element directly
for (int i = 1 ; i < 6; i++) {
vec4 new_value{ data[i], data[i], data[i], data[i] };
vec4 shifted_lo = { 0, sorted_lo[0], sorted_lo[1], sorted_lo[2]};
vec4 shifted_hi = { sorted_lo[3],sorted_hi[0],sorted_hi[1],sorted_hi[2]};
shifted_lo = max(shifted_lo, new_value0);
shifted_hi = max(shifted_hi, new_value0);
sorted_lo = max(sorted_lo, shifted_lo);
sorted_hi = max(sorted_hi, shifted_hi);
}
Многие архитектуры SIMD (SSE4, ARM64) содержат операции мин/макс, а также переключение между двумя векторами и дублирование одной полосы движения. В AVX2 нельзя эффективно переключаться между полосами, но можно сортировать два независимых вектора по 5-8 элементов.
Значительно улучшенная версия будет использовать битоническую сортировку слиянием с двумя векторами. Первый вектор использует прием сортировки вставкой для трех первых значений, например, из1 8 4 3 5 4как в1 4 8 inf, другой вектор отсортирован поinf 5 4 3.
Затем этап битонического слияния выполнит сортировку.A = min(a,b); B = max(a,b), затем отсортируйтеA[0]<->A[2], A[1]<->A[3], B[0]<->B[2], B[1]<->B[3]параллельно и наконец последний этапA[0]<->A[1], A[2]<->A[3],B[0]<->B[1], B[2]<->B[3].
В примерах значений это будет означать
A = 1 4 8 inf, B = inf 5 4 3
<--------------->
<---------------->
<---------------->
<--------------->
A = 1 4 4 3 , B = inf 5 8 inf
<---> <----->
<---> <---->
A = 1 3 4 4 , B = 8 5 inf inf
<-> <-> <---> <---->
A = 1 3 4 5 , B = 5 8 inf inf
Наверное, самый трудный шагA[0,2], A[1,3], B[0,2], B[1,3]этап, требующий некоторой перетасовки. Напротив, по крайней мере, ARM64 NEON имеет инструкцию для извлечения попарного минимума/максимума.
Отвечая на комментарий, передача данных в векторные регистры обычно не является проблемой. При получении данных из регистров SIMD или из памяти может возникнуть более длительная задержка. Для SSE2 я бы, например, попытался поместить 6 элементов в вектор
int32_t x[8] = {inf, 0,0,0,0,0,0, inf};
что позволило бы быстро перетасовать (pshufd / _mm_shuffle_epi32), чтобы получить первые отсортированные векторыval[1], inf, inf, infпротивinf, inf, inf, val[4]а также трансляцию любой полосы через регистры XXM.
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
int t[6] = {0};
int r1,r2;
r1=0;
r1 += (a[0] > a[1]);
r1 += (a[0] > a[2]);
r1 += (a[0] > a[3]);
r1 += (a[0] > a[4]);
r1 += (a[0] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[0];
r2=0;
r2 += (a[1] > a[0]);
r2 += (a[1] > a[2]);
r2 += (a[1] > a[3]);
r2 += (a[1] > a[4]);
r2 += (a[1] > a[5]);
while(t[r2]){r2++;}
t[r2] = a[1];
r1=0;
r1 += (a[2] > a[0]);
r1 += (a[2] > a[1]);
r1 += (a[2] > a[3]);
r1 += (a[2] > a[4]);
r1 += (a[2] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[2];
r2=0;
r2 += (a[3] > a[0]);
r2 += (a[3] > a[1]);
r2 += (a[3] > a[2]);
r2 += (a[3] > a[4]);
r2 += (a[3] > a[5]);
while(t[r2]){r2++;}
t[r2] = a[3];
r1=0;
r1 += (a[4] > a[0]);
r1 += (a[4] > a[1]);
r1 += (a[4] > a[2]);
r1 += (a[4] > a[3]);
r1 += (a[4] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[4];
r2=0;
r2 += (a[5] > a[0]);
r2 += (a[5] > a[1]);
r2 += (a[5] > a[2]);
r2 += (a[5] > a[3]);
r2 += (a[5] > a[4]);
while(t[r2]){r2++;}
t[r2] = a[5];
a[0]=t[0];
a[1]=t[1];
a[2]=t[2];
a[3]=t[3];
a[4]=t[4];
a[5]=t[5];
}
static __inline__ void sort6(int* a)
{
#define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
register int t;
wire( 0, 1); wire( 2, 3); wire( 4, 5);
wire( 3, 5); wire( 0, 2); wire( 1, 4);
wire( 4, 5); wire( 2, 3); wire( 0, 1);
wire( 3, 4); wire( 1, 2);
wire( 2, 3);
#undef wire
}
Попробуйте "объединить отсортированный список" сортировать.:) Используйте два массива. Самый быстрый для маленьких и больших массивов.
Если вы согласны, вы только проверяете, где вставить. Другие большие значения вам не нужно сравнивать (cmp = ab>0).
Для 4 номеров вы можете использовать систему 4-5 cmp (~4.6) или 3-6 cmp (~4.9). Bubble sort использовать 6 cmp (6). Много cmp для больших чисел медленнее кода.
Этот код использует 5 cmp (не сортировка MSL):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);}
if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);}
if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);}
if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);}
if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}
Принципиальный MSL
9 8 7 6 5 4 3 2 1 0
89 67 45 23 01 ... concat two sorted lists, list length = 1
6789 2345 01 ... concat two sorted lists, list length = 2
23456789 01 ... concat two sorted lists, list length = 4
0123456789 ... concat two sorted lists, list length = 8
JS код
function sortListMerge_2a(cmp)
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end = arr_count;
//var str = '';
cycles = 0;
if (end>3)
{
stepmax = ((end - start + 1) >> 1) << 1;
m = 1;
n = 2;
for (step=1;step<stepmax;step<<=1) //bounds 1-1, 2-2, 4-4, 8-8...
{
a = start;
while (a<end)
{
b = a + step;
c = a + step + step;
b = b<end ? b : end;
c = c<end ? c : end;
i = a;
j = b;
k = i;
while (i<b && j<c)
{
if (cmp(arr[m][i],arr[m][j])>0)
{arr[n][k] = arr[m][j]; j++; k++;}
else {arr[n][k] = arr[m][i]; i++; k++;}
}
while (i<b)
{arr[n][k] = arr[m][i]; i++; k++;
}
while (j<c)
{arr[n][k] = arr[m][j]; j++; k++;
}
a = c;
}
tmp = m; m = n; n = tmp;
}
return m;
}
else
{
// sort 3 items
sort10(cmp);
return m;
}
}Может быть, я опаздываю на вечеринку, но по крайней мере мой вклад - это новый подход.
- Код действительно должен быть встроен
- даже если встроено, слишком много веток
- анализирующая часть в основном O(N(N-1)), которая кажется нормальной для N=6
- код может быть более эффективным, если стоимость
swapбудет выше (и стоимостьcompare) - Я верю, что статические функции встроены.
- Метод связан с ранговой сортировкой
- вместо рангов используются относительные ранги (смещения).
- сумма рангов равна нулю для каждого цикла в любой группе перестановок.
- вместо
SWAP()В двух элементах циклы преследуются, им требуется только одна временная замена и один (регистр-> регистр) своп (новый <- старый).
Обновление: немного изменил код, некоторые люди используют компиляторы C++ для компиляции кода C...
#include <stdio.h>
#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif
static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);
int wsort6(int *arr);
void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
fprintf(stderr, " %3d", *arr);
}
fprintf(stderr,"\n");
}
void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
fprintf(stderr, " %3d", (int) *arr);
}
fprintf(stderr,"\n");
}
static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;
for (top = 0; top < cnt; top++ ) {
for (bot = 0; bot < top; bot++ ) {
if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
}
}
return ;
}
/* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){
dif[0] = (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}
static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;
Dif difs[cnt];
#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);
#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif
nswap = 0;
for (idx=0; idx < cnt; idx++) {
int newval;
int step,cyc;
if ( !difs[idx] ) continue;
newval = arr[idx];
cyc = 0;
src = idx;
do {
int oldval;
step = difs[src];
difs[src] =0;
dst = src + step;
cyc += step ;
if(dst == idx+1)idx=dst;
oldval = arr[dst];
#if (DUMP_IT&1)
fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
, nswap, cyc, step, idx, oldval, newval
, src, dst, difs[dst], arr[dst]
, newval );
do_print_a("Array ", arr, cnt);
do_print_d("Steps ", difs, cnt);
#endif
arr[dst] = newval;
newval = oldval;
nswap++;
src = dst;
} while( cyc);
}
return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}
Сортировать 4 элемента с использованием cmp==0. Числа cmp ~4.34 (у родной FF ~4.52), но занимают в 3 раза больше времени, чем слияние списков. Но лучше меньше операций cmp, если у вас большие цифры или большой текст. Редактировать: исправлена ошибка
Онлайн-тест http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm
function sort4DG(cmp,start,end,n) // sort 4
{
var n = typeof(n) !=='undefined' ? n : 1;
var cmp = typeof(cmp) !=='undefined' ? cmp : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end = typeof(end) !=='undefined' ? end : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
{
swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
if (cc[13]>0)
{
swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
return n;
}
else {
cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3])); // new cc23 | c03 //repaired
if (cc[23]>0)
{
swap(n,i+2,i+3);
return n;
}
return n;
}
}
else {
if (cc[12]>0)
{
swap(n,i+1,i+2);
cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
if (cc[23]>0)
{
swap(n,i+2,i+3);
return n;
}
return n;
}
else {
return n;
}
}
return n;
}
Хорошо, если это только 6 элементов, и вы можете использовать параллелизм, хотите минимизировать условное ветвление и т. Д. Почему вы не генерируете все комбинации и не проверяете порядок? Рискну предположить, что в некоторых архитектурах это может быть довольно быстро (при условии, что у вас предварительно выделена память)
Вот три типичных метода сортировки, которые представляют три разных класса алгоритмов сортировки:
Insertion Sort: Θ(n^2)
Heap Sort: Θ(n log n)
Count Sort: Θ(3n)
Но посмотрите обсуждение Стефаном Нельссоном самого быстрого алгоритма сортировки? где он обсуждает решение, которое сводится к O(n log log n).. проверить его реализацию в C
Этот алгоритм полулинейной сортировки был представлен в статье в 1995 году:
А. Андерссон, Т. Хагеруп, С. Нильссон и Р. Раман. Сортировка по линейному времени? В материалах 27-го ежегодного симпозиума ACM по теории вычислений, стр. 427-436, 1995.