Обработка повторяющихся элементов в предыдущих операциях быстрой сортировки
Я нашел способ более эффективно обрабатывать повторяющиеся элементы в quicksort и хотел бы знать, видел ли кто-нибудь это раньше.
Этот метод значительно снижает накладные расходы, связанные с проверкой повторяющихся элементов, что повышает производительность как с повторяющимися элементами, так и без них. Как правило, повторяющиеся элементы обрабатываются несколькими различными способами, которые я сначала перечислю.
Во-первых, существует метод голландского национального флага, который сортирует массив как [ < pivot | == pivot | unsorted | > pivot].
Во-вторых, существует способ поместить равные элементы в крайнее левое положение во время сортировки, а затем перемещать их в центр, сортировка [ == pivot | < pivot | unsorted | > pivot], а затем после сортировки элементы == перемещаются в центр.
В-третьих, разбиение Bentley-McIlroy ставит элементы == на обе стороны, поэтому сортировка [ == pivot | < pivot | unsorted | > pivot | == pivot], а затем элементы == перемещаются в середину.
Последние два метода выполняются с целью уменьшения накладных расходов.
Мой метод
Теперь позвольте мне объяснить, как мой метод улучшает быструю сортировку, уменьшая количество сравнений. Я использую две функции quicksort вместе, а не только одну.
Первая функция, которую я вызову 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. Они используют метод сортировки Sedgewick для сходящихся указателей. Очевидно, что они могут быть очень оптимизированы (например, они выбирают крайне мало), но это просто для того, чтобы показать эту идею. Моя собственная реализация длиннее, быстрее и намного сложнее читать, поэтому начните с этого:
// 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 - это сортировка стандартной библиотеки С++, двухповоротная быстродействующая сортировка - это то, что вышло несколько месяцев назад Владимиром Ярославским, а qs1/qs2 - моя реализация быстрой сортировки.
На гораздо меньших случайных данных. с 2 000 000 элементов и сгенерировано с помощью rand() % 1000 (что означает, что каждый элемент имеет примерно 2000 копий):
std::sort - 0.468 seconds
dual-pivot quicksort - 0.438 seconds
qs1/qs2 - 0.407 seconds
Есть несколько случаев, когда выигрыш двухпользовательской быстрой сортировки выигрывает, и я понимаю, что быстродействующая сортировка с двойным шарниром может быть оптимизирована больше, но то же самое можно было бы с уверенностью сказать для моей быстрой сортировки.
Кто-нибудь видел это раньше?
Я знаю, что это длинный вопрос/объяснение, но кто-нибудь из вас видел это улучшение раньше? Если да, то почему он не используется?
