Последовательно упорядоченные файлы

Как вы знаете, большинство картотек, как, например, телефонные справочники, упорядочены по алфавиту (Рисунок 4.3). Этот метод использует сравнение каждой новой записи с имеющимися для определения того, где ее место. Такие последовательно упорядоченные файлы (ordered sequential files) могут использовать буквы алфавита, как в нашем примере с картотекой, или числа, которые тоже имеют определенную последовательность. Обычной стратегией поиска здесь является так называемый поиск делением пополам (или дихотомия). Поиск начинается разделением всего массива записей на две половины и выборкой записи в середине. Если она оказывается той, что нужна, то процедура поиска закончена. Если искомая запись находится прежде выбранной, то мы выполняем ту же операцию с первой половиной, если после — со второй.

Рисунок 4.3. Последовательно упорядоченный файл. Иллюстрация структуры файла как упорядоченной картотеки. В данном случае сортировка производится с использованием алфавита.

Таким образом, программе не требуется просматривать большую часть файла. Среднее количество операций в этой стратегии определяется как log₂(n+l). В нашем прежнем примере время поиска сокращается до немногим более двух часов вместо прежних 28-ми.

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

Не нашли, что искали? Воспользуйтесь поиском: