Кто-либо видел это улучшение quicksort прежде?

Обработка повторенных элементов в предыдущем quicksorts

Я нашел способ обработать повторенные элементы более эффективно в quicksort и хотел бы знать, видел ли кто-либо сделанный прежде.

Этот метод значительно уменьшает издержки, вовлеченные в проверку повторные элементы, которая улучшает производительность и с и без повторных элементов. Как правило, повторные элементы обрабатываются несколькими различными способами, которыми я сначала перечислю.

Во-первых, существует голландский метод Национального флага, которые сортируют массив как [ < pivot | == pivot | unsorted | > pivot].

Во-вторых, существует метод помещения равных элементов к крайне левому во время вида и затем перемещения их к центру, который вид [ == pivot | < pivot | unsorted | > pivot] и затем после вида == элементы перемещены в центр.

В-третьих, Бентли-McIlroy, делящая, помещает == элементы обеим сторонам так вид [ == pivot | < pivot | unsorted | > pivot | == pivot] и затем == элементы перемещены в середину.

Последние два метода сделаны в попытке уменьшить издержки.

Мой метод

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

Первая функция я буду звонить q1 и это сортирует массив как [ < pivot | unsorted | >= pivot].

Вторая функция я буду звонить q2 и это сортирует массив как [ <= pivot | unsorted | > pivot].

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

В первую очередь, мы звоним q1 отсортировать целый массив. Это выбирает центр, к которому мы далее сошлемся как pivot1 и затем виды вокруг pivot1. Таким образом наш массив отсортирован к этой точке как [ < pivot1 | >= pivot1 ].

Затем для [ < pivot1] раздел, мы отправляем его в q1 снова, и та часть довольно нормальна так, давайте отсортируем другой раздел сначала.

Для [ >= pivot1] раздел, мы отправляем его в q2. q2 choses центр, к которому мы сошлемся как pivot2 из этого подмассива и видов это в [ <= pivot2 | > pivot2].

Если мы смотрим теперь на целый массив, наша сортировка похожа [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2]. Это очень походит на двойной центр quicksort.

Теперь, давайте возвратимся к подмассиву в 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);
}

Я знаю, что это - довольно простая идея, но она дает довольно существенное улучшение во времени выполнения, когда я добавляю в стандарте quicksort улучшения (median-3 выбор центра и вид вставки для небольшого массива для запуска). Если Вы собираетесь протестировать использование этого кода, только сделайте это на случайных данных из-за плохого выбора центра (или улучшите выбор центра). Для использования этого вида, Вы звонили бы:

qs1(array,0,indexofendofarray);

Некоторые сравнительные тесты

Если Вы хотите знать, как быстро это, вот определенные данные для начинающих. Это использует мою оптимизированную версию, не один данный выше. Однако один данный выше еще намного ближе вовремя к двойному центру quicksort, чем std::sort время.

На очень случайных данных с 2 000 000 элементов я получаю эти времена (от сортировки нескольких последовательных наборов данных):

std::sort - 1.609 seconds  
dual-pivot quicksort - 1.25 seconds  
qs1/qs2 - 1.172 seconds

Где std::sort вид Библиотеки Стандарта C++, двойной центр quicksort является тем, который вышел несколько месяцев назад Vladimir Yaroslavskiy, и qs1/qs2 моя quicksort реализация.

На намного менее случайных данных. с 2 000 000 элементов и сгенерированный с rand() % 1000 (что означает, что каждый элемент имеет копии примерно 2000 года), времена:

std::sort - 0.468 seconds  
dual-pivot quicksort - 0.438 seconds  
qs1/qs2 - 0.407 seconds

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

Кто-либо видел это прежде?

Я знаю, что это - долгий вопрос/объяснение, но какой-либо из Вас видел это улучшение прежде? Если так, затем почему это не то, что я был используемым?