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

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

#Доступ ко всем полям и методам. (52141 hits)
#Поверхностное клонирование. (23250 hits)
#Летающие, крутящиеся шарики. (38524 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (51623 hits)
#Динамическое формирование выпадающего списка. (45756 hits)
#Счетчик времени с точностью до микросекунд. (118757 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (110316 hits)
#Работа с камерой. (30632 hits)
#Разбор строки. (267940 hits)
#Обработка шаблонных писем. (32480 hits)
#Вращение фигуры в плоскости. (35114 hits)
#Арктангенс. (40976 hits)
#Простая быстрая сортировка. (104456 hits)
#Замена символа строки. (435933 hits)
#Поразрядная сортировка, общий принцип. (120175 hits)
#Рисование множества Мандельброта. (38658 hits)
#Выборка конкретной записи из таблицы. (26749 hits)
#Наибольший общий делитель. (181992 hits)
#Обновление нескольких записей таблицы. (27787 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (62516 hits)


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



Оптимизация последовательного поиска

Aвтор:
Дата:
Просмотров: 41543
реализации(C#: 4шт...) +добавить

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

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

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

 псевдокод: Последовательный поиск, версия #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] искомому. Первую проверку можно исключить, добавив элемент-метку в конце массива:

 псевдокод: Последовательный поиск, версия #2  ссылка
  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 раз. Дальнейшее сокращение не ускорило работу программы.

 псевдокод: Последовательный поиск, версия #3  ссылка
  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%.

 

 

Реализации: C#(4)   +добавить реализацию

1) Последовательный поиск, версия #1, code #58[автор:this]
2) Последовательный поиск, версия #2, code #59[автор:this]
3) Последовательный поиск, версия #3, code #60[автор:this]
4) Тест производительности разных версий последовательного поиска, code #61[автор:this]



© 2006-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.016828 секунд
Количество запросов к БД: 14, gzip: off