Создание минимальной кучи с использованием одной рекурсии - PullRequest
Новая
       28

Создание минимальной кучи с использованием одной рекурсии

0 голосов
/ 08 июля 2019

Это попытка заставить кучи сортировать кучи исключительно с помощью вызовов функций. Проблема в том, что для его завершения требуется слишком много времени, дольше, чем для простой пузырьковой сортировки, написанной в том же проекте, почти 100 секунд против 42 пузырька с 100000 записей в порядке убывания. Слияние и быстрая сортировка не прошли ни секунды. Не говоря уже о том, что он падает на 100000, если компилятору не удается выполнить оптимизацию хвостового вызова.

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

int heap_sort_step(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    char bfl = (nextl<len)|((nextr<len)<<1);

    switch(bfl)
    {
        case 3:
        case 2:
            while(v[i] > heap_sort_step(v, len, nextr))
                swap(v + i, v + nextr);
        case 1:
            while(v[i] > heap_sort_step(v, len, nextl))
                swap(v + i, v + nextl);
        default:
            return v[i];
    }

}

void heap_sort(int v[], int len){
    return (len > 1)?
                (heap_sort_step(v, len, 0),
                 heap_sort(v + 1, len - 1)):
            NULL;
}

heap_sort (int v [], int len) берет массив и его размер и строит минимальную кучу для каждого элемента в массиве, используя heap_sort_step (), упорядочивая его. Хвостовые вызовы необходимы здесь.

heap_sort_step (int v [], int len, int i) принимает массив, его размер и индекс для построения кучи, с уравнениями, как показано в nextl и nextr, 2i + 1 и 2i + 2, начиная с i = 0. «bfl» - это трюк для оптимизации (небольшие улучшения по сравнению с использованием ifs), чтобы решить, к каким ветвям перейти или просто вернуть текущее значение, посмотрев, есть ли еще пункты впереди. Коммутатор использует падение и находится там, где строится куча, 3 и 2 означают, что есть вещи справа (0b11 и 0b10), а 1 означает, что есть вещи слева (0b01), поведение по умолчанию возвращает текущее число. Раньше это было написано как: 

int heap_sort_step(int v[], int len, int i){
    int nextl = (((i + 1) * 2) - 1), nextr = nextl + 1;
    if(nextl < len)
        while(v[i] > heap_sort_step(v, len, nextl))
            swap(v + i, v + nextl);

    if(nextr < len)
        while(v[i] > heap_sort_step(v, len, nextr))
            swap(v + i, v + nextr);

    return v[i];
}

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

На данный момент я почти уверен, что это просто плохая реализация, и хочу знать, является ли это проблемой сложности, вызванной изменениями, или чем-то еще. Можно ли сделать так, чтобы она конкурировала с mergesort и quicksort, используя одну и ту же концепцию? Это должно быть O n (log (n)), верно?

Ответы [ 2 ]

0 голосов
/ 08 июля 2019

После нескольких изменений он работает как шарм, вот решение:

Это неполно:

Куча формируется снова и снова для каждого элемента, поэтому, как указал Джон, это работает как странная сортировка выбора.

Для завершения добавлены две новые функции: 

void sift(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    int next  = 0;

    if(nextr < len)
        if(v[i] > v[nextr]){
            if(v[nextr] < v[nextl])
                swap(v + i, v + (next = nextr));
            else
                swap(v + i, v + (next = nextl));
        }
    if(nextl < len)
        if(v[i] > v[nextl])
            swap(v + i, v + (next = nextl));

    return (next == 0) ? NULL: sift_min(v, len, next);
}

восстанавливает кучу. После переключения первого и последнего он меняет каждое меньшее число на дерево по одному пути. 

void reverse(int v[], int len){
    int i;
    for(i = 0; i < len/2; i++)
        swap((v + i), (v + (len - (i + 1))));
}

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

В главном блоке есть ненужная рекурсия: 

void heap_sort(int v[], int len){
    return (len > 1)?
                (heap_sort_step(v, len, 0),
                 heap_sort(v + 1, len - 1)):
            NULL;
}

заменяется на 

void heap_sort(int v[], int len){

    heapify(v, len, 0);//this is heap_sort_step with a new name

    int templen = len
    while(templen > 1){
        swap(v, v + --templen);
        sift(v, templen, 0);
    }

    reverse(v, len);
}

Окончательный код: 

void swap(int* ref1, int* ref2){
    int temp = *ref1;
    *ref1 = *ref2;
    *ref2 = temp;
}

int heapify(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;

    if(nextr < len)
        while(v[i] > heapify(v, len, nextr))
            swap(v + i, v + nextr);

    if(nextl < len)
        while(v[i] > heapify(v, len, nextl))
            swap(v + i, v + nextl);

    return v[i];
}

void sift(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    int next  = 0;

    if(nextr < len)
        if(v[i] > v[nextr]){
            if(v[nextr] < v[nextl])
                swap(v + i, v + (next = nextr));
            else
                swap(v + i, v + (next = nextl));
        }
    if(nextl < len)
        if(v[i] > v[nextl])
            swap(v + i, v + (next = nextl));

    return (next == 0) ? NULL: sift(v, len, next);
}

void reverse(int v[], int len){
    int i;
    for(i = 0; i < len/2; i++)
        swap((v + i), (v + (len - (i + 1))));
}

void heap_sort(int v[], int len){

    heapify(v, len, 0);

    int templen = len;

    while(templen > 1){
        swap(v, v + (--templen));
        sift(v, templen, 0);
    }

    reverse(v, len);
}

Долго, но все равно рекурсивно строит кучу и быстро. Можно сделать быстрее, используя maxheap, и, конечно, исключая рекурсию. Быстрый тест дает в среднем менее 0,1 секунды для тех же образцов, которые брали более минуты.

0 голосов
/ 08 июля 2019

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

  1. Упорядочить элементы для сортировки в кучу (наивно, O (n log n); вдумчиво, O (n))
  2. Какесли в куче есть как минимум два элемента, (O (n) итераций)
    1. Поменяйте элемент head с последним.(O (1))
    2. Уменьшите (логический) размер кучи на 1. (O (1))
    3. Восстановите состояние кучи.(O (log n), если все сделано правильно)

Конечно, это применимо, сортируете ли вы в порядке возрастания, используя максимальную кучу, или в порядке убывания, используяmin-heap.

Как вы пояснили в комментариях, ваш подход состоит в том, чтобы расположить массив в min-heap для получения наименьшего элемента, а затем повторить с хвостом элемента n - 1 массива. Это не куча сортировки - это разновидность сортировки выбора .При правильной реализации это стоит O (n 2 ), потому что каждый шаг построения кучи должен посещать как минимум n / 2 неконечных узлов и, следовательно, стоит O (n).

...