Стр. 46 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
44
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
организация памяти (структура данных или алгоритм поиска), которая
потребует меньшего обращения к магнитному диску.
Предварительные рассуждения:
1. В бинарном дереве из
n
вершин продолжительность поиска или
включения-исключения пропорциональна высоте дерева, и быстродействие
О(
2
log
n
). Если бы удалось на каждом шаге сокращать размер таблицы в
k
раз,
где
k >
2 (т.е. увеличить ветвление дерева до
k
ветвей), то затраты упали бы до
О(
log
k
n
).
6
2
log 10 20
≈
;
6
100
log 10 3
≈
.
Ветвлений дерева поиска должно быть больше, чем 2.
2. Рассмотрим структуру потерь времени при обращении к магнитному
диску.
нужные
данные
α
Рис. 45. Считывание данных с магнитного диска
Процесс считывания данных разбивается на 3 этапа:
1-й – перемещение магнитной головки на нужную дорожку (разгон и
торможение магнитной головки, необходимой для перемещения на нужную
дорожку), это очень медленный процесс
t
1
;
2-й – поворот магнитного диска на некоторый угол для того, чтобы начало
считываемых данных оказалось под головкой
t
2
;
3-й – поворот диска на некоторый угол при считывании данных
t
3
.
Практически при любом объеме считываемых данных затраты времени на
эти 3 шага
3
2 1
t
t t
>> +
. Причем
t
1
и
t
2
не зависят от объема считываемых данных.
Следовательно, выгоднее считывать данные с диска не по одному элементу, а
целыми страницами, а обработку страниц проводить уже в оперативной памяти.
В задаче поиска каждая страница может содержать ключи, связанную с
ними информацию и адреса других страниц, связанных с данной страницей.
В оперативной памяти внутри страницы можно организовать,
например,бинарный поиск.
