CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Часики на js. (93739 hits)
#Рисование полусферы. (29210 hits)
#Вычисление значения полинома. (62355 hits)
#Сравнение алгоритмов быстрой сортировки. (74132 hits)
#Сравнение алгоритмов сортировки массива. (182688 hits)
#Рисование линии (по Брезенхэму). (34236 hits)
#Рисование окружности (по Брезенхэму). (34095 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (69938 hits)
#Курсы валют. (67694 hits)
#Простая геометрическая и текстовая анимация. (401173 hits)
#Летающие, крутящиеся шарики. (44801 hits)
#Просмотр изображения во всплывающем окне. (89522 hits)
#Работа с камерой. (36030 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (39100 hits)
#Рисование прямоугольника. (31502 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (101372 hits)
#Выборка всех записей таблицы. (33703 hits)
#Заливка замкнутой области. (62704 hits)
#Таймер. (40968 hits)
#Подсветка синтаксиса. (31655 hits)
показать все >>


Главная >> Каталог задач >> Поиск >> Последовательный >>

Последовательный поиск и его оптимизации

Aвтор:
Дата:
Просмотров: 44860
реализации(java: 1шт...) +добавить

Последовательный (или линейный) поиск - наверное одна из самых простых и наиболее использумых программистких задач, выполняющая повсеместно почти что в любой программе. Казалось бы - что вообще можно оптимизировать в таком элементарном алгоритме?
Оказывается и здесь есть достаточное поле для улучшения производительности...

По книге Джона Бентли:
"Жемчужины программирования"

"...Обратимся к последовательному поиску в таблице, которая может быть неотсортированной:

 псевдокод: Последовательный поиск в массиве, исходная версия  ссылка
  1. int ssearch1(t)
  2.   for i = 0 to n
  3.     if x[i] == t
  4.       return i
  5.   return -1;


Эта короткая программа находит элемент в массиве х за 4,06n нc в среднем (прим. редактора: при быстроте компьютеров по тем временам конечно). Поскольку в среднем приходится просматривать примерно половину элементов, на каждый из них приходится около 8,1 нc.

Цикл выглядит достаточно стройным, но жирок с него все-таки срезать можно. Во внутреннем цикле выполняется две проверки. Сначала проверяется, достиг ли индекс i конца массива, а затем выясняется, не равен ли элемент x[i] искомому. Первую проверку можно исключить, добавив элемент-метку в конце массива:

 псевдокод: Линейный поиск, оптимизированная версия, убрана 1 проверка  ссылка
  1. int ssearch2(t)
  2.   hold = x[n]
  3.   x[n] = t
  4.   for (i = 0; ;i++)
  5.     if x[i] == t
  6.       break
  7.  
  8.   x[n] = hold
  9.   if i == n
  10.     return -1
  11.   else
  12.     return i;


Время работы уменьшилось до 3,87n нc, то есть быстродействие возросло на 5%. Мы предполагаем, что массив уже выделен, поэтому имеется возможность временно затереть значение х[n]. Нужно быть аккуратным при сохранении значения х[n] и его восстановлении. В большинстве приложений этого не требуется, так что мы исключим эту операцию из следующей версии программы.

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

В итоге получаем такой последовательный поиск в массиве, оптимизированный практически до предела:

 псевдокод: Алгоритм последовательного поиска ускоренный примерно в 8 раз  ссылка
  1. int ssearch3(t)
  2.   x[n] = t
  3.   for (i = 0; ;i += 8)
  4.     if x[i] == t
  5.       break
  6.     if x[i+1] == t
  7.       i += 1
  8.       break
  9.     if x[i+2] == t
  10.       i += 2
  11.       break
  12.     if x[i+3] == t
  13.       i += 3
  14.       break
  15.     if x[i+4] == t
  16.       i += 4
  17.       break
  18.     if x[i+5] == t
  19.       i += 5
  20.       break
  21.     if x[i+6] == t
  22.       i += 6
  23.       break
  24.     if x[i+7] == t
  25.       i += 7
  26.       break
  27.  
  28.   if i == n
  29.     return -1
  30.   else
  31.     return i;


При этом время поиска сокращается до 1,07n нc, то есть наблюдается 56% ускорение. На старых компьютерах уменьшение дополнительных затрат может дать ускорение работы на 10 или 20%. На современных машинах раскрытие цикла позволяет избежать остановки конвейера, уменьшить количество ветвей и увеличить параллелизм на уровне инструкций.... "

 

При этом согласно проведенным примерным тестам производительности - оптимизация #1 быстрее базовой на процентов 10%, оптимизация #2 - процентов на 20%.

 

 

Реализации:

java(1), C#(4)   +добавить

1) Последовательный поиск, начальная версия на java, code #796[автор:this]