Реалистичное использование развернутых списков пропусков

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

Во-первых, развернутый связанный список обычно использует довольно маленький размер узла. Как сказано в статье в Википедии: "достаточно большой, чтобы узел заполнил одну строку кэша или маленькое кратное». На современных процессорах Intel длина кэш-строки составляет 64 байта. Узлы списка пропуска имеют в среднем два указателя на узел, что означает в среднем 16 байтов на узел для прямых указателей. Плюс какие бы ни были данные для узла: 4 или 8 байтов для скалярного значения или 8 байтов для ссылки (здесь я предполагаю 64-битную машину).

Итак, 24 байта всего для «элемента». За исключением того, что элементы не имеют фиксированного размера. Они имеют различное количество прямых указателей. Таким образом, вам нужно либо сделать каждый элемент фиксированным размером, выделив массив для максимального количества прямых указателей для каждого элемента (что для списка пропуска с 32 уровнями потребует 256 байтов), либо использовать динамически выделяемый массив правильного размера. . Таким образом, ваш элемент становится, по сути:

struct UnrolledSkipListElement
{
    void* data; // 64-bit pointer to data item
    UnrolledSkipListElement* forward_pointers; // dynamically allocated
}

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

Если вы сможете найти способ обойти эту проблему, вы все равно не выиграете многого. Основная причина развертывания связанного списка заключается в том, что вы должны посещать каждый узел (вплоть до найденного узла), когда вы его ищете. Таким образом, любое время, которое вы можете сэкономить с каждым переходом по ссылке, составляет очень большую экономию. Но со списком пропуска вы делаете большие прыжки. Например, в идеально организованном списке пропуска вы можете пропустить половину узлов при первом переходе (если искомый узел находится во второй половине списка). Если ваши узлы в развернутом списке пропуска содержат только четыре элемента, то экономия, которую вы получите, будет только на уровнях 0, 1 и 2. На более высоких уровнях вы пропускаете более трех узлов вперед, и в результате вы понесете промах кеша.

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

Сложность связанного списка – O(N)

Сложность списка пропуска: O(Log N)

Сложность развернутого связанного списка можно рассчитать следующим образом:

O (N / (M / 2) + Log M) = O (2N/M + Log M)

Где M — количество элементов в одном узле.

Поскольку Log M не имеет значения,

Сложность развернутого связанного списка – O(N/M)

Если мы предположим объединить список Skip со связным списком Unrolled, новая сложность будет

O(Log N + "что-то из развёрнутого связанного списка, такого как N1/M")

Это означает, что «новая» сложность будет не так хороша, как может показаться на первый взгляд. Новая сложность может быть даже хуже исходной O(Log N). Реализация также будет более сложной. Так что выигрыш сомнительный и довольно сомнительный.

Кроме того, поскольку один узел будет иметь много данных, но только один «прямой» массив, «дерево» также не будет сбалансировано, и это разрушит часть O (Log N) уравнения.