Суть этого метода заключается в том, что элемент списка с ключом, равным аргументу поиска, становится первым элементом списка, исходя из предположения,что к этому элементу будут обращаться чаще всего.
Этот алгоритм применим как для списков, так и для массивов. Однако не рекомендуется применять его для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.
Алгоритм переупорядочивания в начало списка:
q= nil
p = table
while (p <> nil) do
if key = k(p) then
search = p
if q = nil
then 'перестановка не нужна'
return
endif
nxt(q) = nxt(p)
nxt(p) = table
table = p
return
endif
q = p
p = nxt(p)
endwhile
search = 0
return
Метод транспозиции
В данном методе найденный элемент переставляется на один элемент к голове списка. И если к этому элементу обращаются часто, то, перемещаясь к голове списка, он скоро окажется на первом месте.
р - рабочий указатель
q - вспомогательный указатель, отстает на один шаг от р
s - вспомогательный указатель, отстает на два шага от q
Алгоритм метода транспозиции:
s = nil
q = nil
p = table
while (p <> nil) do
if key = k ( p ) then
‘ нашли, транспонируем
if q = nil then
‘ переставлять не надо
return
endif
nxt(q) = nxt(p)
nxt(p) = q
if s = nil then
table = p
else
nxt(s) = p
search = p
endif
return
endif
s =q
q = p
p = nxt(p)
endwhile
search = nil
return
Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются только два стоящих рядом элемента).
Дерево оптимального поиска
Если извлекаемые элементы сформировали некоторое постоянное множество, то может быть выгодным настроить дерево бинарного поиска для большей эффективности последующего поиска.
Рассмотрим деревья бинарного поиска, приведенные на рисунках 5.6a и 5.6б. Оба дерева содержат три элемента - K 1, K 2, K 3, где K 1< K 2< K 3. Поиск элемента K 3 требует двух сравнений для рисунка 5.6 a), и только одного - для рисунка 5.6 б).
Число сравнений ключей, которые необходимо сделать для извлечения некоторой записи, равно уровню этой записи в дереве бинарного поиска плюс 1.
Предположим, что:
p 1 - вероятность того, что аргумент поиска key = K 1
р2 - вероятность того, что аргумент поиска key = K 2
р3 - вероятность того, что аргумент поиска key = K 3
q 0 - вероятность того, что key < K 1
q 1 - вероятность того, что K 2 > key > K 1
q 2 - вероятность того, что K 3 > key > K 2
q 3 - вероятность того, что key > K 3
C 1 - число сравнений в первом дереве рисунка 5.6 a)
C 2 - число сравнений во втором дереве рисунка 5.6 б)
Тогда p 1+ p 2+р3+q0+q1+q2+q3 = 1
Ожидаемое число сравнений в некотором поиске есть сумма произведений вероятности того, что данный аргумент имеет некоторое заданное значение, на число сравнений, необходимых для извлечения этого значения, где сумма берется по всем возможным значениям аргумента поиска. Поэтому
C 1 = 2р1+1р2+2р3+2 q 0+2 q 1+2 q 2+2 q 3
C 2 = 2р1+3р2+1р3+2q0+2q1+3q2+1q3
Это ожидаемое число сравнений может быть использовано как некоторая мера того, насколько "хорошо" конкретное дерево бинарного поиска подходит для некоторого данного множества ключей и некоторого заданного множества вероятностей. Так, для вероятностей, приведенных далее слева, дерево из a) является более эффективным, а для вероятностей, приведенных справа, дерево из б) является более эффективным:
P1 = 0.1 P1 = 0.1
P2 = 0.3 P2 = 0.1
P3 = 0.1 P3 = 0.3
q0 = 0.1 q0 = 0.1
q1 = 0.2 q1 = 0.1
q2 = 0.1 q2 = 0.1
q3 = 0.1 q3 = 0.2
Тогда
C1 = 1.6 C1 = 1.8
C 2 = 2.2 C 2 = 1.7
Дерево бинарного поиска, которое минимизирует ожидаемое число сравнений некоторого заданного множества ключей и вероятностей, называется оптимальным. Хотя алгоритм создания дерева может быть очень трудоемким, дерево, которое он создает, будет работать эффективно во всех последующих поисках. К сожалению, однако, заранее вероятности аргументов поиска редко известны.
Дата: 2019-12-10, просмотров: 428.
