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


Я практикую написание библиотеки C код и написал приоритетную очередь по некоторым графиком работы.

Я довольно новыми для написания библиотек C, поэтому был бы признателен за любые отзывы об этой реализации.

Некоторые детали для начала.

  1. Пользователь приоритетной очереди, как ожидается, определить их тип в соответствии с данными.заголовок сек. Это чтобы код был гибким и не использовать Void*. Я бы быть заинтересованы в какой-либо отзывы об этой идее.

  2. Пользователь должен предоставить функцию сортировки. Я не могу видеть любой путь вокруг этого. Я подумал о том, как сделана сортировка по умолчанию, но не мог думать ни о чем. Что может быть лучше?

Затем код.

Во-первых, данные.H-файл.

/*
    use data.h to define the data to store in the priority queue
*/

#ifndef DATA_H_
#define DATA_H_

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

#endif // DATA_H_

Приоритет заголовочный файл очереди:

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

#ifndef PRIORITY_QUEUE_
#define PRIORITY_QUEUE_

#include "data.h"

struct priority_queue_t;

struct priority_queue_t* priority_queue_init(int(*compare)(const struct element* element1, const struct element* element2));
void priority_queue_free(struct priority_queue_t* pq);
int priority_queue_empty(struct priority_queue_t* pq);
void priority_queue_insert(struct priority_queue_t* pq, struct element* el);
struct element* priority_queue_top(struct priority_queue_t* pq);

#endif // PRIORITY_QUEUE_

файл реализации - priority_queue.с

#include "priority_queue.h"

#include <stdlib.h>

typedef int(*compare)(const struct element* element1, const struct element* element2);

struct priority_queue_t {
    int capacity;
    int n;
    struct element** array;
    compare cmp;
};

static const int initial_size = 16;

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

