Требуемый: очень Быстрые связанные списки в C
Я пытаюсь реализовать отдельно связанный список в C. Общая реализация, что Вы видите плавание вокруг Интернета, является чем-то как
typedef struct {
int head;
Node *tail;
} Node;
с методами как
Node cons(int head, Node tail) {
Node y;
y.head = head;
y.tail = malloc(sizeof(Node));
*y.tail = tail;
}
Производительность очень важна. Там какой-либо путь состоит в том, чтобы реализовать связанный список в C, который будет быстрее, чем это? Например, избавление от выделения памяти (y.tail = malloc(sizeof(Node))) должен обеспечить значительное увеличение скорости.
8 ответов
Да есть.... Это называется пулом памяти. Аналогично пулу потоков. В основном вы выделяете область памяти в начале программы типа Node. Указатели на эту область хранятся в массиве. В вашей функции cons все, что вы делаете, это получаете указатели из массива. Это не улучшает общую скорость, но если вы часто выделяете память, это увеличит скорость работы программы за счет некоторого пространства для массива
.Какая операция должна выполняться быстро: вставка, извлечение, все? Всегда есть компромисс. Ваше решение должно быть масштабируемым? Связанного списка нет.
Если вы хотите / должны придерживаться связанного списка, вы можете сохранить его в массиве структур, имеющих поле, указывающее индекс следующей записи в связанном списке. Вставка будет очень быстрой, без какого-либо выделения, недостатком является то, что вам нужно заранее знать количество элементов - или перераспределить таблицу, когда она заполнится.
См. Подраздел « Связанные списки с использованием массивов узлов » на странице Википедии о связанных списках .
Помимо проблем с памятью, несколько мыслей о том, как сделать списки одиночных ссылок быстрее.
Я думаю, что в вашем коде есть небольшая путаница. По сути, связанный список выглядит следующим образом:
typdef struct _node {
...
struct _node *next;
} NODE;
В большинстве реализаций есть void * , на который можно повесить полезную нагрузку. На данный момент это не особенно важно.
Вставки списка должны соединять указатели. Для простого добавления узла (и игнорирования добавления полезной нагрузки) существует 1 назначение, если узел идет в начале или конце списка, и 2, если он идет в середине. Мало что можно сделать, чтобы обойти это.
Иногда в простых списках используются только узловые структуры, поэтому вставка хвоста требует обхода. Это дорого. Наличие специальной структуры головы со знанием первого и последнего узла устраняет эту стоимость.
Обход можно ускорить, реализовав это как список пропуска ( http://en.wikipedia.org/wiki/Skip_list ). Хотя при вставке узла необходимо соблюдать некоторую осторожность для оптимизации (и при вставке вы получаете больше назначений указателей).
Я бы предложил вам использовать реализацию списка ядра linux:
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h
(без дополнительного выделения памяти)
Если вас беспокоит фрагментация malloc, вы можете запросить большое количество узлов размером, кратное размеру, и продолжать увеличивать указатель на sizeof (узел) каждый раз, когда вы копируете значения узла.
Также проверьте скорость реализации этого односвязного списка:
http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps /linked_list.html
Если единственные операции, которые вам нужны, это push, popping и итерация, то вместо связного списка вы можете поместить элементы в массив. Выталкивание и выталкивание элемента - это просто изменение одного числа (индекса первого или последнего элемента). Передняя и задняя части массива могут быть циклически связаны, поэтому элементы можно свободно проталкивать без проблемы, что массив закончится.
Очень быстрое добавление в связный список? веревка (не ограниченная строками с небольшими модификациями) позволит вам пакетно выделять память (улучшая производительность), не штрафуя за добавление в конец списка.