Приоритет реализации очереди в C на основе кучи заказал (изменяемого размера) массив - берите 2


Вы думаете, что ваш код идеален ... пока вы не положите его на проверку кода.

Я положил мой приоритет в очереди на проверку и получил много хороших отзывов. В том числе утечка памяти, которая была неловко.

Смотрите здесь:

Приоритет реализации очереди в C на основе кучи заказал (изменяемого размера) массив

Поэтому я добавил в предложения и вот это. Я хотел бы видеть, если я интерпретировал предложения, а также увидеть, если есть что-нибудь еще, что нуждается в исправлении.

Я понимаю, конечно, что сделать это действительно промышленных масштабах, как, например, с сортировки функции библиотеки или стандартной библиотеки C++, то изменений не требуется. Но, надеюсь, этот код по-прежнему полезны для некоторых видов применения.

Один оставшийся пункт, что я не обращался функция array_resize. Фиксации, который не является тривиальным, поэтому оставили этот вопрос сейчас. В принципе, если realloc не удается, что делать.

Вот код.

priority_queue.H - заголовочный:

/*
Heap ordered priority queue storing in a resizable array
*/

#ifndef PRIORITY_QUEUE_
#define PRIORITY_QUEUE_

struct priority_queue;
typedef struct priority_queue priority_queue_t;

/* priority_queue_init initialises the priority queue and returns a handle which 
must be passed to subsequent priority_queue_xxx functions..  Argument is the
comparison function.  This comparison function must return a negative value if
the first argument is less than the second, a positive integer value if the 
first argument is greater than the second, and zero if the arguments are equal.
The function must also not modify the objects passed to it.  The meaning of
greater or less can be reversed. */
priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2));
/* priority_queue_free frees memory used by priority queue. init in constant time */
void priority_queue_free(priority_queue_t* pq);
/* returns 1 if the queue is empty, 0 otherwise. constant time */
int priority_queue_empty(const priority_queue_t* pq);
/* insert an object into the priority queue. insert in logarithmic time */
void priority_queue_insert(priority_queue_t* pq, void* el);
/* pops the 'top' element and removes from the priority queue. pop in logarithmic time */
void* priority_queue_pop(priority_queue_t* pq);
/* returns the top element but does not remove from priority queue. top in constant time */
void* priority_queue_top(const priority_queue_t* pq);
/* returns number of elements in priority queue. constant time */
int priority_queue_size(const priority_queue_t* pq);

#endif // PRIORITY_QUEUE_

priority_queue.с - реализации:

#include "priority_queue.h"

#include <stdlib.h>

typedef int(*compare)(const void* element1, const void* element2);

struct priority_queue {
    int capacity;
    int n;
    void** array;
    compare cmp;
};

static const int initial_size = 16;

static void swap(priority_queue_t* pq, int index1, int index2) {
    // shallow copy of pointers only
    void* tmp = pq->array[index1];
    pq->array[index1] = pq->array[index2];
    pq->array[index2] = tmp;
}


static void rise(priority_queue_t* pq, int k) {
    while (k > 1 && pq->cmp(pq->array[k / 2], pq->array[k]) < 0) {
        swap(pq, k, k / 2);
        k = k / 2;
    }
}

static void fall(priority_queue_t* pq, int k) {
    while (2 * k <= pq->n) {
        int child = 2 * k;
        if (child < pq->n && pq->cmp(pq->array[child], pq->array[child + 1]) < 0) {
            child++;
        }

        if (pq->cmp(pq->array[k], pq->array[child]) < 0) {
            swap(pq, k, child);
        }
        k = child;
    }
}

static void** array_resize(void** array, int newlength) {
    /* reallocate array to new size
       this is problematic because realloc may fail and return NULL
       in which case there is a leak because array is still allocated
       but not returned so cannot be free'd */
    return realloc(array, newlength * sizeof(void*));
}

priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2)) {
    priority_queue_t* pq = malloc(sizeof(priority_queue_t));
    pq->array = NULL;
    pq->capacity = 0;
    pq->n = 0;
    pq->cmp = compare;
    return pq;
}

void priority_queue_free(priority_queue_t* pq) {
    free(pq->array);
    free(pq);
}

int priority_queue_empty(const priority_queue_t* pq) {
    return pq->n == 0;
}

void priority_queue_insert(priority_queue_t* pq, void* el) {

    if (pq->capacity == 0) {
        pq->capacity = initial_size;
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }
    else if (pq->n == pq->capacity) {
        pq->capacity *= 2;
        // we need to resize the array
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }

    // we always insert at end of array
    pq->array[++pq->n] = el;
    rise(pq, pq->n);
}

void* priority_queue_pop(priority_queue_t* pq) {

    // reduce array memory use if appropriate
    if (pq->capacity > initial_size && pq->n < pq->capacity / 4) {
        pq->capacity /= 2;
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }

    void* el = pq->array[1];
    swap(pq, 1, pq->n--);
    pq->array[pq->n + 1] = NULL;  // looks tidier when stepping through code - not really necessary
    fall(pq, 1);
    return el;
}

void* priority_queue_top(const priority_queue_t* pq) {
    return pq->array[1];
}

int priority_queue_size(const priority_queue_t* pq) {
    return pq->n;
}

пример программы драйвера:

#include "priority_queue.h"

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int weight;
    char* data;
} element;


int descending(const void* a, const void* b) {
    const element* element1 = a;
    const element* element2 = b;
    if (element1->weight < element2->weight)
        return -1;
    if (element1->weight > element2->weight)
        return 1;

    return 0;
}

typedef struct {
    int vertex;
    int weight;
} edge;

int ascending(const void* a, const void* b) {
    const edge* edge1 = a;
    const edge* edge2 = b;
    if (edge2->weight < edge1->weight)
        return -1;

    if (edge2->weight > edge1->weight)
        return 1;

    return 0;
}

