<< Пред.           стр. 6 (из 19)           След. >>

Список литературы по разделу

  if q = nil then table = s
  else q.^nxt = s;
  search:= s;
  exit
  Достоинством списковой структуры является ускоренный алгоритм удаления или вставки элемента в список, причем время вставки или удаления не зависит от количества элементов, а в массиве каждая вставка или удаление требуют передвижения примерно половины элементов. Эффективность поиска в списке примерно такая же, как и в массиве.
  Эффективность последовательного поиска можно увеличить.
  Пусть имеется возможность накапливать запросы за день, а ночью их обрабатывать. Когда запросы собраны, происходит их сортировка.
 
  5.2.Индексно-последовательный поиск
 
  При таком поиске организуется две таблицы: таблица данных со своими ключами (упорядоченная по возрастанию) и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал (рис. 5.3).
  Сначала производится последовательный поиск в таблице индексов по заданному аргументу поиска. Как только мы проходим ключ, который оказался меньше заданного, то этим мы устанавливаем нижнюю границу поиска в основной таблице - low, а затем - верхнюю - hi , на которой ( kind > key ).
  Например, key = 101.
  Поиск идет не по всей таблице, а от low до hi.
 
 
 
 
  Примеры программ:
 
  Псевдокод:
  i = 1
  while (i <= m) and (kind(i) <= key) do
  i=i+1
  endwhile
  if i = 1 then low = 1
  else low = pind(i-1)
  endif
  if i = m+1 then hi = n
  else hi = pind(i)-1
  endif
  for j=low to hi
  if key = k(j) then
  search=j
  return
  endif
  next j
  search=0
  return
  Паскаль:
  i:=1;
  while (i <= m) and (kind[i] <= key) do
  i=i+1;
  if i = 1 then low:=1 else low:=pind[i-1];
  if i = m+1 then hi:=n else hi:=pind[i]-1;
  for j:=low to hi do
  if key = k[j] then
  begin
  search:=j;
  exit;
  end;
  search:=0;
  exit; 5.3. Эффективность последовательного поиска
 
  Эффективность любого поиска может оцениваться по количеству сравнений C аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска.
  Эффективность последовательного поиска в массиве:
 
  C = 1 n, C = (n + 1)/2.
 
  Эффективность последовательного поиска в списке - то же самое. Хотя по количеству сравнений поиск в связанном списке имеет ту же эффективность, что и поиск в массиве, организация данных в виде массива и списка имеет свои достоинства и недостатки. Целью поиска является выполнение следующих процедур:
  1) Найденную запись считать.
  2) При отсутствии записи произвести ее вставку в таблицу.
  3) Найденную запись удалить.
  Первая процедура (собственно поиск) занимает для них одно время. Вторая и третья процедуры для списочной структуры более эффективна (т. к. у массивов надо сдвигать элементы).
  Если k - число передвижений элементов в массиве, то k = (n + 1)/2.
 
  5.4. Эффективность индексно-последовательного поиска
 
  Ecли считать равновероятным появление всех случаев,то эффективность поиска можно рассчитать следующим образом:
  Введем обозначения: m - размер индекса; m = n / p;
  p - размер шага
 
  Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1
 
  Продифференцируем Q по p и приравняем производную нулю:
 
  dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0
  Отсюда
  p2=n ;
 
 
  Подставив ропт в выражение для Q, получим следующее количество сравнений:
 
  Q = +1
  Порядок эффективности индексно-последовательного поиска O ()
 
 5.5 Методы оптимизации поиска
 
  Всегда можно говорить о некотором значении вероятности поиска того или иного элемента в таблице. Считаем, что в таблице данный элемент существует. Тогда вся таблица поиска может быть представлена как система с дискретными состояниями, а вероятность нахождения там искомого элемента - это вероятность p(i) i - го состояния системы.
 
 
 
  Количество сравнений при поиске в таблице, представленной как дискретная система, представляет собой математическое ожидание значения дискретной случайной величины, определяемой вероятностями состояний и номерами состояний системы.
 
  Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)
 
  Желательно, чтобы p(1)p(2) p(3) …p(n).
  Это минимизирует количество сравнений, то есть увеличивает эффективность. Так как последовательный поиск начинается с первого элемента, то на это место надо поставить элемент, к которому чаще всего обращаются (с наибольшей вероятностью поиска).
  Наиболее часто используются два основных способа автономного переупорядочивания таблиц поиска. Рассмотрим их на примере односвязных списков.
 
  5.5.1 Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка
  Суть этого метода заключается в том, что элемент списка с ключом, равным заданному, становится первым элементом списка, а все остальные сдвигаются.
 
 
 
  Этот алгоритм применим как для списков, так и для массивов. Однако не рекомендуется применять его для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.
  Алгоритм переупорядочивания в начало списка:
  Псевдокод:
  q=nil
  p=table
  while (p <> nil) do
  if key = k(p) then
  if q = nil then 'перестановка не нужна'
  search = p
  return
  endif
  nxt(q) = nxt(p)
  nxt(p) = table
  table = p
  search = p
  return
  endif
  q = p
  p = nxt(p)
  endwhile
  search = nil
  return Паскаль:
  q:=nil;
  p:=table;
  while (p <> nil) do
  begin
  if key = p^.k then
  begin
  if q = nil
  then 'перестановка не нужна'
  search := p;
  exit;
  end;
  q^.nxt := p^.nxt;
  p^.nxt := table;
  table := p;
  exit;
  end;
  q := p;
  p := p^.nxt;
  end;
  search := nil;
  exit;
  5.5.2. Метод транспозиции
  В данном методе найденный элемент переставляется на один элемент к голове списка. И если к этому элементу обращаются часто, то, перемещаясь к голове списка, он скоро окажется на первом месте.
 
 
 
  р - рабочий указатель
  q - вспомогательный указатель, отстает на один шаг от р
  s - вспомогательный указатель, отстает на два шага от q
 
  Алгоритм метода транспозиции:
 
  Псевдокод:
  s=nil
  q=nil
  p=table
  while (p <> nil) do
  if key = k(p) then
  ‘ нашли, транспонируем
  if q = nil then
  ‘ переставлять не надо
  search=p
  return
  endif
  nxt(q)=nxt(p)
  nxt(p)=q
  if s = nil then
  table = p
  else nxt(s)=p
  endif
  search=p
  return
  endif
  endwhile
  search=nil
  return Паскаль:
  s:=nil;
  q:=nil;
  p:=table;
  while (p <> nil) do
  begin
  if key = p^.k then
  ‘ нашли, транспонируем
  begin
  if q = nil then
  begin
  ‘переставлять не на-
  до search:=p;
  exit;
  end;
  q^.nxt:=p^.nxt;
  p^.nxt:=q;
  if s = nil then
  table := p;
  else
  begin
  s^.nxt := p;
  end;
  search:=p;
  exit;
  end;
  end;
  search:=nil;
  exit;
  Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются только два стоящих рядом элемента).
 
  5.5.3. Дерево оптимального поиска
  Если извлекаемые элементы сформировали некоторое постоянное множество, то может быть выгодным настроить дерево бинарного поиска для большей эффективности последующего поиска.
  Рассмотрим деревья бинарного поиска, приведенные на рисунках a и b.Оба дерева содержат три элемента - к1, к2, к3, где к1<к2<к3. Поиск элемента к3 требует двух сравнений для рисунка 5.6 a), и только одного - для рисунка 5.6 б).
  Число сравнений ключей, которые необходимо сделать для извлечения некоторой записи, равно уровню этой записи в дереве бинарного поиска плюс 1.
  Предположим, что:
  p1 - вероятность того, что аргумент поиска key = к1
  р2 - вероятность того, что аргумент поиска key = к2
  р3 - вероятность того, что аргумент поиска key = к3
  q0 - вероятность того, что key < к1
  q1 - вероятность того, что к2 > key > к1
  q2 - вероятность того, что к3 > key > к2
  q3 - вероятность того, что key > к3
  C1 - число сравнений в первом дереве рисунка 5.6 a)
  C2 - число сравнений во втором дереве рисунка 5.6 б)
 
 
 
  Тогда р1+р2+р3+q0+q1+q2+q3 = 1
  Ожидаемое число сравнений в некотором поиске есть сумма произведений вероятности того, что данный аргумент имеет некоторое заданное значение, на число сравнений, необходимых для извлечения этого значения, где сумма берется по всем возможным значениям аргумента поиска. Поэтому
 
  C1 = 2р1+1р2+2р3+2q0+2q1+2q2+2q3
  C2 = 2р1+3р2+1р3+2q0+3q1+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.7 C1 = 1.9
  C2 = 2.4 C2 = 1.8
  Дерево бинарного поиска, которое минимизирует ожидаемое число сравнений некоторого заданного множества ключей и вероятностей, называется оптимальным. Хотя алгоритм создания дерева может быть очень трудоемким, дерево, которое он создает, будет работать эффективно во всех последующих поисках. К сожалению, однако, заранее вероятности аргументов поиска редко известны.
 
  5.6 Бинарный поиск (метод деления пополам)
 
  Будем предполагать, что имеем упорядоченный по возрастанию массив чисел. Основная идея - выбрать случайно некоторый элемент AM и сравнить его с аргументом поиска Х. Если AM=Х, то поиск закончен; если AM X.
  Выбор М совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача- исключить как можно больше элементов из дальнейшего поиска. Оптимальным решением будет выбор среднего элемента, т.е. середины массива.
  Рассмотрим пример, представленный на рис. 5.7. Допустим нам необходимо найти элемент с ключом 52. Первым сравниваемым элементом будет 49. Так как 49<52, то ищем следующую середину среди элементов, расположенных выше 49. Это число 86. 86>52, поэтому теперь ищем 52 среди элементов, расположенных ниже 86, но выше 49. На следующем шаге обнаруживаем, что очередное значение середины равно 52. Мы нашли элемент в массиве с заданным ключом.
 
 
 
 
 
 
 
 
  Программы на псевдокоде и Паскале:
 
  Low = 1
  hi = n
  while (low <= hi) do
  mid = (low + hi) div 2
  if key = k(mid) then
  search = mid
  return
  endif
  if key < k(mid) then
  hi = mid - 1
  else low = mid + 1
  endif
  endwhile
  search = 0
  return low := 1;
  hi := n;
  while (low <= hi) do
  begin
  mid := (low + hi) div 2;
  if key = k[mid] then
  begin
  search := mid;
  exit;
  end;
  if key < k[mid]
  then hi := mid - 1
  else low := mid + 1;
  end;
  search := 0;
  exit
  При key = 101 запись будет найдена за три сравнения (в последовательном поиске понадобилось бы семь сравнений).
  Если С - количество сравнений, а n - число элементов в таблице, то
  С = log2n.
  Например, n = 1024.
  При последовательном поиске С = 512, а при бинарном

<< Пред.           стр. 6 (из 19)           След. >>

Список литературы по разделу