Требуются: очень быстрые связанные списки в C

Question

Я пытаюсь реализовать односвязный список на 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))) должно обеспечить значительное увеличение скорости.

Answer 1

Да, есть ... Это называется пулом памяти.Похоже на пул потоков.В основном вы выделяете область памяти в начале программы типа Node.Указатели на эту область хранятся в массиве.В вашей функции cons все, что вы делаете, - это получаете указатели из массива.Это не улучшает общую скорость, но если вы часто выделяете память, это увеличивает скорость реакции программы за счет некоторого места для массива

Answer 2

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

Answer 3

Какая операция должна быть быстрой: вставка, поиск, все? Всегда есть компромисс. Ваше решение должно быть масштабируемым? Связанного списка нет.

Если вы хотите / должны придерживаться связанного списка, вы можете сохранить его в массиве структур, имеющих поле, указывающее индекс следующей записи в связанном списке. Вставка будет очень быстрой, без какого-либо распределения, недостатком будет то, что вам нужно знать количество элементов заранее - или перераспределять таблицу, когда она заполнится.

См. Подраздел " Связанные списки с использованием массивов узлов " на странице Википедии в связанном списке .

Answer 4

Память не касается, некоторые мысли о том, как сделать списки ссылок быстрее.

Я думаю, что в вашем коде есть некоторая путаница.По своей сути связанный список выглядит так:

typdef struct _node {
     ...
     struct _node *next;
} NODE;

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

Вставка списка должна соединять указатели.Для простого добавления узла (и игнорирования добавления полезной нагрузки) существует 1 назначение, если узел идет в начале или в конце списка, и 2, если он идет в середине.Ничего не поделаешь, чтобы обойти это.

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

Обходы можно ускорить, реализовав их в виде списка пропусков (http://en.wikipedia.org/wiki/Skip_list). Хотя необходимо соблюдать определенную осторожностьво время вставки узла для оптимизации (и вы получите больше указателей при вставке).

Answer 5

Я бы предложил вам использовать реализацию списка ядра Linux:

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

(без выделения дополнительной памяти)

Answer 6

Если вы обеспокоены фрагментацией malloc, вы можете запросить большое количество множественных узлов Node и продолжать увеличивать указатель на sizeof (Node) каждый раз, когда копируете значения узла.

Answer 7

Если единственными операциями, которые вам нужны, является нажатие, выталкивание и повторение, то вместо связанного списка вы можете поместить элементы в массив.Нажатие и выталкивание элемента - это просто изменение одного номера (индекса первого или последнего элемента).Передняя и задняя части массива могут быть циклически связаны, так что элементы могут свободно перемещаться без проблем, что массив заканчивается.

Answer 8

Проверьте скорость реализации этого односвязного списка:

http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html