НОУ ІНТУІТ, Лекція, Пошук
Послідовний пошук
Для послідовного пошуку таблиці ми припускаємо, що є покажчик , значення якого належить відрізку чи, можливо, . Над цим покажчиком дозволяється проводити лише такі операції; первісне привласнення йому значення 1 або (або, якщо зручніше, 0 або , збільшення та/або зменшення його на одиницю та порівняння його з 0, 1, або . За таких угод найбільш очевидний алгоритм пошуку в таблиці першого входження даного імені має вигляд алгоритму 13.1 .Тут, як і в усіх інших алгоритмах пошуку, викладених у цій лекції, ми вважаємо, що алгоритм зупиняється негайно після відшукання або встановлення, що в таблиці немає.
Алгоритм 13.1. Послідовний пошук
знайдено: вказує на не знайдено: не входить до
Розглянемо деякі аспекти ефективності послідовного пошуку, починаючи із стандартних методів програмування. У програмі, побудованій як одного циклу , як алгоритм 13.1, будь-яке значне прискорення має бути наслідком поліпшення коду в циклі. Для того щоб побачити, які операції виконуються всередині циклу, необхідно переписати алгоритм 13.1 у формі, близькій до мови машини:
За кожну ітерацію виконується до чотирьох команд: два порівняння, одна операція збільшення та одна передача управління.
Для прискорення внутрішнього циклу загальним прийомом є додавання до таблиці спеціальних рядків, які роблять необов'язковою явну перевірку того, чи вказівник меж таблиці досяг. Це можна зробити у алгоритмі 13.1. Якщо перед пошуком ми додамо шукане ім'я наприкінці таблиці, цикл завжди буде завершуватися пошуком входження ; таким чином, нам не потрібно в циклі щоразу робити перевірку. Наприкінці циклу перевірка умови n" style="display:inline; ">", що виконується лише одного разу, говорить про те, чи є знайдене входження істинним або спеціальним елементом таблиці. Це демонструється в алгоритмі 13.2.
Алгоритм 13.2. Поліпшений послідовний пошук
Поліпшення алгоритму 13.1 буде найбільш очевидним, якщо ми перепишемо алгоритм 13.2 у тих же близьких до мови машини позначення, які використовувалися раніше:
За кожної ітерації виконуються лише три дії замість чотирьох, як це було в алгоритмі 13.1. Таким чином, у більшості обчислювальних пристроїв цикл в алгоритмі 13.2 виконуватиметься набагато швидше, ніж в алгоритмі 13.1, і оскільки швидкість циклу визначає швидкість всієї програми, таке ж порівняння має місце для двох програм.
Сумно те, що фокус із додаванням до кінця таблиці перед пошуком вдається, тільки якщо ми маємо прямий безпосередній доступ до кінця таблиці. Це можливо, якщо таблиця зберігається в пам'яті з довільним доступом, але неможливо у загальному випадку, коли використовується пов'язане розміщення або пам'ять з послідовним доступом.
Алгоритм 13.3.Послідовний пошук за таблицею, що зберігається в природному порядку
Логарифмічний пошук у статичних таблицях
Ми говоримо про логарифмічний час пошуку, як тільки виникає можливість за час , не залежить від , послідовно звести завдання пошуку в таблиці, що містить імен, до завдання пошуку в таблиці, що містить не більше імен, де - константа. У цьому випадку час , який потрібний для пошуку в таблиці з іменами, задовольняє рекурентному співвідношенню
Найпоширенішими припущеннями, які дають змогу зменшити розмір таблиці від до за час, що не залежить від , є припущення про те, що простір імен лінійно впорядкований і що порівняннядвох імен (для визначення y)" style="display: inline; "> є елементарна операція, що вимагає постійної кількості часу, що не залежить від . В результаті час, необхідний для більшості логарифмічних алгоритмів пошуку, природно вимірюється числом порівнянь (з трьома результатами) пар імен. Для деяких алгоритмів, однак, більш природні порівняння з великим , але фіксованою кількістю наслідків.
У цьому розділі ми розглядаємо тільки статичні таблиці, тобто таблиці, в яких включення і виключення або не зустрічаються, або такі рідкісні, що коли вони з'являються, будується нова таблиця. Динамічні структури таблиць, що допускають логарифмічний час пошуку, як і ефективні алгоритми включення і виключення, обговорюються наприкінці цієї лекції. Для статичних таблиць потрібно обговорити лише алгоритми пошуку та побудови таблиці. Алгоритми пошуку досить прості, але з алгоритмів побудови таблиці складні. Така ситуація виникає тому, що у разі статичної таблиці розумно вважати частоти звернення відомими, і, можливо, варто витратити суттєві зусилля на побудову оптимальної таблиці – таблиці з мінімальним середнім часом пошуку (щодо даних частот обігу). Алгоритми побудови таблиць та його аналіз є найважливішими темами цього розділу.