int main() {
    priority_queue_t* pq = priority_queue_init(descending);
    printf("size of pq now = %d\n", priority_queue_size(pq));

    int weights[] = { 14,8,15,16,11,1,12,13,4,10,9,3,5,7,2,6,6,6 };
    int size = sizeof(weights) / sizeof(weights[0]);

    // insert each one into priority queue
    for (int i = 0; i < size; ++i) {
        element* el = malloc(sizeof(element));

        // generate string
        char buffer[20];
        sprintf(buffer, "added no: %d", i + 1);
        el->data = malloc(strlen(buffer) + 1);
        strcpy(el->data, buffer);
        el->weight = weights[i];
        priority_queue_insert(pq, el);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    element* el = malloc(sizeof(element));
    el->weight = 22;
    el->data = "hi guys";
    priority_queue_insert(pq, el);
    printf("size of pq now = %d\n", priority_queue_size(pq));

    const element* top = priority_queue_top(pq);
    printf("peek of top item: %d %s\n", top->weight, top->data);

    while (!priority_queue_empty(pq)) {
        element* top = priority_queue_pop(pq);
        printf("top is: %d %s\n", top->weight, top->data);
        free(top);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    priority_queue_free(pq);

    // try using different data/comparator
    pq = priority_queue_init(ascending);
    edge* e1 = malloc(sizeof(edge));
    e1->vertex = 0;
    e1->weight = 1;
    priority_queue_insert(pq, e1);
    edge* e2 = malloc(sizeof(edge));
    e2->vertex = 1;
    e2->weight = 3;
    priority_queue_insert(pq, e2);

    edge* e3 = malloc(sizeof(edge));
    e3->vertex = 2;
    e3->weight = 3;  // same weight
    priority_queue_insert(pq, e3);

    while (!priority_queue_empty(pq)) {
        edge* top = priority_queue_pop(pq);
        printf("top is: %d %d\n", top->weight, top->vertex);
        free(top);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    priority_queue_free(pq);
}


494
3
задан 3 февраля 2018 в 12:02 Источник Поделиться
Комментарии
1 ответ


Один оставшийся пункт, что я не обращался функция array_resize. Фиксации, который не является тривиальным, поэтому оставили этот вопрос сейчас. В принципе, если realloc не удается, что делать(?)


  1. Меня смущает, для pq->array выделенную память как пропорционально pq->capacity + 1. Переписать код так массива счетчик pq->capacity.

  2. Я бы на array_resize() что может повлиять на состояние priority_queue_t* pq положить его на ошибки/начального состояния. Пример

    // return true on problem
    static bool array_resize(priority_queue_t* pq, size_t new_count) {
    if (new_count > 0) {
    void *new_pointer = realloc(pq->array, sizeof *pq->array * new_count);
    if (new_pointer) { // Success path
    pq->array = new_pointer;
    pq->capacity = new_count;
    return false;
    }
    if (new_count <= pq->capacity) {
    return false; // failure to reduce is not really an error.
    }
    // fall though on allocation failure
    }
    pq->n = 0;
    pq->capacity = 0;
    free(pq->array);
    pq->array = NULL;
    return new_count > 0;
    }

Другие вещи


  1. Справиться с неожиданными функция использования заказа. Правда, что вышел из строя функций использования о методе init() и свободный() являются проблематичными, но то, что о priority_queue_pop() ничего нет в очереди? Код экспонаты УБ. Лучше проверить и вернуть NULL или как-то остановить/предупредить/ручка.

  2. Хорошие идеи, как показано ниже, которые полезны для отладки можно обернуть в макрос. ИМО, когда бремя это свет, просто оставьте в отладочном и рабочем коде.

    #ifndef NDEBUG
    pq->array[pq->n + 1] = NULL;
    #endif

  3. Примечание: priority_queue_pop() никогда не сжимает массив выделения до 0. Не плохая цель дизайн. Хммм.

Незначительные


  1. Хороший улучшение.

  2. Добавьте несколько пустых строк, чтобы улучшить ясность.

    /* returns 1 if the queue is empty, 0 otherwise. constant time */
    int priority_queue_empty(const priority_queue_t* pq);

    /* insert an object into the priority queue. insert in logarithmic time */
    void priority_queue_insert(priority_queue_t* pq, void* el);

    /* pops the 'top' element and removes from the priority queue. pop in logarithmic time */
    void* priority_queue_pop(priority_queue_t* pq);


  3. size_t является "просто право" тип для массива индексации и размеров. Ни слишком широким, ни слишком узким.

    struct priority_queue {
    // int capacity, n;
    size_t capacity, n;
    ...
    };

    // int priority_queue_size(const priority_queue_t* pq);
    size_t priority_queue_size(const priority_queue_t* pq);


  4. Хорошее форматирование. Но смотреть на код в вопрос. Есть горизонтальная полоса прокрутки, чтобы показать priority_queue.*? Для меня это означает, что код слишком широк. Обертывания ширина презентацию обзора. Автоматическое форматирование должно быть легко.

  5. Идиоматические сравните, что многие компиляторы распознают и выделяют эффективный код:
    (a > b) - (a < b)

    int descending(const void* a, const void* b) {
    ...
    return (element1->weight > element2->weight) -
    (element1->weight < element2->weight);
    }

Передовые идеи:


  1. Комментарии .ч не о том, что priority_queue функции будут делать, когда предметы равны. Стабильный? Недетерминированный? Если n элементов были вставлены, все тот же приоритет, это порядок, в котором они pop() определена? Классный priority_queue бы вернуть эти таким образом, чтобы предотвратить залежалый товар (тот, который сидит в течение длительного времени). Возможно, если 2 детали имеют одинаковый приоритет, в пользу одного с нижнего индекса массива?

0
ответ дан 3 февраля 2018 в 08:02 Источник Поделиться