Поиск в списке с пропусками

Поиск в списке с пропусками

Если еще раз внимательно посмотреть на рис. 6.3, можно обратить внимание, что полученный список можно охарактеризовать как несколько объединенных односвязных и двухсвязных списков. На уровне 0 находится двухсвязный список, далее, на уровне 1 - односвязный список, который соединяет каждый второй узел, после него на уровне 2 находится еще один односвязный список, который объединяет каждый четвертый узел и, наконец, на уровне 3 односвязный список соединяет каждый восьмой узел. Таким образом, чтобы, например, найти узел с именем g, нужно перейти по указателю уровня 2 от начального узла к узлу d, затем по указателю первого уровня до узла f и, наконец, по указателю уровня 0 до узла g. Следовательно, теоретически говоря, чтобы найти седьмой узел, нужно будет перейти всего по трем указателям.

Теперь, когда мы в общих чертах рассмотрели алгоритм, давайте опишем его более подробно. Пусть у нас уже имеется список с пропусками. (Скоро мы изучим принцип создания списка с пропусками, однако часть алгоритма создания представляет собой алгоритм поиска, который мы сейчас и рассматриваем.) Алгоритм поиска работает следующим образом:

1. Установить значение переменной LevelNumber равным самому высшему уровню указателей списка с пропусками (предполагается, что уровень списка указывается при его создании и выполнении операций вставки и удаления).

2. Установить переменную BeforeNode на начальный фиктивный узел.

3. Перейти по прямому указателю уровня LevelNumber от узла BeforeNode. Назвать узел, в который мы попали, NextNode.

4. Сравнить элемент в узле NextNode с искомым. Если NextNode является искомым узлом, поиск завершается.

5. Если элемент в узле NextNode меньше искомого, то искомый узел должен находиться после узла NextNode. Установить переменную BeforeNode на узел NextNode и перейти к шагу 3.

6. Если элемент в узле NextNode больше искомого, то искомый узел, если он присутствует в списке, должен находиться между узлами BeforeNode и NextNode. Уменьшаем значение переменной LevelNumber на единицу (другими словами, уменьшаем количество пропускаемых за один шаг узлов).

7. Если значение переменной LevelNumber равно 0 или больше, перейти к шагу 3. В противном случае искомый элемент в списке не найден, и если его необходимо вставить, то его позиция должна находиться между узлами BeforeNode и NextNode.

В соответствии с этим алгоритмом, при поиске узла g на рис. 6.3 мы начинаем с уровня 3 и начального узла. Переходим по указателю уровня 3 до узла h. Сравниваем h и g. Поскольку h больше g, уменьшаем уровень на единицу и начинаем сначала. По указателю второго уровня от начального узла переходим к узлу d. d меньше, чем g, следовательно, узел d становится новым начальным узлом. Снова переходим по указателю уровня 2 до узла h. Поскольку h больше, чем g, уменьшаем уровень на единицу. Переходим от узла d по указателю уровня 1 до узла f. Он меньше искомого, поэтому делаем его новым начальным узлом. Переходим по указателю уровня 1, и мы снова попадаем в узел h, который больше искомого. Снова понижаем уровень на единицу, переходим вперед по указателю уровня 0 и находим искомый узел g.

Таким образом, при поиске было пройдено шесть ссылок и выполнено шесть сравнений. Звучит не очень впечатляюще, особенно если учитывать, что в простом двухсвязном списке нам пришлось бы перейти по семи указателям и выполнить семь сравнений. Тем не менее, на рис. 6.3 принято допущение, что указатель уровня n+1 переходит на расстояние, в два раза превышающее расстояние перехода для указателя уровня n. Но обязательно ли соблюдать это условие? Почему в два раза, а не в три или пять? В списке с пропусками, который будет создан в этой главе, указатели первого уровня будут переходить через четыре узла, указатели второго уровня - через 16 узлов (т.е. 4 * 4), указатели третьего уровня - через 64 узла (т.е. 4(^3^)) и указатели уровня n - через 4(^n^) узлов.

Подобный выбор расстояний переходов объясняется необходимостью балансировки степени возникновения переходов на большие расстояния на высоких уровнях и скорости поиска на уровне 0 при подходе к искомому узлу. Множитель 4 является хорошим компромиссом.

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

(поскольку в узле будет находиться два прямых указателя). Для уровня 2 размер узлов будет составлять пять указателей и т.д. Таким образом, на уровне n размер узлов будет равен не менее n + 3 указателям. (Если предположить, что размер указателя равен 4 байта, то мы получим узлы 12, 16, 20 и 4n + 12 байт для узлов уровней 0, 1, 2 и n соответственно.) В действительности, для организации списка с пропусками требуется увеличить полученные размеры узлов, по крайней мере, на 1 байт, поскольку в каждом узле необходимо хранить уровень, к которому принадлежит данный узел.

Как вы уже знаете, узел уровня n содержит указатель на узел, находящийся впереди него на 4" узлов. Если n равно 16, то указатель уровня n позволяет перейти вперед примерно на 4 миллиарда узлов - абсолютно недостижимое количество. Так, например, в 32-разрядной операционной системе каждый процесс имеет доступ к 4 миллиардам байт, в которых никак не могут разместиться 4 миллиарда узлов разного размера. На практике количество узлов, как правило, не будет превышать одного миллиона, поэтому указателей уровня 11 окажется вполне достаточно (т.е. общее количество уровней составит 12). На высшем уровне переход будет осуществляться на 4 миллиона узлов вперед.

На основе всего вышесказанного можно легко разработать структуру узла списка с пропусками. Это будет структура переменой длины, что несколько усложняет выделение памяти под узлы и ее освобождение. Структура узла приведена в листинге 6.14.

Листинг 6.14. Структура узла списка с пропусками

const

tdcMaxSkipLevels = 12;

type

PskNode = ^TskNode;

TskNodeArray = array [0..pred(tdcMaxSkipLevels) ] of PskNode;

TskNode = packed record

sknData : pointer;

sknLevel : longint;

sknPrev : PskNode;

sknNext : TskNodeArray;

end;

Мы не собираемся объявлять переменные типа TskNode. Фактически мы будем иметь дело исключительно с переменными типа PskNode, память под которые выделяется из кучи. Размер переменной будет вычисляться как

(3+sknLevel)*sizeof(pointer) + sizeof(longint)

Определившись со структурой узла списка с пропусками, можно перейти к рассмотрению реализации алгоритма поиска, которая приведена в листинге 6.15. Поиск представляет собой внутренний метод класса TtdSklpList. Он будет использоваться методами Add и Remove класса. И как мы сейчас увидим, еще одна его задач заключается в создании списка "предыдущих узлов" для каждого уровня.

Листинг 6.15. Поиск в списке с пропусками

function TtdSkipList.slSearchPrim(aItem : pointer;

var aBeforeNodes : TskNodeArray): boolean;

var

Level : integer;

Walker : PskNode;

Temp : PskNode;

CompareResult : integer;

begin

{заполнить весь массив BeforeNodes начальным узлом}

for Level := 0 to pred(tdcMaxSkipLevels) do

aBeforeNodes[Level] := FHead;

{инициализировать}

Walker := FHead;

Level := MaxLevel;

{начать поиск искомого узла}

while (Level >= 0) do

begin

{найти следующий узел на этом уровне}

Temp := Walker^.sknNext [Level];

{если следующий узел является конечным, считать его большим, чем искомый узел}

if (Temp = FTail) then

CompareResult := 1 {в противном случае сравнить данные следующего узла с искомыми данными}

else

CompareResult := FCompare(Temp^.sknData, aItem);

{если данные узла равны искомым данным, поиск завершен; выйти из функции}

if (CompareResult = 0) then begin

aBeforeNodes[Level] := Walker;

FCursor :=Temp;

Result := truer-Exit;

end;

{если данные следующего узла меньше, чем искомые данные, перейти в следующий узел}

if (CompareResult < 0) then begin

Walker := Temp;

end

{если данные следующего узла больше, чем искомые данные, понизить уровень}

else begin

aBeforeNodes[Level] := Walker;

dec(Level);

end;

end;

{если мы достигли этой точки, значит, искомый узел не найден}

Result := false;

end;

