Обработка повторяющихся элементов в предыдущих быстрой сортировке
Я нашел способ более эффективно обрабатывать повторяющиеся элементы в быстрой сортировке и хотел бы знать, видел ли кто-нибудь это раньше.
Этот метод значительно снижает накладные расходы, связанные с проверкой повторяющихся элементов, что повышает производительность как с повторяющимися элементами, так и без них. Как правило, повторяющиеся элементы обрабатываются несколькими различными способами, которые я сначала перечислю.
Во-первых, существует метод голландского национального флага, который сортирует массив как [ < pivot | == pivot | unsorted | > pivot].
Во-вторых, существует метод помещения равных элементов в крайнее левое положение во время сортировки, а затем перемещения их в центр, сортировка составляет [ == pivot | < pivot | unsorted | > pivot], а затем после сортировки элементы == перемещаются в центр.
В-третьих, при разбиении Bentley-McIlroy элементы == располагаются с обеих сторон, поэтому сортировка равна [ == pivot | < pivot | unsorted | > pivot | == pivot], а затем элементы == перемещаются в середину.
Последние два метода сделаны в попытке уменьшить накладные расходы.
Мой метод
Теперь позвольте мне объяснить, как мой метод улучшает быструю сортировку за счет уменьшения количества сравнений.
Я использую две функции быстрой сортировки вместе, а не одну.
Первую функцию я назову q1, и она сортирует массив как [ < pivot | unsorted | >= pivot].
Вторую функцию я назову q2, и она сортирует массив как [ <= pivot | unsorted | > pivot].
Теперь давайте посмотрим на их использование в тандеме, чтобы улучшить обработку повторяющихся элементов.
Прежде всего, мы вызываем q1, чтобы отсортировать весь массив. Он выбирает пивот, который мы далее будем называть pivot1, а затем сортирует вокруг pivot1. Таким образом, наш массив отсортирован по этой точке как [ < pivot1 | >= pivot1 ].
Затем, для раздела [ < pivot1], мы снова отправляем его в q1, и эта часть является вполне нормальной, поэтому давайте сначала отсортируем другой раздел.
Для раздела [ >= pivot1] мы отправляем его на q2. q2 выбирает сводку, на которую мы будем ссылаться как pivot2 из этого подмассива, и сортирует ее по [ <= pivot2 | > pivot2].
Если мы посмотрим теперь на весь массив, наша сортировка выглядит как [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2]. Это очень похоже на быструю сортировку с двойным поворотом.
Теперь вернемся к подмассиву внутри q2 ([ <= pivot2 | > pivot2]).
Для раздела [ > pivot2] мы просто отправляем его обратно на q1, что не очень интересно.
Для раздела [ <= pivot2] сначала проверяем, если pivot1 == pivot2. Если они равны, то этот раздел уже отсортирован, потому что все они равные элементы! Если стержни не равны, то мы просто отправляем этот раздел на q2 снова, который выбирает свод (далее pivot3), сортирует, и если pivot3 == pivot1, то не нужно сортировать [ <= pivot 3] скоро.
Надеюсь, вы уже поняли смысл. Усовершенствование с этой техникой состоит в том, что равные элементы обрабатываются без необходимости проверять, равны ли каждый элемент и стержни. Другими словами, он использует меньше сравнений.
Есть еще одно возможное улучшение, которое я еще не пробовал - это проверка в qs2, является ли размер раздела [ <= pivot2] достаточно большим (или раздел [> pivot2] очень маленьким) по сравнению с размер его общего подмассива, а затем выполнить более стандартную проверку для повторяющихся элементов в этом случае (один из методов, перечисленных выше).
Исходный код
Вот две очень упрощенные функции qs1 и qs2. Они используют метод сортировки сходящихся указателей Седжвика. Очевидно, что они могут быть очень оптимизированы (например, они крайне плохо выбирают опорные точки), но это только для того, чтобы показать идею. Моя собственная реализация длиннее, быстрее и намного сложнее для чтения, поэтому давайте начнем с этого:
// qs sorts into [ < p | >= p ]
void qs1(int a[], long left, long right){
// Pick a pivot and set up some indicies
int pivot = a[right], temp;
long i = left - 1, j = right;
// do the sort
for(;;){
while(a[++i] < pivot);
while(a[--j] >= pivot) if(i == j) break;
if(i >= j) break;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Put the pivot in the correct spot
temp = a[i];
a[i] = a[right];
a[right] = temp;
// send the [ < p ] partition to qs1
if(left < i - 1)
qs1(a, left, i - 1);
// send the [ >= p] partition to qs2
if( right > i + 1)
qs2(a, i + 1, right);
}
void qs2(int a[], long left, long right){
// Pick a pivot and set up some indicies
int pivot = a[left], temp;
long i = left, j = right + 1;
// do the sort
for(;;){
while(a[--j] > pivot);
while(a[++i] <= pivot) if(i == j) break;
if(i >= j) break;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Put the pivot in the correct spot
temp = a[j];
a[j] = a[left];
a[left] = temp;
// Send the [ > p ] partition to qs1
if( right > j + 1)
qs1(a, j + 1, right);
// Here is where we check the pivots.
// a[left-1] is the other pivot we need to compare with.
// This handles the repeated elements.
if(pivot != a[left-1])
// since the pivots don't match, we pass [ <= p ] on to qs2
if(left < j - 1)
qs2(a, left, j - 1);
}
Я знаю, что это довольно простая идея, но она дает довольно значительное улучшение во время выполнения, когда я добавляю в стандартные улучшения быстрой сортировки (выбор сводки по медиане-3 и сортировка вставки для небольшого массива для начала). Если вы собираетесь тестировать с помощью этого кода, сделать это только на случайных данные из-за плохой поворот выбора (или улучшить выбор поворота). Чтобы использовать этот вид, вы бы позвонили:
qs1(array,0,indexofendofarray);
Некоторые тесты
Если вы хотите знать, насколько это быстро, вот немного данных для начинающих. Здесь используется моя оптимизированная версия, а не та, что приведена выше. Тем не менее, приведенный выше по-прежнему гораздо ближе по времени к быстрой сортировке с двойным поворотом, чем время std::sort.
Для очень случайных данных с 2 000 000 элементов я получаю следующие значения (от сортировки нескольких последовательных наборов данных):
std::sort - 1.609 seconds
dual-pivot quicksort - 1.25 seconds
qs1/qs2 - 1.172 seconds
Где std::sort - это сортировка стандартной библиотеки C ++, двойная сводная сортировка - это та, которая была разработана несколько месяцев назад Владимиром Ярославским, а qs1/qs2 - моя реализация быстрой сортировки.
На гораздо меньше случайных данных. с 2 000 000 элементов и сгенерированные с rand() % 1000 (что означает, что каждый элемент имеет примерно 2000 копий) время:
std::sort - 0.468 seconds
dual-pivot quicksort - 0.438 seconds
qs1/qs2 - 0.407 seconds
В некоторых случаях побеждает быстрая сортировка с двойным поворотом, и я понимаю, что быстрая сортировка с двойным поворотом могла бы быть оптимизирована больше, но то же самое можно смело утверждать для моей быстрой сортировки.
Кто-нибудь видел это раньше?
Я знаю, что это длинный вопрос / объяснение, но кто-нибудь из вас видел это улучшение раньше? Если так, то почему он не используется?