Самый быстрый способ сортировки 10 номеров? (числа 32 битные)

211

Я решаю проблему, и она включает в себя сортировку 10 чисел (int32) очень быстро. Мое приложение должно сортировать 10 чисел в миллионы раз как можно быстрее. Я выбираю набор данных из миллиардов элементов, и каждый раз мне нужно выбрать из него 10 чисел (упрощенно) и отсортировать их (и сделать выводы из отсортированного списка из 10 элементов).

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

У кого-нибудь есть идеи о том, как подойти к этой проблеме?

bodacydo
источник
14
Как бы грубо это ни звучало, ряд вложенных ifоператоров должен работать лучше всего. Избегайте петель.
Джон Алексиу
8
Ожидаете ли вы, что числа будут даны вам с любым смещением в наборе перестановок, или они будут распределены равномерно? Будет ли какая-либо связь между порядком одного списка и следующим?
Дуглас Заре
4
Весь набор данных (с миллиардами чисел) распределяется по закону Бенфорда, но когда я выбираю элементы случайным образом из этого набора, они больше не являются (я думаю).
бодасидо
13
Вы можете прочитать этот stackoverflow.com/q/2786899/995714
phuclv
11
Если вы выбираете случайным образом из миллиардов элементов, вполне возможно, что задержка для извлечения этих данных может оказать большее влияние, чем время, необходимое для сортировки выбранных элементов, даже если весь набор данных находится в ОЗУ. Вы можете проверить влияние, сравнив производительность, выбирая данные последовательно, а не случайно.
Стив С.

Ответы:

213

(Вслед за предложением HelloWorld изучить сети сортировки.)

Кажется, что сеть из 29 сравнений / свопов - самый быстрый способ сделать сортировку с 10 входами. Я использовал сеть, обнаруженную Ваксманом в 1969 году для этого примера в Javascript, который должен быть переведен непосредственно в C, поскольку это просто список ifутверждений, сравнений и свопов.

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

Вот графическое представление сети, разделенной на независимые фазы. Чтобы воспользоваться преимуществами параллельной обработки, группировка 5-4-3-4-4-4-3-2 может быть преобразована в группировку 4-4-4-4-4-4-3-2.
Сортировочная сеть с 10 входами (Waksman, 1969)

Сортировочная сеть с 10 входами (Waksman, 1969) перегруппирована

m69 '' язвительный и неприветливый ''
источник
69
предложение; использовать макрос подкачки. как#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
Питер Кордес
9
Можно ли логически показать, что это минимум?
CorsiKa
8
@corsiKa Да, сортировочные сети были областью исследований с первых дней информатики. Во многих случаях оптимальные решения известны десятилетиями. См en.wikipedia.org/wiki/Sorting_network
М69 «» и неприветливый элегантный «»
8
Я сделал Jsperf для тестирования и могу подтвердить, что сетевая сортировка более чем в 20 раз быстрее, чем собственная сортировка браузеров. jsperf.com/fastest-10-number-sort
Даниэль
9
@Katai Это разрушит любую оптимизацию, которую может произвести ваш компилятор. Плохая идея. Прочитайте это для получения дополнительной информации en.wikipedia.org/wiki/…
Antzi
88

Когда вы имеете дело с этим фиксированным размером, взгляните на Сортировка сетей . Эти алгоритмы имеют фиксированное время выполнения и не зависят от их ввода. Для вашего варианта использования у вас нет таких накладных расходов, как у некоторых алгоритмов сортировки.

Битонная сортировка - это реализация такой сети. Этот лучше всего работает с len (n) <= 32 на процессоре. На больших входах вы можете подумать о переходе на графический процессор. https://en.wikipedia.org/wiki/Sorting_network

