Существует ли процедура сортировки быстрее, чем qsort?

Question

Это не алгоритмический вопрос, а вопрос реализации.

У меня есть структура данных, которая выглядит следующим образом:

struct MyStruct {
   float val;
   float val2;
   int idx;
}

Я перебираю массив из примерно 40 миллионов элементов,и назначить поля 'val' для элемента, а поле 'idx' для индекса.

Затем я звоню:

MyStruct* theElements = new MyStruct[totalNum];
qsort(theElements, totalNum, sizeof(MyStruct), ValOrdering);

и затем, когда я заполняюв val2, в обратном порядке:

qsort(theElements, totalNum, sizeof(MyStruct), IndexOrdering);

, где

static int ValOrdering(const void* const v1, const void* const v2)
{
  if (((struct MyStruct*) v1)->val < ((struct MyStruct*) v2)->val)
    return -1;

  if (((struct MyStruct*) v1)->val> ((struct MyStruct*) v2)->val)
    return 1;

  return 0;
}

и

static int IndexOrdering(const void* const v1, const void* const v2)
{
  return ((struct MyStruct*) v1)->idx- ((struct MyStruct*) v2)->idx;
}

. Для выполнения обеих сортировок требуется 4 секунды.4 секунды кажутся чем-то большим, чем 40 миллионов элементов, которые используют процессор i5 с частотой 3 ГГц;Есть ли более быстрый подход?Я использую vs2010 с компилятором Intel (который имеет сортировки, но не имеет таких структур, которые я вижу).

Обновление : Использование std :: sort сокращает время ожидания примерно на 0,4 секунды.времени выполнения, которое называется как:

std::sort(theElements, theElements + totalPixels, ValOrdering);
std::sort(theElements, theElements + totalPixels, IndexOrdering);

и

bool GradientOrdering(const MyStruct& i, const MyStruct& j){
    return i.val< j.val;
}
bool IndexOrdering(const MyStruct& i, const MyStruct& j){
    return i.idx< j.idx;
}

, добавление ключевого слова inline к предикатам не имеет значения.Так как у меня есть, и в спецификации предусмотрена четырехъядерная машина, я проверю какую-то многопоточную сортировку следующим образом.

Обновление 2 : После @SirGeorge и @stark я взялвзгляд на одну сортировку, выполненную с помощью перенаправления указателя:

bool GradientOrdering(MyStruct* i, MyStruct* j){
    return i->val< j->val;
}
bool IndexOrdering(MyStruct* i, MyStruct* j){
    return i->idx< j->idx;
} 

Несмотря на то, что есть только один вызов сортировки (в процедуру GradientOrdering), результирующий алгоритм занимает 5 секунд, на 1 секунду дольше, чем подход qsort,Похоже, что std :: sort пока побеждает.

Обновление 3 : Похоже, Intel tbb::parallel_sort победил, уменьшив время выполнения одной сортировки до 0,5 с на моемсистема (итак, 1,0 с для обоих, что означает, что она довольно хорошо масштабируется по сравнению с оригинальными 4,0 для обоих).Я попытался использовать параллельную причуду, предложенную Microsoft здесь , но, поскольку я уже использую tbb, а синтаксис для parallel_sort идентичен синтаксису для std::sort, я мог бы использовать свой ранее std::sort компараторов, чтобы все закончить.

Я также использовал предложение @ gbulmer (на самом деле, осознание удара по голове), что у меня уже есть оригинальные индексы, поэтому вместо второго вида,Мне просто нужно назначить второй массив с индексами от первого обратно в отсортированном порядке.Я могу обойтись без этого использования памяти, потому что я развертываю только на 64-битных машинах с по крайней мере 4 ГБ ОЗУ (хорошо, что эти спецификации были разработаны заранее);без этого знания второй сорт был бы необходим. Предложение

@ gbulmer дает наибольшее ускорение, но первоначальный вопрос задавался о самой быстрой сортировке.std::sort - самый быстрый однопоточный, parallel_sort - самый быстрый многопоточный, но никто не дал такого ответа, поэтому я даю чек @gbulmer.

Answer 1

Вообще говоря, std::sort в C ++, расположенный в algorithm, превзойдет qsort, поскольку он позволяет компилятору оптимизировать косвенный вызов по указателю на функцию и облегчает компилятору выполнение встраивания.Тем не менее, это будет только постоянный фактор ускорения;qsort уже использует очень быстрый алгоритм сортировки.

Обратите внимание, что если вы решите переключиться на std::sort, то ваш функтор сравнения должен будет измениться.std::sort принимает простой результат сравнения, возвращающий bool, а std::qsort принимает функтор, возвращающий -1, 0 или 1, в зависимости от ввода.

Answer 2

Набор данных огромен по сравнению с кешем, поэтому он будет ограничен кешем памяти.

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

Рассмотрите возможность разбиения структуры на две структуры в двух массивах.

В качестве эксперимента сравните проход 1 с проходом, где структура только { float val; int idx; };

Если это связано с кэшем и пропускной способностью, это должно иметь существенное значение.

Если ключевым вопросом является локальность кэша, возможно, стоит рассмотреть возможность многофакторного слияния или сортировки в Shell; что-нибудь, чтобы улучшить местность.

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

Как получается поле idx? Похоже, это исходная позиция в массиве. Индекс исходной записи?

Если это так, просто выделите второй массив и скопируйте первый во второй:

struct { float val; float val2; int idx } sortedByVal[40000000];
struct { float val; float val2 } sortedbyIdx[40000000];

for (int i=0; i<40000000; ++i) {
    sortedbyIdx[sortedByVal[i].idx].val = sortedByVal[i].val;
    sortedbyIdx[sortedByVal[i].idx].val2 = sortedByVal[i].val2;
}

