Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 108

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 102 103 104 105 106 107 < 108 > 109 110 111 112 113 114 .. 161 >> Следующая

Для того чтобы продемонстрировать работу метода двусвязных списков на практике, можно попробовать использовать систему распределения памяти, определенную с помощью класса BiListMemory, для размещения в ней объектов разных классов. Например, в главе 4 обсуждались алгоритмы представления и обработки выражений, представленных в виде деревьев. В них описывались классы для представления узлов деревьев выражений— constant, variable, Binary и др. Объекты этих классов имеют различное представление и, соответственно, различную потребность в памяти, однако все они являются наследниками абстрактного класса Expression. Если переопределить операторы new и delete в классе Expression таким образом, чтобы вместо обращения к системным функциям распределения памяти они использовали бы нашу, только что описанную систему, то все объекты классов, наследующих класс Expression, будут размещаться в ней.
Будем считать, что указатель на систему распределения памяти описан в виде внешней переменной следующим образом:
extern BiListMemory * memoryManagement;
Алгоритмы распределения памяти
311
Тогда определения операторов new и delete в классе Expression могут выглядеть следующим образом (приведены только определения этих операторов):
class Expression { public :
void * operator new(size_t sz) { return memoryManagement->get(sz); } void operator delete(void * ptr) { memoryManagement->release(ptr); }
};
Приятно, что больше ничего в определениях классов, реализующих деревья выражений, менять не надо. Зато, имея свою собственную систему распределения памяти, вы можете теперь не только ускорить работу алгоритмов, которые часто создают новые узлы деревьев выражений, но также удобно и просто контролировать затраты памяти. Например, если в реализацию методов get и release вставить операторы, осуществляющие статистический учет занятой и освобождаемой памяти, то можно легко проверить, сколько всего памяти было затрачено на представление выражений, вся ли память была возвращена в систему, каков средний размер блока памяти, выделяемого по запросу из программы, и т. п.
На приложенном компакт-диске в папке "Chapter5\5.3\BiList" реализованная нами система распределения памяти используется для алгоритмов дифференцирования и упрощения выражений так, как это было описано в разд. 4.3. При этом практически никаких изменений в тексты примеров, кроме описанной выше вставки определений операторов new и delete, вносить не потребовалось. Есть только еще одно небольшое изменение, которое касается отведения памяти для глобально описанных объектов. При описании посетителей для упрощения и дифференцирования выражений использовались статические переменные класса, содержащие представления для констант 0 и 1. Вот как, например, были описаны эти константы в файле diff.cpp:
Constant * Diff::zero = new Integer(0);
Constant * Diff::one = new Integer(1);
Однако это означает, что работа операторов new для создания этих констант может начаться еще до того, как система распределения памяти вообще инициализирована. Не поможет даже описание системы здесь же на глобальном уровне:
BiListMemory * memoryManagement = new BiListMemory (20000) ;
поскольку порядок исполнения инициализаторов глобальных переменных в языке не определен, и полагаться на какой-то определенный порядок исполнения невозможно.
312
Гпава 5
Но мы можем сделать исключение для наших глобальных констант и распределить под них память с помощью системных механизмов. Это можно сделать с помощью небольшой модификации приведенных выше строк:
Constant * Diff::zero = ::new Integer(O);
Constant * Diff::one = ::new Integer(1);
Теперь наши две константы будут размещаться в памяти, отведенной встроенной системой управления памятью, а все остальные компоненты выражения — в памяти, отведенной реализованной нами системой. Ничего страшного в этом нет, и вполне может оказаться, что один из операндов выражения расположен внутри памяти, которой управляет система реализации языка C++, а другой— внутри памяти, управляемой классом BiListMemory. Надо только быть аккуратным при освобождении памяти: эффект от возврата в систему блока памяти, который ею не распределялся, может быть непредсказуем. Конечно, опять самой простой и безопасной будет политика, при которой до окончания обработки выражений возвратов памяти вообще не происходит, а вся память освобождается в конце работы с помощью вызова:
memoryManagement->clear() ;
или даже (если и сама система больше не понадобится):
delete memoryManagement;
Однако если пользоваться освобождением памяти аккуратно и не путать между собой области памяти, распределенные разными системами (т. е. не освобождать память с помощью оператора :: delete, если она была выделена оператором Expression: :new и наоборот), то наша система будет работать исправно и надежно.
Реализация системы распределения памяти с помощью организации двусвязных списков свободных блоков памяти довольно проста и естественна. Она обладает хорошими показателями внешней и внутренней фрагментации, однако скорость работы методов get и release невысока. Это происходит из-за того, что во время работы метода get требуется просматривать список свободных блоков в поисках первого подходящего блока памяти, а при работе метода release тот же список просматривается в поисках свободных блоков, примыкающих к возвращаемому в систему блоку памяти. Все следующие описываемые в этом разделе методы управления памятью используются для борьбы за повышение скорости работы. Они также имеют небольшую внешнюю фрагментацию, однако платой за эффективность становится увеличение объемов внутренней фрагментации по сравнению с описанным выше методом построения двусвязных списков свободных блоков.
Предыдущая << 1 .. 102 103 104 105 106 107 < 108 > 109 110 111 112 113 114 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.