Методы программирования. Громов Ю.Ю - 104 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

104
И, наконец, можно разделить методы сортировки на методы с ис-
пользованием ключей действительных и преобразованных.
Поиск и сортировка зачастую тесно связаны между собой. Напри-
мер, рассмотрим следующую задачу. Даны числовые множества A =
= {a
1
, a
2
, ..., a
m
}, B = {b
1
, b
1
, ..., b
n
} и необходимо определить, является ли
множество A подмножеством множества
BAB
⊆
:
. Очевидными пред-
ставляются следующие варианты её решения:
а) сравнивать каждое a
i
∈ A со всеми b
j
∈ A последовательно до на-
хождения совпадения;
б) сначала отсортировать множества A и B, а затем сделать только
один последовательный проход по обоим файлам, сравнивая их элементы;
в) внести все элементы b
j
с арифметически преобразованными клю-
чами (хеширование) в таблицу и выполнить поиск каждого значения a
i
.
Каждое из этих решений имеет свои достоинства для различных
значений m и n. Решение (а) требует порядка c
1
mn единиц времени, где
c
1
– некоторая константа. Решение (б) требует порядка c
2
(m lgm + n lgn)
единиц времени, где c
2
– некоторая константа. При выборе подходящего
метода хеширования решение (в) займёт около c
3
m + c
4
n единиц времени
для некоторых (ещё бóльших) констант c
3
и c
4
. Отсюда следует, что ре-
шение (а) подходит для очень небольших значений m и n. При увеличе-
нии мощности множеств лучшим становится решение (б). Затем наилуч-
шим станет решение (в) – до тех пор, пока n не превысит размер внут-
ренней памяти. После этого наилучшим обычно вновь становится реше-
ние (б), пока n не вырастет до совсем уж громадных значений. Таким об-
разом, существуют ситуации, в которых сортировка служит хорошей за-
меной поиску, а поиск – отличной заменой сортировке.
Более сложные задачи поиска зачастую сводятся к простым. Пред-
положим, что ключи представляют собой слова, которые могут быть за-
писаны с небольшими ошибками и необходимо найти запись, невзирая на
ошибки в ключах. При этом можно сделать две копии файла, в одном из
которых ключи будут расположены в обычном лексикографическом по-
рядке, а в другом – в лексикографическом порядке при чтении слова за-
дом наперёд. Тогда искажённый аргумент поиска будет, вероятно, совпа-
дать до половины (или более) своей длины с ключом некоторой записи в
одном из файлов.
Подобные задачи привлекли внимание учёных в связи с вводом в
действие систем резервирования билетов на самолёты и других подобных
им систем, в которых велика вероятность возникновения ошибки в фами-
лии из-за плохой слышимости или некаллиграфического почерка. Целью
исследований был поиск метода преобразования аргумента в некий код,
который позволил бы группировать различные варианты одной фамилии.
Далее описан метод Soundex, нашедший широкое применение для коди-
рования фамилий:

Страницы