Второго сорта нет. Если это так, объедините распределение значения val2 с этим проходом.

Редактировать

Мне было любопытно, что касается относительной производительности, поэтому я написал программу для сравнения функций сортировки «библиотеки» C, qsort, mergesort, heapsort, а также для сравнения сортировки по idx с копией в idx. Он также пересортирует отсортированные значения, чтобы разобраться с этим. Это тоже довольно интересно. Я не реализовывал и не тестировал сортировку Shell, которая часто превосходит qsort на практике.

Программа использует параметры командной строки, чтобы выбрать, какую сортировку и выполнять сортировку по idx, или просто копировать. Код: http://pastebin.com/Ckc4ixNp

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

Я запускал его на старом MacBook Pro 2,2 ГГц Intel Core 2 Duo. Некоторые временные характеристики зависят от ОС C.

Сроки (немного переформатированы):

qsort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration =            16.304194
Re-order to idx by copying - duration = 2.904821
Sort in-order data - duration =         2.013237
Total duration = 21.222251
User Time:       20.754574
System Time:      0.402959

mergesort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration =            25.948651
Re-order to idx by copying - duration = 2.907766
Sort in-order data - duration =         0.593022
Total duration = 29.449438
User Time:       28.428954
System Time:      0.973349

heapsort(data, number-of-elements=40000000, element-size=12)
Sorting by val - duration =            72.236463
Re-order to idx by copying - duration = 2.899309
Sort in-order data - duration =        28.619173
Total duration = 103.754945
User Time:       103.107129
System Time:       0.564034

ПРЕДУПРЕЖДЕНИЕ : это одиночные прогоны. Для получения разумной статистики понадобится много прогонов.

Код на pastebin фактически сортирует 8-байтовый массив с уменьшенным размером. На первом проходе нужны только val и idx, и поскольку массив добавляется при добавлении val2, в первом массиве нет необходимости в val2. Эта оптимизация заставляет функции сортировки копировать меньшую структуру, а также помещать больше структур в кеш, что хорошо. Я был разочарован тем, что это дает улучшение в qsort на несколько%. Я интерпретирую это как qsort быстро получает куски сортируются по размеру, который помещается в кэш.

Та же самая стратегия уменьшенного размера дает более чем 25% -ное улучшение для порта.

Синхронизация для 8-байтовых структур, без val2:

qsort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration =            16.087761
Re-order to idx by copying - duration = 2.858881
Sort in-order data - duration =         1.888554
Total duration = 20.835196
User Time:       20.417285
System Time:      0.402756

mergesort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration =            22.590726
Re-order to idx by copying - duration = 2.860935
Sort in-order data - duration =         0.577589
Total duration = 26.029249
User Time:       25.234369
System Time:      0.779115

heapsort(data, number-of-elements=40000000, element-size=8)
Sorting by val - duration =            52.835870
Re-order to idx by copying - duration = 2.858543
Sort in-order data - duration =        24.660178
Total duration = 80.354592
User Time:       79.696220
System Time:      0.549068

ПРЕДУПРЕЖДЕНИЕ : Это одиночные прогоны. Для получения разумной статистики понадобится много прогонов.

Answer 3

std::sort() должно быть более чем на 10% быстрее.Однако вам нужно две вещи:

1. Использование указателя на функцию берет героику из компилятора, чтобы обнаружить, что функция может быть встроенной.Функциональный объект с оператором вызова встроенной функции сравнительно легко встроить.
2. В режиме отладки ядро ​​std::sort() не будет оптимизировано, а qsort() оптимизировано: попробуйте скомпилировать в режиме выпуска.

Answer 4

При сортировке по индексу radix sort может быть быстрее быстрой сортировки. Вы, вероятно, захотите сделать это с базой, равной степени 2 (так что вы можете использовать побитовые операции вместо модуля).

Answer 5

Прямо сейчас вы сортируете array of structures, что означает, что каждый своп в массиве равен как минимум двум присваиваниям (копирование целых структур).Вы можете попытаться отсортировать массив указателей на структуры, что сэкономит вам много времени на копирование (просто копирование указателей), но вы будете использовать больше памяти.Другое преимущество сортировки массива указателей состоит в том, что у вас может быть несколько из них (каждый отсортирован по-разному) - опять же, требуется больше памяти.Дополнительные косвенные указатели могут быть дорогими, хотя.Вы также можете попытаться использовать оба подхода, предложенные здесь другими вместе: std::qsort с массивом указателей - и посмотреть, есть ли какое-либо ускорение в вашем случае.

Answer 6

Все алгоритмы сортировки известны и существуют.Их легко реализовать.Оцените их.

Быстрая сортировка может быть не самой быстрой во всех случаях, но в среднем она довольно эффективна.Однако 40 миллионов записей - это много, сортировка, которая за 3-4 секунды не является неслыханной.

edit

Я суммирую мои комментарии: доказано, чтов модели Тьюринга (здесь пишется прямо !!!) алгоритмы сортировки сравнения ограничены Ω (n log n).Поэтому в плане сложности не так много места для улучшения, но дьявол кроется в деталях.Чтобы обнаружить различия в производительности эквивалентных по сложности алгоритмов - вам нужно сравнить их и посмотреть на результаты.

Если, однако, у вас есть некоторые дополнительные знания о ваших данных (например, idx будетнаходиться в пределах определенного предустановки и относительно небольшого диапазона), вы можете использовать алгоритмы, которые не являются сравнительными и имеют улучшение сложности.Вам все равно следует провести сравнительный анализ, чтобы убедиться, что улучшение действительно происходит для ваших данных, но для большого объема разница между Ω (n log n) и Ω (n), вероятно, будет заметна.Примером таких алгоритмов является сортировка по группам.

Для более полного анализа списка и сложности - начните здесь .