static void rise(struct 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(struct priority_queue_t* pq, int k) {
    while (2 * k <= pq->n) {
        int j = 2 * k;
        if (j < pq->n && pq->cmp(pq->array[j], pq->array[j + 1]) < 0) {
            j++;
        }

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

static struct element** array_resize(struct element** array, int newlength) {
    // reallocate array to new size
    return realloc(array, newlength * sizeof(struct element*));
}

struct priority_queue_t* priority_queue_init(int(*compare)(const struct element* element1, const struct element* element2)) {
    struct priority_queue_t* pq = malloc(sizeof(struct priority_queue_t));
    pq->array = malloc(sizeof(struct element*) * (initial_size + 1));
    pq->capacity = initial_size;
    pq->n = 0;
    pq->cmp = compare;
    return pq;
}

void priority_queue_free(struct priority_queue_t* pq) {
    free(pq);
}

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

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

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

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

struct element* priority_queue_top(struct priority_queue_t* pq) {

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

    struct element* 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;
}

некоторые кода

#include "priority_queue.h"

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

int compare(const struct element* element1, const struct element* element2) {
    return element1->weight - element2->weight;
}

int main() {
    struct priority_queue_t* pq = priority_queue_init(compare);

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

    // insert each one into priority queue
    for (int i = 0; i < size; ++i) {
        struct element* el = malloc(sizeof(struct 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);
    }

    struct element* el = malloc(sizeof(struct element));
    el->weight = 22;
    el->data = "hi guys";
    priority_queue_insert(pq, el);

    while (!priority_queue_empty(pq)) {
        struct element* top = priority_queue_top(pq);
        printf("top is: %d %s\n", top->weight, top->data);
        free(top);
    }

    priority_queue_free(pq);
}


1246
4
задан 31 января 2018 в 08:01 Источник Поделиться
Комментарии
4 ответа


  1. "Пользователь приоритетной очереди, как ожидается, определить их тип в соответствии с данными.заголовок сек. Это чтобы код был гибким и не использовать Void*".

    Код ограничивает типы доступны ссылки на некоторые struct. Определение механизма требует data.h файл - это неудобно. Настоятельно рекомендую проще прямого подхода и пересмотра void *.


  2. "Пользователь должен предоставить функцию сортировки". Это разумно, хотя я бы назвал это сравнение функций.

  3. Если человек хочет сохранить struct element подход, по крайней мере использовать как имя .H-файл, возможно element.h.

  4. В 16 в initial_size = 16; является произвольным. ИМО, пустой "мешок" такой приоритетной очереди должны использовать минимальное пространство. Пожалуй, начнем с 0 и использовать initial_size в качестве начального распределения после некоторых что-то добавляется.

  5. Рассмотрите возможность использования const для вызовов функций, которые не изменяют состояние. Он передает коды намерениях лучше и возможно дает некоторые оптимизации.

    priority_queue_empty(const struct priority_queue_t* pq);

  6. Хорошо использовать static функции.

  7. В общем, хороший именования функций.

  8. Я бы ожидать, что функция, которая возвращает количество участников очереди.

  9. Называя, я был удивлен, что priority_queue_top() удален приоритетным элементом, а не просто сообщить об этом. Рассмотрим 2 функции, одна для отчета и другой поп его.

  10. "priority_queue.ч" следует документировать интерфейс более как это то, что пользователи видят. В частности, деталь значение возвращаемое значение int(*compare)(element1, element2) и как это влияет на очереди. Отрицательной доходности пузыриться element1 или element2. Что происходит, когда возвращаемое значение равно 0?

  11. Передовые концепции: государство, что int(*compare)() должны быть последовательным, как функцию сравнения для qsort(). Он должен сообщить об этом знак результата для одной и той же парой аргумент каждый раз это называется. qsort указывает это таким образом


Когда одни и те же объекты (..., независимо от их текущей позиции в массиве) передаются чаще, чем один раз в функцию сравнения, результаты должны быть согласованы друг с другом. То есть, для qsort они должны определить общий заказ на массива,

5
ответ дан 1 февраля 2018 в 05:02 Источник Поделиться


  • Определенная утечка памяти:

    void priority_queue_free(struct priority_queue_t* pq) {
    free(pq);
    }

    не free(pq->array).


  • Возможная утечка памяти: есть realloc в array_resizeможет потерпеть неудачу, и после

        pq->array = array_resize(....)

    массив будет потерян.


  • В pq->array[0] никогда не используется. Я не уверен, что это делает код проще. Идиоматически n следует отметить первый неиспользуемые записи.

Для решения ваших насущных проблем,


  • пользователь вынужден обернуть ее тип данных в структуре, хотя это может быть примитивный тип. Вы можете хотеть пропустить struct из вашего кода, и требует всего typedef whatever element от пользователей.

  • Если мне нужно воспользоваться этой очереди с различных типов данных в одной и той же программы, мне нужно скомпилировать его несколько раз - один раз для каждого типа - разные файлы представившись data.hи обойти несколько определений. Это является возможным, но я не хочу поддерживать систему сборки.

Я не думаю, что компаратор по умолчанию является желательным и/или возможным.

5
ответ дан 31 января 2018 в 09:01 Источник Поделиться

Других ответов сделать некоторые хорошие моменты (особенно @ВНП, который поймал две утечки памяти — это огромное дело!). Я постараюсь не слишком повторяться.


int compare(const struct element* element1, const struct element* element2) {
return element1->weight - element2->weight;
}

Вы должны знать, что этот компаратор может иметь неопределенное поведение, если element1->weight == -2 и element2->weight == INT_MAX (к примеру). Лучше идиома для сравнения "вещи" (не обязательно даже Интеграл вещи) - это

int compare(const struct element* a, const struct element* b) {
return (a->weight < b->weight) ? -1 : (a->weight > b->weight);
}


Ваш код заканчивается повторяя сайта struct много. Вы могли бы рассмотреть определение

struct priority_queue; // forward-declared
typedef struct priority_queue priority_queue_t;

struct element; // forward-declared
typedef struct element element_t;

так что вы можете использовать облегченную параметр список

void priority_queue_insert(priority_queue_t *pq, element_t *el);


Я был так же удивлен, как @chux, что priority_queue_top на самом деле достает элемент из очереди. Я бы ожидал, что поп-функцию по имени, Ну, priority_queue_pop!

Также, было бы неплохо получить документ прямо в API, является ли "поп" (в настоящее время так называемой "верхней") появляется маленький элемент или большое элемента. Вы можете сделать это одним из двух способов:

element_t *priority_queue_min(const priority_queue_t *);
element_t *priority_queue_pop_min(priority_queue_t *);

(и лично я бы сказал _least_element вместо _min для абсолютной ясности) или

element_t *minheap_top(const minheap_t *);
element_t *minheap_pop(minheap_t *);

В последнем случае мы используем о том, что "мин-кучи" есть быстрый доступ к минимальному элементу и "Макс-кучи" есть быстрый доступ к максимальному элементу. Структура данных у вас тут конкретно "мин-кучи".


Теперь, глядя на priority_queue_topя поняла, что конечно я должна была догадаться, что он изменил куче, потому что он взял параметр не константный указатель типа! Если он не собирался изменять кучи, он взял бы указатель на константный. ...Но потом я посмотрел и увидел это:

int priority_queue_empty(struct priority_queue_t* pq);

Плохо! Так empty это определенно не изменяя операции, мы должны написать вместо

int priority_queue_empty(const priority_queue_t *pq);
// ^^^^^

Или, если вы знаете, что struct priority_queue очень маленький (скажем, 16 байт или меньше), то вы можете рассмотреть возможность получения умничать и писать

int priority_queue_empty(priority_queue_t pq);

Это делает поверхностное копирование кучи и передает его в по значению; использовать последовательно, это может совершенно обеспечить, что никаких странных мутаций происходит, и даже (теоретически) позволить компилятору оптимизировать больше. Но это определенно "для продвинутых пользователей" и, возможно, "не очень хорошая идея в любом случае." ;)


Последнее, что я хочу поговорить о "генерики" аспект. Прямо сейчас у вас есть как минимум три вещи, которые пользователь может настроить, и вы обрабатываете каждое из них совершенно по-разному:

(А) данные, которые принадлежат "элемент". Настраивается ровно один раз за программу, путем определения struct element.

(Б) "меньше" основных элементов. Настраиваемый в кучи, путем передачи в компаратор (как указатель функции) в куче конструктора priority_queue_init.

(С) "обмен" и "popping" поведение элемента. Не настраиваемый; вместо этого, мы считаем, свопа и поп-указатели на элементы.

(Д) источника динамического выделения памяти. Не настраиваемый; мы используем malloc.

Если бы я писал этот код, я попытаюсь имитировать библиотеку libc функции qsort как можно больше. В частности, я хотел бы дать компаратора эту подпись:

typedef int (*priority_queue_comparator_t)(const void *, const void *);

Сделано правильно, это может обеспечить priority_queue, qsortи bsearch все играют друг с другом естественным образом. (Вы могли бы даже смотреть на то, как в C++ в STL определяет push_heap и pop_heap для работы на произвольные массивы.)

Поэтому мы могли есть API что-то вроде этого:

typedef int (*comparator_t)(const void *, const void *);
typedef int (*comparator_r_t)(void *cookie, const void *, const void *);
typedef void (*swapper_t)(void *, void *);
typedef void (*swapper_r_t)(void *cookie, void *, void *);

void push_heap_r(void *base, size_t nel, size_t width,
void *cookie, comparator_r_t cmp, swapper_r_t swap)
{
char *a = base;
int k = nel - 1;
while (k > 1 && cmp(cookie, a + width * (k / 2), a + width * k) < 0) {
swap(cookie, a + width * (k / 2), a + width * k);
k /= 2;
}
}

typedef struct minheap {
int capacity;
int n;
void **array;
comparator_t cmp;
} minheap_t;

static int pq_cmp(void *cookie, const void *a, const void *b) {
minheap_t *pq = cookie;
return pq->cmp(*(void **)a, *(void **)b);
}

static void pq_swap(void *, void *a, void *b) {
void *tmp = *(void**)a;
*(void**)a = *(void**)b;
*(void**)b = tmp;
}

void minheap_insert(minheap_t *pq, void *el)
{
if (pq->n == pq->capacity) {
pq->capacity *= 2;
// we need to resize the array
pq->array = array_resize(pq->array, pq->capacity);
}

// we always insert at end of array
pq->array[++pq->n] = el;
push_heap_r(pq->array, pq->n, sizeof(void*), pq, pq_cmp, pq_swap);
}

В "куки" параметр может использоваться для передачи данных от абонента, через универсальный алгоритм push_heap_r, в функцию сравнения. В данном случае мы используем файлы cookie, чтобы пройти оригинальный указатель на функцию pq->cmp через которые будут использоваться pq_cmp.

Но пользователь может просто использовать push_heap_r по их данным массивом напрямую, без косвенности через void*С.

static int generic_memcmp(void *cookie, const void *a, const void *b) {
return memcmp(a, b, *(size_t*)cookie);
}
static void generic_swap(void *cookie, void *a, void *b) {
size_t n = *(size_t*)cookie;
char buffer[n]; // VLA alert!
memcpy(buffer, a, n);
memcpy(a, b, n);
memcpy(b, buffer, n);
}

void test() {
struct foo arr[100] = ...;
size_t sz = sizeof (struct foo);
// Build a heap.
for (int i=1; i <= 100; ++i) {
push_heap_r(arr, i, sz, &sz, generic_memcmp, generic_swap);
}
// Now all 100 `foo`s in the array have been arranged heapwise,
// according to the comparator defined by memcmp.
}

Сейчас, это, пожалуй, немного сумасшедшие и ушел в направлении, где вам, возможно, не нужно столько генерики. Но это направление, я думаю о поездке. Это довольно неузнаваемым по сравнению с нашей начальной точке "требуют от пользователя определить struct element" и все же использование его может быть даже проще. Не более mallocнет больше elementбольше никаких массивы указателей... просто самой сырой из того, что можно было бы назвать "кучи". А потом мы построили Танос передоза minheap_t на вершине, что.

В любом случае, это пища для размышлений, даже если YAGNI на практике. :)

4
ответ дан 1 февраля 2018 в 06:02 Источник Поделиться

Одна ошибка

Когда вы измените размер массива, нужно сделать новый размер массива capacity + 1 и не только capacity, потому что Ваш массив на основе 1. Вы сделали это правильно в функции init, но не в двух местах, где вы измените размер массива.

Лучше имена локальных переменных

Вместо j и kбыло бы полезно иметь такие имена, как parent и child. Я должен был продолжать поиск обратно в код, чтобы выяснить, какие переменные держал какой индекс.

Верхняя функция не проверяет крайний случай

Если вы называете top функция на пустую приоритетную очередь, это приведет к n идти негатив, который в итоге может привести к сегфолт позже.

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