КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Организация файлов в виде кучи
Эффективность организации блоков в файле
Основная операция внешней памяти – доступ к блоку, т.е. передача блока из внешней памяти в оперативную и наоборот. Важно отметить, что в большинстве современных систем передача данных, при которой осуществляется операции считывания/записи данных из/во вторичной памяти, требуется обычно столько же или более времени, чем поиск требуемых данных в блоке, который уже находится в оперативной памяти. К тому же во всех системах, кроме некоторых гипотетических или экспериментальных, данные необходимо иметь в основной памяти прежде, чем они могут быть использованы. Таким образом, когда идет речь о быстродействии различных алгоритмов доступа к данным, следует подсчитывать число блоков, которые должны быть прочитаны в основную память или записаны из нее. Это число и будет представлять оценку быстродействия алгоритма.
На скорость доступа к данным могут влиять и дополнительные факторы. Например, операционная система может буферизировать (кэшировать) блоки. Также на скорость доступа влияет, насколько далеко друг от друга расположены считываемые блоки. Однако в дальнейших расчетах не будем учитывать дополнительные факторы, принимая во внимание только количество считанных и записанных блоков. Таким образом, скорость доступа к данным будет зависеть от организации хранения блоков в файле.
Для оценки эффективности организации файла необходимо рассмотреть, как долго выполняются следующие операции: поиск, вставка, удаление и модификация.
Это наиболее тривиальный способ организации файлов. При этом записи записываются в блоки, без упорядочивания по какому либо признаку. Сами блоки выстраиваются таким же образом. То есть, записи помещаются в один блок последовательно по мере появления. Когда блок заполняется, то выделяется новый блок, указатель на него помещается в предыдущий блок и аналогичным образом производится заполнение нового блока. Графически это можно представить в виде схемы изображенной на рисунке 4.
 |
Рисунок 4 – Схема организации файла в виде кучи
|
|
Дата добавления: 2015-05-09; Просмотров: 854; Нарушение авторских прав?; Мы поможем в написании вашей работы!