Кстати, здесь есть хорошая страница для сравнения алгоритмов сортировки (хотя в ней отсутствует bitonic sort.

http://www.sorting-algorithms.com

Привет мир
источник
3
@ ErickG.Hagstrom Есть много решений; пока они используют 29 сравнений, они одинаково эффективны. Я использовал решение Ваксмана с 1969 года; он, очевидно, был первым, кто обнаружил 29-версию сравнения.
m69 '' язвительный и неприветливый ''
1
Да, @ m69. Их более миллиона. Решение Ваксмана имеет длину 29 и глубину 9. Связанное мною решение является улучшением по сравнению с измерением глубины: длина = 29, глубина = 8. Конечно, при реализации в C глубина не имеет значения.
Эрик Дж. Хагстрем
4
@ ErickG.Hagstrom По-видимому, есть 87 решений с глубиной 7, первое из которых было найдено Кнутом в 1973 году, но я не смог найти ни одного из них с помощью быстрого Google. larc.unt.edu/ian/pubs/9-input.pdf (см. Заключение,
стр. 14
4
@ ErickG.Hagstrom: глубина может не иметь значения «на уровне C», но, вероятно, после того, как компилятор и процессор закончат с ним, есть некоторый шанс, что он будет частично распараллелен внутри процессора, и, следовательно, может помочь меньшая глубина. Конечно, в зависимости от процессора: некоторые процессоры относительно просты и выполняют одно за другим, в то время как некоторые процессоры могут выполнять несколько операций в полете, в частности, вы можете получить очень разную производительность для любых нагрузок и сохранения в стеке, которые необходимы в Чтобы манипулировать 10 переменных, в зависимости от того, как они сделаны.
Стив Джессоп
1
@ ErickG.Hagstrom Это было не сразу ясно из статьи Иэна Парберри, но сети глубины 7 имеют длину больше 29. См. Кнут, «Искусство компьютерного программирования», том III, §5.3.4, рис. , 49 и 51.
m69 '' язвительный и неприветливый ''
33

Используйте сортировочную сеть, у которой есть сравнения в группах по 4, так что вы можете сделать это в SIMD-регистрах. Пара упакованных инструкций min / max реализует упакованную функцию компаратора. Извините, у меня нет времени сейчас искать страницу, которую я помню об этом, но, надеюсь, поиск по SIMD или SSE сортировочным сетям что-то даст.

x86 SSE имеет упакованные 32-битные целочисленные инструкции min и max для векторов четырех 32-битных целых. AVX2 (Haswell и более поздние версии) имеют то же самое, но для векторов 256b по 8 дюймов. Есть также эффективные инструкции перемешивания.

Если у вас много независимых небольших сортировок, может быть возможно выполнить 4 или 8 сортировок параллельно, используя векторы. Особенно если вы выбираете элементы случайным образом (так что сортируемые данные в любом случае не будут непрерывными в памяти), вы можете избежать перемешивания и просто сравнивать их в нужном вам порядке. 10 регистров для хранения всех данных из 4 (AVX2: 8) списков по 10 дюймов по-прежнему оставляют 6 регистров на пустом месте.

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

Питер Кордес
источник
26

Как насчет развернутой сортировки без веток?

#include <iostream>
#include <algorithm>
#include <random>

//return the index of the minimum element in array a
int min(const int * const a) {
  int m = a[0];
  int indx = 0;
  #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); 
  //see http://stackoverflow.com/a/7074042/2140449
  TEST(1);
  TEST(2);
  TEST(3);
  TEST(4);
  TEST(5);
  TEST(6);
  TEST(7);
  TEST(8);
  TEST(9);
  #undef TEST
  return indx;
}

void sort( int * const a ){
  int work[10];
  int indx;
  #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; 
  //get the minimum, copy it to work and set it at max_int in a
  GET(0);
  GET(1);
  GET(2);
  GET(3);
  GET(4);
  GET(5);
  GET(6);
  GET(7);
  GET(8);
  GET(9);
  #undef GET
  #define COPY(i) a[i] = work[i];
  //copy back to a
  COPY(0);
  COPY(1);
  COPY(2);
  COPY(3);
  COPY(4);
  COPY(5);
  COPY(6);
  COPY(7);
  COPY(8);
  COPY(9);
  #undef COPY
}

int main() {
  //generating and printing a random array
  int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle( a, a+10, g);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  }
  std::cout << std::endl;

  //sorting and printing again
  sort(a);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  } 

  return 0;
}

http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

Единственные соответствующие строки - первые два #define.

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


эталонный тест