Реализация метода начинается с заполнения всего массива aBeforeNode начальным узлом. Затем поиск начинается с высшего уровня списка (MaxLevel). Переход по указателям высшего уровня продолжается до тех пор, пока не будет найден узел, данные которого больше искомых. Обратите внимание, что обрабатывается специальный случай для концевого узла. Предполагается, что данные конечного узла больше любых других данных в списке. К сожалению, для класса, предназначенного для любых типов данных, подобная проверка обязательна, поскольку значение конечного узла установить заранее невозможно. Если же, с другой стороны, разрабатывается список с пропусками специально для строк, значение конечного узла можно выбрать таким, чтобы оно было больше любой строки, которая будет храниться в списке.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам»

Из книги автора

Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам» Тема научного поиска не прошла мимо разработчиков персональных поисковиков. Подробному рассказу о возможностях таких поисковых систем посвящена отдельная глава нашей книги (см. главу 6).


Поиск

Из книги автора

Поиск Строка поискаЧтобы скрыть строку поиска из IE7, в разделе HKCUSoftwarePoliciesMicrosoftInternet ExplorerInfoDeliveryRestrictionsсоздайте параметр типа DWORD ·NoSearchBox· со значением 1. Перезапустите IE7, чтобы изменения вступили в силу. Кнопка Поиск (IE6)Чтобы изменить адрес поисковика, который у вас


Поиск

Из книги автора

Поиск На всех страницах сайта обязательно должно быть поле для поиска товаров. Удивительно, но в некоторых интернет-магазинах отсутствует поддержка поиска по сайту. Убедитесь, что на вашем сайте есть поиск. Более того, сделайте функцию поиска максимально заметной. Чаще


Вставка и удаление элементов в односвязном списке

Из книги автора

Вставка и удаление элементов в односвязном списке А каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями.Для односвязного списка существует только


Вставка и удаление элементов в двухсвязном списке

Из книги автора

Вставка и удаление элементов в двухсвязном списке Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре


Списки с пропусками

Из книги автора

Списки с пропусками После подробного описания нескольких генераторов случайных чисел, давайте рассмотрим структуру данных, которая для обеспечения высоких вероятностных характеристик быстродействия использует случайные числа.Код класса для списков с пропусками


Яндекс. Поиск – быстрый поиск документов

Из книги автора

Яндекс. Поиск – быстрый поиск документов Документы, как известно, имеют премерзкое свойство накапливаться. И чем больше документов, тем труднее в их залежах найти нужный. Электронные документы здесь не слишком отличаются от бумажных. Проблема места для хранения, правда,


Получение индекса компонента в списке родителя

Из книги автора

Получение индекса компонента в списке родителя Мне необходимо найти индекс компонента в родительском списке дочерних элементов управления. Я попытался модифицировать prjexp.dll, но без успеха. У кого-нибудь есть идеи?Есть такая функция. Ищет родителя заданного компонента,


Глава 12 Поиск с предпочтением: эвристический поиск

Из книги автора

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


Поиск

Из книги автора

Поиск Проблема поиска информации существовала всегда. Поиск информации на локальном компьютере напоминает работу поисковых систем Интернета. В данном случае можно также выделить два основных направления поиска: обычный и усложненный. Под обычным подразумевается поиск


Вэлкам ту Раша, Эдвард, или Почему в списке Сноудена не хватает пары имён Евгений Золотов

Из книги автора

Вэлкам ту Раша, Эдвард, или Почему в списке Сноудена не хватает пары имён Евгений Золотов Опубликовано 05 августа 2013 Лихорадка имени Эдварда Сноудена никак не желает стихать. Вот уже два месяца тема слежки за сетянами и противодействия ей остаётся


Вэлкам ту Раша, Эдвард, или Почему в списке Сноудена не хватает пары имён Евгений Золотов

Из книги автора

Вэлкам ту Раша, Эдвард, или Почему в списке Сноудена не хватает пары имён Евгений Золотов Опубликовано 05 августа 2013 Лихорадка имени Эдварда Сноудена никак не желает стихать. Вот уже два месяца тема слежки за сетянами и противодействия ей остаётся


Расстановка приоритетов в списке дел

Из книги автора

Расстановка приоритетов в списке дел Итак, вы сидите за рабочим столом, и перед вами список сегодняшних дел. Десятки пунктов. Как вы определите, с чего начать?Этот раздел посвящен расстановке приоритетов в этом списке. В разных ситуациях приходится использовать разные