AOP_Tom3 (1021738), страница 106

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 106)

Какие из перечисленных в табл 1 методов являются бережливыми? 5. [45[ Довольно сложно сравнивать неслучайные данные, в которых присутствует множество равных ключей. Придумайте тест для определения эффективности сортировки, который (1) был бы актуальным как сегодня, так и через 100 лет, (й) не включал бы в рассмотрение случай равномерно распределенных случайных ключей и (ш) не использовал бы входных последовательностей данных, которые изменнлнсь бы со временем.

Я посчитал Оы цель достигнутой, если бы мне удалось рассортировать и расположить в логическом порядке основную часть того огромного материала, касающегося сортировки, котооый появился зэ несколько последних лет. — Д>К. К. ХОСКЕН (З. С. НО5КЕМ) (1955) ГЛАВА б поиск Взглянем на запись..

— ЭЛ СМИТ (АС ЭМ!ТН) ~1928) Эта глава могла бы носить более претенциозное название .— "Хранение н получение информации"; с другой стороны, ее можно было бы назвать кратко н просто— "Просмотр таблиц". В ней мы займемся вопросами накопления информации в памяти компьютера и рассмотрим способы ее быстрого извлечения. Зачастую мы сталкиваемся с избыточной информацией, и лучшее, что с ней можно сделать, забыть о ней или уничтожить ее.

Однако нередки ситуации, когда крайне важно сохранить материал и организовать его таким образом, чтобы впоследствии обеспечить к нему максимально быстрый доступ. Основная часть втой главы посвящена изучению простейшей задачи: поиску информации, сохраненной с конкретным идентификатором.

Например, в численном приложении может понадобиться найти ~(х) по данному х и таблице значений Л другим примером может послужить поиск перевода на английский язык некоторого русского слова. В целом, мы предполагаем, что имеется набор из ЛГ записей и задача состоит в нахождении одной из них. Как и в случае сортировки, мы полагаем, что каждая запись включает специальное поле, именуемое ее ключом; данный термин удачен, так как, несомненно, отражает тот печальный факт, что ежедневно миллионы людей тратят время и силы на поиски собственных неизвестно куда запропастившихся ключей... В общем случае нам требуется Аг различных ключей для того, чтобы каждый из них однозначно идентифицировал связанную с ним запись. Набор всех записей именуется таблицей или файлом, причем слово "таблица" обычно используется для описания маленького файла, а слово "файл" -- для описания большой таблицы.

Большой же файл (или группу файлов) часто называют базой данных. Алгоритм поиска имеет так называемый аргуменш, К, и задача заключается в нахождении записи, для которой К служит ключом. Результатом поиска может быть одно из двух: либо поиск завершился успешно, и уникальная запись, содержащая К, найдена, либо поиск оказался неудачным, и запись с ключом К не найдена.

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

Хотя цель поиска — — нахождение информации, хранящейся в ассоциированной с К записи, алгоритмы в этой главе предназначены для поиска К. После нахождения К поиск связанной с ним информации становится тривиальной задачей, зависящей от способа хранения информации. Например, найдя К в ТАВЕЕ+1, мы обнаружим связанные с ним данные в ТАВЕЕ + 1 + 1, в ВАТА + 1 или в еще каком-то месте, которое определяется способом хранения информации. Поэтому мы считаем задачу выполненной в тот момент, когда находим К (илн убеждаемся в его отсутствии).

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

В случае, когда мы можем выбирать ключи, имеется еще один способ избежать поиска: выбрать в качестве ключа натуральные числа (1,2,...,Х); при этом запись с ключом К просто размещается в ТАВОТЕ + К. Обе эти технологии были использованы, чтобы избежать поиска в алгоритме топологической сортировки, обсуждавшемся в разделе 2.2,3. Однако поиск необходим, если объекты для топологической сортировки представлены не числовыми, а символьными значениями.

Естественно, в этом случае очень важно подобрать эффективный алгоритм поиска. Методы поиска могут быть классифицированы несколькими способами. Мы можем разделить их на внутренний и внешний поиск так же, как в главе 6 мы разделяли алгоритмы сортировки иа внутренние и внешние. Возможно деление на статические н динамические методы поиска, где термин "статический" означает, что содержимое таблицы остается неизменным и главная задача — уменьшить время поиска без учета времени, необходимого для настройки таблицы. Термин "динамический" означает, что таблица часто изменяется путем вставки (а возможно, и удаления) элементов.

Третья возможная схема классификации методов поиска— их разделение в.завясимости от того, на чем они основаны: на сравнении ключей или на некоторых числовых свойствах ключей (по аналогии с разделением на сортировку методом сравнения и сортировку методом распределения). И наконец, можно разделить методы сортировки на методы с использованием ключей действительных и преобразованных (трансформированных). Организация этой главы представляет собой комбинацию двух посчедних способов классификации. Раздел 6.1 посвящен методам последовательного поиска, т.

е. методам поиска "в лоб". В разделе 6.2 рассмотрены усовершенствования, основанные на сравнении ключей с использованием алфавитного или числового порядка для управления решениями. Раздел 6.3 посвящен числовому поиску, а в разделе 6.4 обсуждается важный класс методов с общим названием "хеширование", основанных на арифметическом преобразовании действительных ключей. В каждом из этих разделов рассматривается как внутренний, так и внешний поиск (как для статического, так и для динамического случаев).

В каждом разделе вы найдете описание достоинств и недостатков рассматриваемых алгоритмов. Поиск и сортировка зачастую тесно связаны между собой. Например, рассмотрим следующую задачу. Даныдва числовых множества, А = (ат,аз, а ) и В = (Ьы Ьг,..., Ь„). Необходимо определить, является ли множество А подмножеством множества В:А С В. Очевидными представляются такие варианты решения. 1. Сравнивать каждое а, со всеми Ь последовательно до нахождения совпадения. 2. Сначала рассортировать множества А и В, а затем сделать только один последовательный проход с проверкой по обоим файлам.

3. Внести все элементы Ь. в таблицу и вьпюлнить поиск каждого значения а,, Каждое из этих решений имеет свои достоинства для различных значений т и и. Решеняе 1 требует порядка сттп единиц времени, где ст — некоторая константа. Решение 2 требует порядка сг(тп !к пт+ и !к тт) единиц времени, где сг — некоторая (большая) константа.

При выборе подходящего метода хеширования решение 3 займет около сзпт + схп единиц времени для некоторых (еще больших) констант сз и сэ. Отсюда следует, что решение 1 подходит для очень небольших значений тп и и; при увеличении множеств лучшим становится решение 2. Затем наилучшим станет решение 3 — до тех пор, пока и пе превысит размер внутренней памяти. После этого наилучшим обычно вновь становится решение 2, пока и не вырастет до совсем уж громадных значений...

Итак, мы видим, что существуют ситуации, в которых сортировка слу'жит хорошей заменой поиску, а поиск — отличной заменой сортировке. Более сложные задачи поиска зачастую сводятся к более простым (которые мы и рассматриваем). Предположим, например, что ключи представляют собой слова, которые могут быть записаны с небольшими ошибками.

Наша задача— найти запись, невзирая на ошибки в ключах. Если мы сделаем две копии файла, в одном из которых ключи расположены в обычном лексикографическом порядке, а в другом — в обратном порядке, справа налево (как если бы их читали задом наперед), искаженный аргумент поиска будет, вероятно, совпадать до половины (яли более) своей длины с записью в одном из файлов. Методы поиска, описываемые в разделах 6.2 и 6.3, таким образом, могли бы быть приспособлены для поиска по искаженному ключу. Подобные задачи привлекли внимание в связи с вводом в действие систем резервирования билетов на самолеты и других подобных им систем, в которых велика вероятность возникновения ошибки из-за плохой слышимости или некаллиграфического почерка.

Характеристики

Список файлов книги