Я сравнил сеть сортировки, и мой код выглядит медленнее. Однако я попытался удалить развертывание и копию. Запуск этого кода:

#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

int min(const int * const a, int i) {
  int m = a[i];
  int indx = i++;
  for ( ; i<10; i++) 
    //see http://stackoverflow.com/a/7074042/2140449
    (m > a[i]) && (m = a[i], indx = i ); 
  return indx;
}

void sort( int * const a ){
  for (int i = 0; i<9; i++)
    std::swap(a[i], a[min(a,i)]); //search only forward
}


void sortNet10(int * const data) {  // ten-input sorting network by Waksman, 1969
    int swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
}


std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
  std::mt19937 g(seed);
  int a[10] = {10,11,12,13,14,15,16,17,18,19};
  std::chrono::high_resolution_clock::time_point t1, t2; 
  t1 = std::chrono::high_resolution_clock::now();
  for (long i = 0; i < 1e7; i++) {
    std::shuffle( a, a+10, g);
    func(a);
  }
  t2 = std::chrono::high_resolution_clock::now();
  return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
}

int main() {
  std::random_device rd;
  for (int i = 0; i < 10; i++) {
    const int seed = rd();
    std::cout << "seed = " << seed << std::endl;
    std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
    std::cout << "sort:      " << benchmark(sort,      seed).count() << std::endl;
  }
  return 0;
}

Я последовательно получаю лучший результат для сортировки без ветвления по сравнению с сетью сортировки.

$ gcc -v
gcc version 5.2.0 (GCC) 
$ g++ -std=c++11 -Ofast sort.cpp && ./a.out
seed = -1727396418
sortNet10: 2.24137
sort:      2.21828
seed = 2003959850
sortNet10: 2.23914
sort:      2.21641
seed = 1994540383
sortNet10: 2.23782
sort:      2.21778
seed = 1258259982
sortNet10: 2.25199
sort:      2.21801
seed = 1821086932
sortNet10: 2.25535
sort:      2.2173
seed = 412262735
sortNet10: 2.24489
sort:      2.21776
seed = 1059795817
sortNet10: 2.29226
sort:      2.21777
seed = -188551272
sortNet10: 2.23803
sort:      2.22996
seed = 1043757247
sortNet10: 2.2503
sort:      2.23604
seed = -268332483
sortNet10: 2.24455
sort:      2.24304
DarioP
источник
4
Результаты не очень впечатляющие, но на самом деле то, что я ожидал. Сортировочная сеть сводит к минимуму сравнения, а не свопы. Когда все значения уже находятся в кеше, сравнения намного дешевле, чем свопы, поэтому выборочная сортировка (которая минимизирует количество свопов) имеет преимущество. (и сравнений не так уж и много: сеть с 29 сравнениями, до 29 свопов ?; выборочная сортировка с 45 сравнениями и максимум 9 свопами)
пример
7
Да, и у него есть ответвления - если только линия for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i ); не очень хорошо оптимизирована. (короткое замыкание обычно является формой ветвления)
пример
1
@EugeneRyabtsev, что тоже, но он постоянно подается с одинаковыми случайными последовательностями, поэтому его следует отменить. Я пытался измениться std::shuffleс for (int n = 0; n<10; n++) a[n]=g();. Время выполнения уменьшилось вдвое, и теперь сеть работает быстрее.
DarioP
Как это сравнить с libc ++ std::sort?
gnzlbg
1
@gnzlbg Я тоже старался, std::sortно он работал так плохо, что даже не включил его в тест. Я предполагаю, что с крошечными наборами данных это довольно накладные расходы.
DarioP
20

Вопрос не говорит о том, что это какое-то веб-приложение. Единственное, что бросилось в глаза, было:

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

Как инженер по программному и аппаратному обеспечению это абсолютно кричит "FPGA" для меня. Я не знаю, какие выводы вы должны сделать из отсортированного набора чисел или откуда поступают данные, но я знаю, что было бы почти тривиально обрабатывать где-то от ста миллионов до миллиарда этих «сортировать и анализировать "операций в секунду . В прошлом я занимался секвенированием ДНК с помощью FPGA. Почти невозможно превзойти огромную вычислительную мощность ПЛИС, когда проблема хорошо подходит для решения такого типа.

