Гради Буч - Объектно-ориентированный анализ и проектирование с примерами приложений на С++ (1158635), страница 72
Текст из файла (страница 72)
Нопроизводительность можно значительно увеличить, используя открытые хештаблицы.Абстракция открытой хеш-таблицы проста. Таблица представляетсобой массив последовательностей, которые называются клетками. Помещая втаблицу новый элемент, мы сначала генерируем хеш-код по этому элементу, азатем используем код для выбора клетки, куда будет помещен элемент.
Такимобразом, открытая хеш-таблица делит длинную последовательность нанесколько более коротких, что значительно ускоряет поиск.Соответствующую абстракцию можно определить следующимобразом:template<class Item, class Value, unsigned int Buckets,class Container> class Table { public:Table(unsigned int (*hash)(const Item&))void setHashFunction(unsigned int (*hash)(const Item&));void clear();int bind(const Item&, const Value&);int rebind(const Item&, const Value&);int unbind(const Item&);Container* bucket(unsigned int bucket);unsigned int extent() const;int isBound(const Item&) const;const Value* valueOf(const Item&) const;const Container *const bucket(unsigned int bucket)const;protected:Container rep[Buckets];};Использование класса Container в качестве аргумента шаблонапозволяет применить абстракцию хеш-таблицы вне зависимости от типаконкретной последовательности.
Рассмотрим в качестве примера (сильноупрощенное) объявление неограниченного ассоциативного массива,построенного на базе классов Table и Unbounded:template<class Item, class Value, unsigned int Buckets,class StorageManager> class UnboundedMap : publicMap<Item, Value> { public:UnboundedMap();virtual int bind(const Item&, const Value&);virtual int rebind(const Item&, const Value&);virtual int unbind(const Item&);protected:Table<Item, Value, Buckets, Unbounded<Pair<Item, Value>,StorageManager> > rep;};В данном случае мы истанцируем класс Table контейнеромunbounded.
Рис. 9-12 иллюстрирует схему взаимодействия этих классов.В качестве свидетельства общей применимости этой абстракции мыможем использовать класс Table при реализации классов множеств инаборов.Рис. 9-12. Классы поддержкиИнструментыДля нашей библиотеки основная роль шаблонов заключается впараметризации структур типами элементов, которые будут в нихсодержаться; поэтому такие структуры называют классами-контейнерами.
Но,как видно из определения класса Table, шаблоны можно использовать такжедля передачи классу некоторой информации о реализации.Еще более сложная ситуация возникает при создании инструментов,которые оперируют с другими структурами. Как уже отмечалось, алгоритмытоже можно представить в виде классов, объекты которых будут выступать вроли агентов, ответственных за выполнение алгоритма. Такой подходсоответствует идее Джекоб-сона об объекте управления, который служитсвязующим звеном, осуществляющим взаимодействие обычных объектов [16].Преимущество данного подхода состоит в возможности создания семействалгоритмов, объединенных наследованием. Это не только упрощает ихиспользование, но также позволяет объединить концептуально схожиеалгоритмы.Рассмотрим в качестве примера алгоритмы поиска образца внутрипоследовательности.
Существует целый ряд подобных алгоритмов:• ПростойПоиск образца последовательной проверкойвсей структуры. В худшем случае временной показатель сложности данногоалгоритма будет 0(рп), где р - длина образца и н- длина последовательности.• Кнут-Моррис-ПраттПоиск образца с временным показателем0(р+п). (Knuth-Morris-Pratt) Алгоритм не требует создания копий, поэтомугодится для поиска в потоках.• Бойер-МурПоиск с сублинейным временным показателем(Воуеге-Мооге)0(с(р+п)), где с меньше 1 и обратно пропорционально р.• Регулярное выражение Поиск образца, заданного регулярнымвыражением.У всех этих алгоритмов существуют по крайней мере три общиечерты: все они проводят операции над последовательностями (и значитработают с объектами, имеющими схожий протокол), требуют существованияоперации сравнения для того типа элементов, среди которых ведется поиск(стандартный оператор сравнения может оказаться недостаточным), и имеютодинаковую сигнатуру вызова (целевую строку, образец поиска и индексэлемента, с которого начнется поиск).Об операции сравнения нужно поговорить особо.
Предположим,например, что существует упорядоченный список сотрудников фирмы. Мыхотим произвести в нем поиск по определенному критерию, скажем, найтигруппы из трех записей с сотрудниками, работающими в одном и том жеотделе. Использование оператора operator==, определенного для классаPersormelRecord, не даст нужного результата, так как этот оператор, скореевсего, производит проверку в соответствии с другим критерием, например,табельным номером сотрудника. Поэтому нам придется специальноразработать для этой цели новый оператор сравнения, который запрашивал бы(вызовом соответствующего селектора) название отдела, в котором работаетсотрудник. Поскольку каждый агент, выполняющий поиск по образцу, требуетсвоей функции проверки на равенство, мы можем разработать общийпротокол введения такой функции в качестве части некоторого абстрактногобазового класса.
Рассмотрим в качестве примера следующее объявление:template<class Item, class Sequence> class PatternMatch{ public:PatternMatch();PatternMatch(int ( *isEqual)(const Item& x, const Item&y));virtual ~PatternMatch();virtual void setIsEqualFunction(int (*)(const Item& x,const Item& y));virtual intmatch(const Sequence& target, const Sequences; pattern,unsigned int start = 0) = 0;virtual intmatch(const Sequence&; target, unsigned int start = 0) =О;protected:Sequence rep;int (*isEqual)(const Item& x, const Item& y);private:void operator=(coust PattemMatcb&) {} voidoperator==(const PatternMatch&) {} void operator!=(constPatternMatch&) {}};Операции присваивания и сравнения на равенство для объектовданного класса и его подклассов невозможны, поскольку мы использовалисоответствующие идиомы.
Мы сделали это, потому что операцииприсваивания и сравнения не имеют смысла для абстракций агентов.Теперь опишем конкретный подкласс, определяющий алгоритмБойера-Мура:template<class Item, class Sequence>class BMPatternMatch ; public PatternMatch<ltem,Sequence> {public:BMPatternMatch();BMPattemMatch(int (*isEqual) (const Item& x, const Item&y));virtual ~BMPattemMatch();virtual intmatch(const Sequence& target, const Seque unsigned intstart = 0);virtual intmatch(const Sequence& target, unsigned inProtected:unsigned int length;unsigned int* skipTable;Рис.
9-13. Классы поискаvoid preprogress(const Sequence& pattern);unsigned int itemsSkip(const Sequence& pattern,constItem& item);};Открытый протокол этого класса полностью копируетсоответствующий протокол своего суперкласса. Кроме того, его описаниедополнительно включает два элемента данных и две вспомогательныефункции. Одна из особенностей данного класса состоит в создании временнойтаблицы, которая используется для пропуска длинных неподходящихпоследовательностей. Эти добавочные элементы нужны для реализацииалгоритма.На рис. 9-13 приведена иерархия классов поиска.
Иерархия подобноготипа применима для большинства инструментов библиотеки. При этомформируются сходные по структуре семейства классов, что позволяетпользователям легко в них ориентироваться и выбирать те, которыенаилучшим образом подходят для их приложений.9.4. СопровождениеОдно из наиболее интересных свойств сред разработки заключается втом, что, в случае удачной реализации, они стремятся набрать некуюкритическую массу функциональности и адаптируемости. Другими словами,если мы правильно выбрали основные абстракции и наделили библиотекурядом хорошо взаимодействующих между собой механизмов, то вскореобнаружим, что клиенты используют наш продукт для решения тех задач, окоторых разработчики среды и не подозревали.
После того, как определилисьосновные схемы использования среды, имеет смысл сделать их формальнойчастью самой библиотеки. Признаком правильности конструкции средыразработки является возможность внедрения новых моделей поведения спомощью повторного использования уже существующих свойств продукта ибез нарушения принципов его архитектуры.Одной из таких задач является проблема времени жизни объектов.Может встретиться клиент, который не хочет или не нуждается виспользовании полно масштабной объектно-ориентированной базы данных, апланирует лишь время от времени сохранять состояние таких структур, какочереди и множества, чтобы иметь возможность получить их состояние приследующем вызове из той же программы или из другого приложения.Принимая во внимание то, что подобные требования могут возникатьдовольно часто, имеет смысл дополнить нашу библиотеку простыммеханизмом сохранения объектов.Сделаем два допущения, касающихся этого механизма.
Во-первых,клиент должен обеспечить потоки, в которые объекты будут записываться исчитываться. Во-вторых, клиент обязан обеспечить объектам поведение,необходимое для направления в поток.Для создания такого механизма есть два альтернативных подхода.Можно построить класс-примесь, обеспечивающий семантику "долгожития";именно такой подход реализован во многих объектно-ориентированных базахданных. В качестве альтернативы можно создать класс, экземпляры котороговыступают в качестве агентов, ответственных за перенаправление различныхструктур в поток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
