Структуры данных и алгоритмы (1021739), страница 90
Текст из файла (страница 90)
Допустим, имеется файл, состоящий из одного миллиона записей, причем каждая запись занимает 100 байт. Блоки имеют длину 1000 байт, а указатель наблок занимает 4 байта. Придумайте вариант организации этого файла с помощью хеширования. Сколько блоков потребуется для хранения таблицы сегментов и самих сегментов?11.15. Придумайте вариант организации файла, описанного в упражнении 11.14, ввиде В-дерева.11.16. Напишите программы, реализующие операторы RETRIEVE, INSERT, DELETEи MODIFY дляа) хешированных файлов;б) индексированных файлов;в) файлов в виде В-дерева.11.17. Составьте программу, выполняющую поиск ft-ro наибольшего элементаа) в файле с разреженным индексом;б) в файле в виде В-дерева.*11.18.
Допустим, что на считывание блока, содержащего узел m-арного дерева поиска, уходит а + Ьт миллисекунд. Допустим также, что на обработку каждогоузла во внутренней памяти уходит с + d\og2m миллисекунд. Если на таком дереве имеется п узлов, то потребуется считать приблизительно logmn узлов, чтобы обнаружить нужную запись. Таким образом, общее время, которое потребуется, чтобы найти на дереве нужную запись, составит(logm п)(а + Ьт + с + dlqg 2 т) - (Iog2 л)((а + с + bm)/log2 m + d)миллисекунд. Сделайте обоснованные оценки значений а, Ь, с и d и постройтеграфик зависимости этой величины от т.
При каком значении т удается достичь минимума?*11.19.В*-дерево представляет собой В-дерево, в котором каждый внутренний узелзаполнен не на половину, а по крайней мере на две третьих. Придумайте схему вставки записи для В*-деревьев, которая позволяет отложить расщеплениевнутренних узлов до того момента, пока не окажутся заполненными два узла"брата". Затем два этих заполненных узла можно разделить на три, каждый изкоторых будет заполнен на две третьих. Каковы преимущества и недостаткиВ*-деревьев в сравнении с В-деревьями?336ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИ*11.20. Когда ключ записи представляет собой строку символов, можно сэкономитьместо в памяти, сохраняя в каждом внутреннем узле В-дерева в качестве разделителя ключей только префикс ключа.
Например, слова "cat" и "dog" можноразделить префиксом "d", или "do", или "dog". Придумайте такой алгоритмвставки для В-дерева, который использует как можно более короткие префиксные разделители ключей.*11.21. Допустим, что р-ю часть времени при выполнении операций с определеннымфайлом занимают вставки и удаления, а оставшуюся (1 -р)-ю часть временизанимают операции поиска информации, в которых указывается только однополе. В записях файла имеются k полей, a i-e поле в операциях поиска указывается с вероятностью qt.
Допустим, что выполнение операции поиска занимает а миллисекунд, если для указанного поля не предусмотрен вторичный индекс, и Ь миллисекунд, если для этого поля предусмотрен вторичный индекс.Допустим также, что выполнение операций вставки и удаления занимаетс + sd миллисекунд, где s — количество вторичных индексов. Определитесреднее время выполнение операций как функцию от а, Ь, с, d, p и qt и минимизируйте его.**11.22. Предположим, что используемый тип ключей допускает возможность их линейного упорядочения (например, ключи являются действительными числами)и известно вероятностное распределение в данном файле ключей с заданнымизначениями.
На основании этих сведений постройте алгоритм поиска ключа вразреженном индексе, превосходящий по эффективности двоичный поиск. Этастатистическая информация используется в одной из схем (которая называетсяинтерполяционным поиском) для прогнозирования, в каком именно местедиапазона индексных блоков Bt, ... ,В, вероятность появления ключа х является наибольшей. Докажите, что для поиска ключа в среднем было бы достаточно O(log logn) обращений к блокам.11.23. Допустим, что есть внешний файл записей, каждая из которых представляетребро графа G и стоимость этого ребра.а) Напишите программу построения остовного дерева минимальной стоимостью для графа G, полагая, что объем основной памяти достаточендля хранения всех вершин графа, но не достаточен для хранения всехего ребер.б) Какова временная сложность этой программы как функции от количествавершин и ребер?Совет.
Один из подходов к решению этой задачи заключается в сохранениилеса связных компонентов в основной памяти. Каждое ребро считывается иобрабатывается следующим образом. Если концы очередного ребра находятся вдвух разных компонентах, добавить это ребро и объединить данные компоненты. Если это ребро создает цикл в каком-то из существующих компонентов,добавить это ребро и удалить ребро с наивысшей стоимостью из соответствующего цикла (это ребро может быть текущим).
Такой подход подобен алгоритмуКрускала, но в нем не требуется сортировки ребер, что весьма существеннодля решения данной задачи.11.24. Допустим, что имеется файл, содержащий последовательность положительныхи отрицательных чисел а ь а2, ... ,а„. Напишите программу с временем выполнения О(п), которая находила бы непрерывную вложенную подпоследовательность at, at+i, ...
,а/, которая имела бы наибольшую сумму at + aj+1 + ... + atсреди всех вложенных подпоследовательностей такого рода.УПРАЖНЕНИЯ337Библиографические примечанияДополнительный материал по внешней сортировке можно найти в книге [65], поструктурам внешних данных, и их использованию в системах баз данных — там же,а также в [112] и [118]. Многофазная сортировка обсуждается в работе [102]. Схемаслияния с шестью буферами, описанная в разделе 11.2, заимствована из [39], а схемас четырьмя буферами — из [65].Выбор вторичного индекса, упрощенным вариантом которого является упражнение 11.21, обсуждается в работах [72] и [95].
Ссылка на В-деревья впервые встречается в [6]. В [20] приведен обзор различных вариантов В-деревьев, а в [45] обсуждается их практическое применение.Информацию, касающуюся упражнения 11.12 (сортировка с помощью одной идвух магнитных лент), можно найти в [35]. Тема упражнения 11.22, посвященногоинтерполяционному поиску, подробно обсуждается в [84] и [124].Весьма элегантная реализация подхода, предложенного в упражнении 11.23 длярешения задачи построения остовного дерева минимальной стоимости, принадлежитВ. А. Высоцкому (1960 г., не опубликовано).338ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИГЛАВА 12УправлениепамятьюВ этой главе обсуждаются базовые стратегии, позволяющие повторно использоватьпространство основной (оперативной) памяти или разделять его между несколькимиобъектами или процессами, потребность которых в памяти может произвольным образом увеличиваться или уменьшаться.
Мы обсудим, например, методы созданиясвязных списков свободного пространства памяти и методы "сборки мусора", при использовании которых доступная память подсчитывается лишь в том случае, когдаиспытывается нехватка памяти.12.1. Проблемы управления памятьюВ работе компьютерных систем нередко возникают ситуации, когда ограниченными ресурсами основной памяти приходится управлять, т.е. разделять между несколькими совместно использующими ее "конкурентами". Программист, которыйникогда не занимался реализацией системных программ (компиляторов, операционных систем и т.п.), может даже не подозревать о существовании подобных проблем,поскольку действия, связанные с решением этих проблем, зачастую выполняются "закулисами".
Например, программисты, создающие программы на языке Pascal, знают, что процедура new(p) создает указатель р на новый объект (динамическую переменную) соответствующего типа. Но откуда берется пространство для хранения этогообъекта? Процедура new имеет доступ к большой области памяти, называемой кучей(heap1 — динамически распределяемая область памяти), которая не используется переменными программы. Из этой области выбирается свободный блок последовательных байтов памяти, достаточный для хранения объекта того типа, на который указывает р, а в р помещается адрес первого байта этого блока. Но откуда процедуре newизвестно, какие байты памяти "свободны"? Ответ на этот вопрос читатель найдет вразделе 12.4.Еще более удивительным является то, что происходит, когда значение указателяр изменяется то ли после операций присвоения или удаления, то ли после очередногообращения к процедуре new(p).
Блок памяти, на который указывал р, может оказаться недоступным в том смысле, что до него невозможно добраться посредствомструктур данных вашей программы и, следовательно, нельзя повторно использоватьпредоставляемое им пространство. С другой стороны, прежде чем изменять р, егозначение можно было бы скопировать в какую-то другую переменную. В таком случае этот блок памяти по-прежнему оставался бы частью структур данных нашей программы. Но как узнать, что тот или иной блок в области памяти, используемой процедурой new, больше не требуется вашей программе?Подход к управлению памятью, используемый в языке Pascal, — лишь один изнескольких возможных.
В некоторых случаях (например, в Pascal) одно и то же пространство памяти совместно используют объекты разных размеров. В других случаяхвсе объекты, совместно использующие определенное пространство памяти, имеют1В русскоязычной технической литературе (особенно переводной), посвященной управлению компьютерной памятью, нет единой вполне устоявшейся терминологии, поэтому в даннойглаве мы будем приводить как термины на русском языке (наиболее точные с нашей точкизрения), так и их англоязычные эквиваленты.
— Прим. ред.- '.,• •-I. 'одинаковые размеры. Это различие, касающееся размера объектов, отражает лишьодин из подходов к классификации типов задач управления памятью, с которыминам приходится сталкиваться. Ниже приведено еще несколько примеров.1.2.3.4.340В языке программирования Lisp пространство памяти делится на ячейки (cells),которые, по существу, представляют собой записи, состоящие из двух полей, приэтом каждое поле может содержать либо атом (объект элементарного типа, например целое число), либо указатель на ячейку. Атомы и указатели имеют одинаковый размер, поэтому для всех ячеек требуется одинаковое количество байт.На основе этих ячеек можно создать любые известные структуры данных.
Например, связные списки атомов могут использовать первые поля ячеек для хранения атомов, а вторые поля — для хранения указателей на следующие ячейки всписке. Двоичные деревья также можно представлять с помощью таких ячеек:содержимое первого поля каждой ячейки должно указывать на левого сына, авторого поля — на правого сына. При выполнении Lisp-программы пространствопамяти, используемое для хранения ячеек, может оказываться — в разные моменты времени — частью нескольких различных структур; иногда это связано стем, что ячейка передается из одной структуры в другую, а иногда с тем, чтоячейка сразу же освобождается всеми структурами и может, таким образом, использоваться повторно.Файловая система, вообще говоря, делит устройства вторичной памяти(например, диски) на блоки фиксированной длины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