На каком-то уровне единственным ограничивающим фактором становится то, как быстро вы можете поместить данные в FPGA и как быстро вы можете получить их.

Для справки я разработал высокопроизводительный процессор обработки изображений в реальном времени, который получал 32-битные данные RGB-изображения со скоростью около 300 миллионов пикселей в секунду. Данные передаются на другой конец через фильтры КИХ, умножители матриц, таблицы поиска, блоки обнаружения краев пространства и ряд других операций. Все это на сравнительно небольшой FPGA Xilinx Virtex2 с тактовой частотой от 33 МГц до, если я правильно помню, 400 МГц. О, да, он также имел реализацию контроллера DDR2 и управлял двумя банками памяти DDR2.

ПЛИС может выводить своего рода десять 32-битных чисел на каждом тактовом переходе, работая на сотнях МГц. В начале операции будет небольшая задержка, поскольку данные заполняют конвейер обработки данных. После этого вы сможете получить один результат за часы. Или больше, если обработка может быть распараллелена посредством репликации конвейера сортировки и анализа. Решение в принципе почти тривиально.

Дело в том, что если приложение не привязано к ПК, а поток данных и обработка «совместимы» с решением FPGA (автономным или в виде карты сопроцессора в машине), вы не сможете иметь возможность превзойти достижимый уровень производительности с помощью программного обеспечения, написанного на любом языке, независимо от алгоритма.

РЕДАКТИРОВАТЬ:

Просто запустил быстрый поиск и нашел бумагу, которая может быть вам полезна. Похоже, это восходит к 2012 году. Вы можете сделать намного лучше в производительности сегодня (и даже тогда). Вот:

Сортировка сетей на ПЛИС

Мартин
источник
10

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

С его помощью можно создать очень быструю сортировку по 10 числам.

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 10 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

Обратите внимание, что вместо if (compare) swapутверждения мы явно кодируем троичные операторы для min и max. Это поможет подтолкнуть компилятор к использованию кода без ветвей.

Ориентиры

Следующие тесты скомпилированы с помощью clang -O3 и запущены на моем MacBook Air в середине 2012 года.

Сортировка случайных данных

Сравнивая его с кодом DarioP, вот количество миллисекунд, потраченных на сортировку 1 миллиона 32-битных массивов int размером 10:

Сортировка в жестком коде Net 10: закодированная 88,774 мс Шаблонная сортировка
Бозе-Нельсона 10: 27,815 мс

Используя этот шаблонный подход, мы также можем генерировать сети сортировки по времени компиляции для другого числа элементов.

Время (в миллисекундах) сортировать 1 миллион массивов разных размеров.
Количество миллисекунд для массивов размером 2, 4, 8 составляет 1,943, 8,655 и 20,246 соответственно.
Синхронизированное время статической сортировки Бозе-Нельсона C ++

Кредиты для Гленну Тейтельбауму для развернутого рода вставок.

Вот средние часы на сортировку для маленьких массивов из 6 элементов. Код теста и примеры можно найти по этому вопросу:
Самый быстрый вид массива с фиксированной длиной 6 int

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

Он работает так же быстро, как самый быстрый пример в вопросе для 6 элементов.

Производительность по сортировке отсортированных данных

Часто входные массивы могут быть уже отсортированы или в основном отсортированы.
В таких случаях вставка сортировки может быть лучшим выбором.

введите описание изображения здесь

Вы можете выбрать подходящий алгоритм сортировки в зависимости от данных.

Код, используемый для тестов, можно найти здесь .

Векторизованное
источник
Есть ли шанс, что вы можете добавить сравнение для моего алгоритма ниже?
Гленн Тейтельбаум
@GlennTeitelbaum есть ли шанс, что вы добавили это в свои тесты и раскрыли средства и результаты?
Седобородый
Престижность для добавления данных по сортировке отсортированного ввода.
Седобородый
В некоторых системах v1 = v0 < v1 ? v1 : v0; // Maxможет все еще отрасли, в этом случае он может быть заменен , v1 += v0 - tпотому что , если tесть , v0то v1 + v0 -t == v1 + v0 - v0 == v1еще tесть v1иv1 + v0 -t == v1 + v0 - v1 == v0
Гленн Тейтельбаума
Тернар обычно компилируется в инструкцию maxssили minssна современных компиляторах. Но в тех случаях, когда это не работает, можно использовать другие способы обмена. :)
Векторизовано
5

Хотя сетевая сортировка имеет хорошие шансы быть быстрой на небольших массивах, иногда вы не можете превзойти сортировку вставкой, если она должным образом оптимизирована. Например, пакетная вставка с 2 элементами:

{
    final int a=in[0]<in[1]?in[0]:in[1];
    final int b=in[0]<in[1]?in[1]:in[0];
    in[0]=a;
    in[1]=b;
}
for(int x=2;x<10;x+=2)
{
    final int a=in[x]<in[x+1]?in[x]:in[x+1];
    final int b=in[x]<in[x+1]?in[x+1]:in[x];
    int y= x-1;

    while(y>=0&&in[y]>b)
    {
        in[y+2]= in[y];
        --y;
    }
    in[y+2]=b;
    while(y>=0&&in[y]>a)
    {
        in[y+1]= in[y];
        --y;
    }
    in[y+1]=a;
}
кроличий садок
источник
Не уверен, почему вы повторяете in[y+2]= in[y];, опечатка?
Гленн Тейтельбаум
Вау, как я это сделал? И как это заняло так много времени, чтобы кто-то заметил? Ответ: Это не опечатка: я адаптировал другой алгоритм, который имел и ключ, и массив значений.
Уоррен
3

Вы можете полностью развернуть insertion sort

Чтобы сделать это проще, templateможно использовать рекурсивные s без каких-либо дополнительных функций. Поскольку он уже есть template, intможет быть и templateпараметром. Это также делает размеры массива кодирования, отличные от 10, тривиальными для создания.

Обратите внимание, что сортировать int x[10]вызовы insert_sort<int, 9>::sort(x);так как класс использует индекс последнего элемента. Это можно обернуть, но это будет больше кода для чтения.

template <class T, int NUM>
class insert_sort;

template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
    static void place(T *x) {}
    static void sort(T * x) {}
};

template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
    static void place(T *x)
    {
        T t1=x[NUM-1];
        T t2=x[NUM];
        if (t1 > t2)
        {
            x[NUM-1]=t2;
            x[NUM]=t1;
            insert_sort<T,NUM-1>::place(x);
        }
    }
    static void sort(T * x)
    {
        insert_sort<T,NUM-1>::sort(x); // sort everything before
        place(x);                    // put this item in
    }
};

В моем тестировании это было быстрее, чем примеры сортировки сети.

Гленн Тейтельбаум
источник
0

По тем же причинам , которые я описал здесь , на следующие функции сортировки, sort6_iterator()и sort10_iterator_local(), должен выполнять хорошо, когда сортировка сеть была взята из здесь :

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Для вызова этой функции я передал ей std::vectorитератор.

Мэтью К.
источник
0

Для сортировки вставкой требуется в среднем 29,6 сравнений для сортировки 10 входных данных с наилучшим регистром из 9 и худшим из 45 (с учетом входных данных в обратном порядке).

{9,6,1} Оболочка сортировки потребует в среднем 25,5 сравнений для сортировки 10 входных данных. Наилучший случай - 14 сравнений, наихудший - 34, а для сортировки обратного ввода требуется 22.

Таким образом, использование сортировки по типу оболочки вместо сортировки по вставке уменьшает средний случай на 14%. Хотя лучший случай увеличен на 56%, худший - на 24%, что важно в приложениях, где важно контролировать производительность наихудшего случая. Обратный случай уменьшен на 51%.

Поскольку вы, похоже, знакомы с сортировкой вставок, вы можете реализовать алгоритм как сеть сортировки для {9,6}, а затем добавить сортировку вставок ({1}) после этого:

i[0] with i[9]    // {9}

i[0] with i[6]    // {6}
i[1] with i[7]    // {6}
i[2] with i[8]    // {6}
i[3] with i[9]    // {6}

i[0 ... 9]        // insertion sort
Олоф Форшелл
источник