Применение специализированных строковой и контейнерной бибилиотек в разработке  элементов графического пользовательсклшл интерфейса системы динамического отображения векторной графики

Орехов Михаил Юрьевич

Применение специализированных строковой и контейнерной бибилиотек в разработке элементов графического пользовательсклшл интерфейса системы динамического отображения векторной графики

В работе рассматриваются вопросы использования специализированных инструментов создания функциональной части системы визуализации расчета моделирующих задач в разработке элементов ее графического пользовательского интерфейса на примере конкретной панели. Задача поддержки моделирования сложного технологического объекта с большим числом единиц оборудования и органов управления в процессе его проектирования требует гибкой структуры для графического представления имитируемых подобъектов с неустановленным типом и набором атрибутов, обеспечивающей быстрый поиск в длинном перечне моделируемых параметров. Это требование определяет специализацию строковой и контейнерных библиотек, употребляемых в реализации ассоциативного контейнера элементов сменяемого типа со строковым индексом и малым временем поиска заданного ключа. Выбор специализированных библиотек для манипулирования данными в обработчиках событий панели обусловлен их высокой надежностью и быстродействием, а также наличием встроенных средств сортировки и фильтрации. В исследовании сравниваются реализации алгоритмов ключевых обработчиков событий панели, выполненных с помощью инструментария специализированных библиотек и библиотек STL и Qt. Приведенные фрагменты кода и результаты тестов подтверждают повышение надежности функционирования элемента пользовательского интерфейса, а также частичное увеличение его производительности вследствие применения специализированных средств.

Общественные науки в целом

Диссертации

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36915f1be77c40d592a0

UUID: 6c185783-a503-433e-acee-751f44cbac57

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 4

Орехов Михаил Юрьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 2191203 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ Орехов Михаил Юрьевич Выпускная квалификационная работа аспиранта Применение специализированных строковой и контейнерной библиотек в разработке элементов графического пользовательского интерфейса системы динамического отображения векторной графики 05.13.01 – системный анализ, управление и обработка информации Научный руководитель: доктор физико-математических наук, профессор Матросов Александр Васильевич Заведующий кафедрой информационных систем: доктор физико-математических наук, профессор Олемской Игорь Владимирович Рецензент: кандидат технических наук, доцент Власенко Сергей Владимирович Санкт-Петербург 2016

2 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ............................................................................................................4 ПОСТАНОВКА ЗАДАЧИ..................................................................................... 8 1. Требования к проектированию элемента пользовательского графического интерфейса........................................................................................... 8 2. Средства проектирования элемента пользовательского графического интерфейса................................................................................................................... 9 ОБЗОР ЛИТЕРАТУРЫ........................................................................................ 13 ГЛАВА 1. РЕАЛИЗАЦИЯ ОБРАБОТЧИКОВ ВНЕШНИХ СОБЫТИЙ СРЕДСТВАМИ БИБЛИОТЕК STL И QT................................................................... 15 1. Обработка изменения состава объектов схемы....................................15 1.1. Обоснование необходимости введения таблицы ObjectTab...........15 1.2. Описание алгоритма обработки........................................................16 2. Обработка изменения атрибутов объекта схемы..................................19 2.1. Обоснование выбора структуры данных таблицы ViewOrderTab. 20 2.2. Модификация кода, обусловленная введением таблицы ViewOrderTab......................................................................................................... 22 2.3. Описание алгоритма обработки........................................................25 ГЛАВА 2. РЕАЛИЗАЦИЯ ОБРАБОТЧИКОВ ВНЕШНИХ СОБЫТИЙ СРЕДСТВАМИ СПЕЦИАЛИЗИРОВАННЫХ БИБЛИОТЕК................................... 27 1. 2. Пример применения специализированной строковой библиотеки....27 Обработка изменения состава объектов схемы....................................29 2.1. М о д и ф и к а ц и я к о д а , о б у с л о в л е н н а я п р и м е н е н и е м специализированных библиотек.......................................................................... 29 2.2. Описание алгоритма обработки........................................................32 3. Обработка изменения атрибутов объекта схемы..................................36

3 3.1. Описание алгоритма обработки........................................................36 ВЫВОДЫ............................................................................................................. 39 ЗАКЛЮЧЕНИЕ................................................................................................... 43 Список литературы..............................................................................................44 ВВЕДЕНИЕ Данная работа посвящена вопросам применения средств, использованных в разработке функциональной части системы динамического отображения векторной графики, в проектировании элементов ее пользовательского графического интерфейса. Редактор/клиент динамического отображения векторной графики (рис. 1) является компонентом среды автоматизации создания моделирующих программных комплексов, предназначенных для проектирования сложных технологических объектов [1, 2]. Задача разработки моделирующих и тренажерных комплексов в процессе проектирования объекта моделирования

4 накладывает ряд специфических требований на инструментальные средства ее решения. Основными среди них являются поддержка количественных характеристик моделей имитируемого объекта с числом единиц оборудования и органов управления от нескольких сотен до десятков тысяч, а также учет неопределенности состава параметров и типов моделируемых подобъектов [3, 4]. Для выполнения первого условия графическая система должна поддерживать редактирование насыщенных схем и поиск в больших пространствах имен моделируемых параметров. Соответствие второму требованию предполагает наличие возможности композиции примитивных графических объектов для образования составного объекта пользовательского типа. При этом перечень атрибутов объекта нового типа и набор управляющих его отображением параметров, будучи сформированными пользователем при создании, могут быть впоследствии изменены. Таким образом, функциональная часть системы отображения, выполняющая обмен управляющими воздействиями и реализующая устройство и взаимодействие графических объектов, нуждается в структуре, обеспечивающей гибкость их представления, а именно ассоциативном контейнере элементов сменяемого типа.

5 Рис. 1. Система динамического отображения в режиме «Редактор» К системе отображения предъявляются требования надежности и быстродействия – управление системами моделируемого объекта и наблюдение его параметров должны осуществляться интерактивно [1], т. е. с частотой обновления кадра не менее 5 FPS. Эти требования определяют специализацию средств ее разработки. Так, быстродействие использования гибких структур становится критически зависимым от времени поиска заданного ключа в контейнере, а длительность их формирования – от скорости разбора текстовых определений графических объектов – фрагментов векторных схем открытого текстового формата. Помимо этого необходима гарантия защиты от ошибок итерирования и индексирования элементов контейнера, попыток многократного освобождения и утечек памяти. Соблюдение этих условий требует создания строковой и контейнерных библиотек, основные принципы специализации которых вкратце обозначены ниже.

6 Строковая библиотека использует подстроку на основе пары «указатель на позицию – число символов» как универсальный аргумент собственных функций. Это позволяет уменьшить количество обращений к динамической памяти для размещения разделяемых буферов строковых объектов, сокращая, тем самым, длительность преобразования строковых типов при передаче аргументов и формировании возвращаемых значений [5, 6]. В результате продолжительность операций копирования и сравнения строк приближается к времени выполнения соответствующих низкоуровневых функций стандартной библиотеки. Контейнерный класс представляет собой комбинацию двусвязного спискавладельца данных и набора индексных таблиц, минимизирующих алгоритмические издержки поиска заданного ключа [7, 8]. Модификации состава элементов списка и таблиц согласовываются на уровне их функций. Концепция владения запрещает уничтожение элементов контейнера до его собственной деструкции или явного вызова метода извлечения или удаления. Эти меры предотвращают возникновение ошибок индексирования, а последняя обеспечивает защиту от утечек памяти и попыток ее многократного освобождения. Создание неконстантного итератора сопровождается его регистрацией во внутреннем списке, что позволяет корректировать его позицию при изменении численности элементов контейнера и, тем самым, предупреждать ошибки итерирования. Предпочтение сплошного упорядоченного массива указателей на элементы контейнера в качестве индексной таблицы делает возможным увеличение скорости поиска в сравнении с альтернативными многосвязными структурами за счет высокой эффективности программноаппаратного кэширования. Теперь после краткого описания назначения системы динамического отображения и специфики инструментов ее разработки перейдем к содержанию настоящей работы. В данном исследовании на конкретном примере обосновывается применение библиотек не только как средства создания функциональной части системы визуализации расчета, но и как инструмента проектирования и повышения производительности одного из элементов ее пользовательского графического интерфейса – панели «Список объектов схемы»

7 (рис. 2). В главах 1 и 2 рассмотрена реализация алгоритмов обработки панелью ряда внешних событий. Глава 1 описывает использование инструментария популярных библиотек STL и Qt для оптимизации алгоритмов, отмечая издержки их применения. В главе 2 приведен код тех же обработчиков, написанный в той же последовательности рассуждений, но с помощью средств специализированных библиотек. В результате смены инструмента реализации алгоритмов были повышены надежность и быстродействие функционирования панели, что подтверждают сравнительные оценки применения средств обеих групп, представленные в разделе «Выводы» в виде графиков и численных соотношений. Рис. 2. Панель «Список объектов схемы» с панелью «Поиск и замена»

8 ПОСТАНОВКА ЗАДАЧИ 1. Требования к проектированию элемента пользовательского графического интерфейса Задача настоящей работы заключается в обеспечении проектирования элементов пользовательского графического интерфейса на уровне инструментария разработки, т. е. в определении инструментальных средств, позволяющих реализовать необходимые функциональные возможности и наиболее полно удовлетворить предъявленным требованиям. Панель «Список объектов схемы» (см. рис. 2) должна поддерживать следующие функциональные возможности:  отображение списка объектов схемы с минимальным влиянием на частоту обновления кадра в табличном виде, где строка соответствует объекту, а поле содержит значение атрибута, имя которого выведено в заголовке столбца. Число столбцов и имена их заголовков устанавливаются пользователем. При этом список объектов схемы и перечень отображаемых элементов должны быть согласованы: если режимы сортировки и фильтрации не активированы, численность элементов и порядок следования должны совпадать, значения атрибутов – быть актуальными;  выделение объектов схемы посредством выбора элементов панели;  симметричная обработка выделения объектов на схеме подсвечиванием ассоциированных с ними элементов панели;  определение принципов формирования перечня отображаемых элементов путем задания условий фильтрации, ключа и направления сортировки;  поддержка средств контекстного поиска и замены указанной подстроки в полях элементов. Перечислим требования к средствам проектирования панели «Список объектов схемы», степень соответствия которым позволяет оценить эффективность реализации перечисленных функциональных возможностей:

9  быстродействие, гарантирующее малое время обработки таких внешних и внутренних событий как изменение набора объектов схемы, правка значений атрибутов графических объектов, смена выделения объектов схемы и элементов панели, вход и выход из режимов сортировки и фильтрации и т. д.;  надежность в смысле наличия мер защиты от ошибок обработки данных, поддерживаемых на уровне инструментального средства;  малые издержки сопровождения созданного приложения: модификация средств или реализованных с их помощью алгоритмов приводит к минимальной редакции кода, а высокая надежность уменьшает стоимость отладки, поиска и исправления ошибок. В каче стве примера зависимо сти эффективно сти ре а лизации функциональных возможностей от выбора инструментов разработки рассмотрим обработку таких событий, как изменение состава объектов схемы и модификация графических атрибутов отдельного объекта. Критерием выделения именно этих обработчиков являются высокие вычислительные затраты, а также важность с точки зрения реализации функциональных возможностей. 2. Средства проектирования элемента пользовательского графического интерфейса Разделим инструменты разработки панели «Список объектов схемы» на средства отображения данных на экране и средства манипулирования данными. К первой группе средств относятся классы отображения, а также вспомогательные виджеты: триггеры смены режимов сортировки и фильтрации, кнопки-указатели направления сортировки, таблица ввода условий фильтрации, панель контекстного поиска (см. рис. 2) и др. Основным виджетом панели служит экземпляр типа ObjectsListTree, являющегося потомком класса отображения QTreeWidget – компонента архитектуры «модель-представление» [9, с. 241; 10, с. 88], предназначенного для вывода элементов типа QTreeWidgetItem на экран в древовидной структуре. Перечислим основные члены классов ObjectsListTree и его элемента ObjectsListTreeItem. Обработка упомянутых в п. 1 внешних

10 событий производится методами ObjectsListTree, сосредоточенными в разделе так называемых слотов [9, с. 19]: class ObjectsListTree : public QTreeWidget { ... // Обновить выделение элементов. void reloadItemsSelection(); public: // Элемент верхнего уровня по заданному индексу. ObjectsListTreeItem* topLevelItem(int it) const { return (ObjectsListTreeItem*)QTreeWidget::topLevelItem(it); } // Перечень заголовков столбцов. const QList<SString>* fieldNames() const; // Направления сортировки в столбцах. const QList<Qt::SortOrder>* sortOrders() const; // Режим «Сортировка включена» . bool indexedView() const; ... public slots: // Обработчики внешних событий. // Изменение состава объектов схемы. void objectsListChange(Scheme *scheme); // Изменение атрибутов объекта схемы. void objectPropertiesChange(DataItem* object); // Изменение выделения объекта схемы. void objectSelectionChange(DataItem *object); ... // Изменение режима сортировки. void sortingOnChange(int sortingOn); }; class ObjectsListTreeItem : public QTreeWidgetItem { public: ObjectsListTreeItem(DataItem* object, const QList<SString>* fieldNames) : _obj(object), _fieldNames(fieldNames) {...} DataItem* object() const { return _obj; } int reloadFromObject(); void reloadSelectionFromObject(); ... private: DataItem* _obj; // Контейнер атрибутов объекта схемы. const QList<SString>* _fieldNames; QList<SString> _cachedValues; }; Первым аргументом создания экземпляра ObjectsListTreeItem является ассоциативный контейнер атрибутов графического объекта схемы. Этот контейнер гибкой структуры [7, 8] предоставляет значения атрибутов по их именам. В качестве имен используются заголовки столбцов ObjectsListTree, перечень

11 которых также указывается в конструкторе. В методе reloadFromObject() элемент дерева сравнивает значения атрибутов со значениями кэша _cachedValues и, обнаружив несовпадение, обновляет собственные текстовые метки с возвратом ненулевого значения. Обратим внимание на то, что в роли типа кэш-переменных набора _cachedValues употребляется строковый класс специализированной строковой библиотеки SString (см. п. 1 главы 2). Член reloadSelectionFromObject() согласует выделение элемента со статусом объекта на схеме. Во вторую группу средств разработки панели «Список объектов схемы» входят инструменты реализации обработчиков внешних и внутренних событий, предполагающих выполнение операций редактирования, упорядочивания и фильтрации набора данных, а также поиска элемента набора по заданному ключу. Эти инструменты, в свою очередь, следует разделить на две подгруппы: первую составляют ряд классов строковых и контейнерных систем популярных библиотек STL [11, 12] и Qt [13, 14], а также доступные методы непосредственного оперирования данными на внешнем уровне иерархии «модель-представление» Qt: сортировка набора данных целиком и перестановка его отдельных элементов, выполняемые с помощью методов виджета отображения. Вторую подгруппу образуют средства специализированных строковой [5, 6] и контейнерной библиотек [7, 8]. Сравнительный анализ применения инструментов обеих подгрупп на примере реализации двух основных обработчиков модификаций графической схемы представлен в главах 1 и 2.

12 ОБЗОР ЛИТЕРАТУРЫ Контекст применения системы динамического отображения векторной графики обозначен в [1, 2]. Источник [1] определяет цель, задачи и структуру программно-технического комплекса «Виртуальный энергоблок АЭС с ВВЭР», предназначенного для верификации проекта энергоблока АЭС на моделях и экспериментальных данных. Решение каждой из задач требовало оснащения комплекса адекватным программным средством. Так, проверка функций оператора на виртуальном блочном пульте управления (БПУ) выявила необходимость разработки системы визуализации видеокадров и мозаичных панелей БПУ. Более подробно условия задачи визуализации описаны в [3, 4]. В источниках [5, 6] и [7, 8] соответственно перечислены принципы специализации строковой и контейнерной библиотек, определяющие требования к их проектированию как инструментальных средств разработки системы визуализации. Изложены концепции:  использования подстроки в роли универсального аргумента функций строковой библиотеки;  владения контейнером собственными элементами;  выбора сплошного упорядоченного массива с функцией бинарного поиска в качестве структуры данных для индексной таблицы контейнера. Следование этим ключевым принципам формирует иерархии программных классов библиотек, позволяет повысить надежность, быстродействие и удобство их применения. Приведены результаты тестов, оценивающих длительность выполнения таких характерных операций, как сравнение строк, вставка в

13 контейнер и поиск его элемента по заданному ключу для классов разработанных библиотек и их аналогов из библиотек STL и Qt. Исчерпывающий обзор программных классов библиотеки Qt с указанием их назначения, перечислением открытых методов и некоторых нюансов реализации приведен в [13, 14]. Многочисленные примеры использования средств Qt содержатся в [9, 10]. Разъяснение концепции неявного совместного использования данных (implicit data sharing), а также иллюстрированное описание архитектуры «модель-представление» (model/view architecture) могут быть найдено как в [9], так и в [13, 14]. Перечень средств, методов и алгоритмов библиотеки STL представлен в руководстве пользователя [11, 12]. Специфика упоминаемых в настоящей работе ассоциативных структур данных – хеш-таблиц, списков с пропусками и красно-черных деревьев – описана в [15-17]. Раскрыты понятия коллизий вычисления хеш-индекса, качества хешфункции, балансировки дерева поиска. Определены классы эффективности выполнения словарных операций. Представление о принципах функционирования кэш-памяти процессора дает ознакомление с [18]. Понятие локальности ссылок раскрыто в [19]. ГЛАВА 1. РЕАЛИЗАЦИЯ ОБРАБОТЧИКОВ ВНЕШНИХ СОБЫТИЙ СРЕДСТВАМИ БИБЛИОТЕК STL И QT

14 1. Обработка изменения состава объектов схемы Прежде всего, следует отметить, что обработка изменения состава объектов схемы предполагает манипулирование данными списков, число элементов которых потенциально велико и может достигать нескольких десятков тысяч (см. введение). Поэтому эффективность алгоритмов обхода списков становится критической для быстродействия приложения. 1.1. Обоснование необходимости введения таблицы ObjectTab Назн ачен и е обработчика изм енения со ст ава объектов схем ы ObjectsListTree::objectsListChange() состоит в согласовании списка имеющихся графических объектов схемы и перечня элементов панели. Для упрощения излагаемого материала предположим, что задача обеспечения функциональной возможности отображения элементов ObjectsListTree в упорядоченном виде еще не поставлена. Условием работы метода является вероятное несовпадение порядка следования элементов в списках, что служит предпо сылкой наличия вложенных линейных поисков в алгоритме синхронизации. Уменьшить общее время работы алгоритма и повысить класс эффективности отдельных его частей с квадратичного O(n2) вплоть до O(nlogn) или O(n) в зависимости от выбора структуры данных можно введением индексной т а б л и ц ы ObjectTab, о б е с п еч и в а ю щ е й п о и с к э л е м е н т а п а н е л и п о ассоциированному с ним объекту схемы. Здесь же необходимо указать, что применение индексной таблицы имеет ряд издержек ее сопровождения. Так, все фрагменты кода, изменяющие численность элементов ObjectsListTree, должны быть дополнены соответствующими операторами модификации набора элементов таблицы, что помимо незначительного увеличения общей длительности вставки и уд а л е н и я э л е м е н т о в ObjectsListTree н а л а г а е т н а п р о г р а м м и с т а ответственность за актуальность сведений в индексной таблице. Кроме этого, употребление так называемых итераторов в стиле STL, характерных для структур

15 данных библиотек STL и Qt, для обхода таблицы чревато непредсказуемостью поведения приложения в силу отсутствия поддержки мер извещения об удалении адресуемого элемента и коррекции позиций остальных активных итераторов. Из арсенала доступных в Qt средств ассоциативного поиска [13, 14] наиболее целесообразным для использования в качестве индексной таблицы ObjectTab представляется выбор хеш-таблицы QHash, как весьма эффективной реализации словаря [15, с. 285; 16 с. 323]. Дело в том, что, во-первых, длительность вычисления хеш-функции постоянна и не зависит от количества элементов массива, т. е. хеш-функция обладает средним амортизированным временем выполнения словарных операций O(1). А, во-вторых, ключом здесь будет являться простой сравнимый тип данных – указатель на объект схемы, для которого разработчиками Qt поставляется качественная хеш-функция. Таким образом, состав ObjectsListTree дополняется новым членом: class ObjectsListTree : public QTreeWidget { typedef QHash<DataItem*,ObjectsListTreeItem*> QObjectTab; QObjectTab _objectTab; ... }; 1.2. Описание алгоритма обработки Рассмотрим код обработчика синхронизации списков объектов схемы и элементов, представленных на панели ObjectsListPanel. Его аргументом является указатель на контейнер расположенных на схеме графических объектов. Тело метода составляют два основных блока: в первом из них (строки 1-20) из перечня панели удаляются элементы, объекты которых отсутствуют на схеме, во втором (строки 21-37) производится обновление значений оставшихся и добавление новых. В строках листинга 1-14 формируется строка presence, символически отражающая присутствие ассоциированных с элементами панели объектов на схеме. Условием ее формирования является возможная несогласованность порядка следования элементов в списках, поэтому для нахождения позиции элемента, отвечающего текущему объекту схемы, необходим линейный перебор (строки 6-11). Использование же индексной таблицы в строке 5 позволяет с минимальными издержками выявить отсутствие текущего объекта

16 среди элементов перечня панели. При этом в цикле (строки 15-20), избавляющем ObjectsListTree от лишних элементов, приходится вносить те же изменения и в _objectTab (строка 18). void ObjectsListTree::objectsListChange(Scheme* scheme) { /////////////// Удаление /////////////// (1) QString presence(topLevelItemCount(),'0'); // '0' – отсутствие. (2) Scheme::Iterator obj(*scheme); (3) QTreeWidgetItemIterator item(this); (4) for (uint strIndex; !(++obj)->eol(); ) { (5) if (!_objectTab.contains(obj)) continue; (6) for (QTreeWidgetItemIterator fwd(item); *fwd; ++fwd) (7) if (((ObjectsListTreeItem*)(*fwd))->object()==obj) (8) { item = fwd; goto qfound; } (9) for (QTreeWidgetItemIterator bwd(item); *bwd; --bwd) (10) if (((ObjectsListTreeItem*)(*bwd))->object()==obj) (11) { item = bwd; goto qfound; } (12) found: strIndex = indexOfTopLevelItem(*item); (13) presence[strIndex] = '1'; // '1' – присутствие. (14) } (15) for (uint i=presence.length()-1; i!=~0u; --i) { (16) if (presence[i]=='1') continue; (17) ObjectsListTreeItem* itm = (ObjectsListTreeItem*)takeTopLevelItem(i); (18) _objectTab.remove(itm->object()); (19) delete itm; (20) } По достижении строки 21 количество элементов в списке панели не превосходит числа объектов на схеме. Условие вероятного несовпадения порядка следования элементов сохраняется. Устранять это несоответствие следует именно в блоке добавления элементов ниже, в ином случае обработка вырезки из начала списка объектов схемы стала бы существенно более длительной, поскольку перемещение экземпляров QTreeWidgetItem в п р е д е л а х QTreeWidget является весьма накладным. В строках 25-30 цикла обхода списка объектов дерева выполняется о б н о в л е н и е т е к с т о в ы х м е т о к QTreeWidgetItem и с о г л а с о в а н и е последовательности элементов списков. В строках 32-35 перечень элементов ObjectsListTree расширяется за счет новых объектов схемы. Здесь, как и ранее, необходимо подчеркнуть, что использование индексной таблицы накладывает обязательство обновления ее содержимого вслед за изменением индексируемого

17 набора данных (строка 35). В строке 38 производится обновление выделения элементов ObjectsListTree в соответствии со статусом объектов схемы. (21) (22) (23) (24) (25) (26) (27) (28) (29) (30) (31) (32) (33) (34) (35) (36) (37) (38) } /////////////// Обновление и вставка /////////////// obj.start(); QObjectTab::iterator tabIt; for (uint i=0; !(++obj)->eol(); ++i) { if ((tabIt=_objectTab.find(obj)) != _objectTab.end()) { (*tabIt)->reloadFromObject(); ObjectsListTreeItem *cur = topLevelItem(i), *desired = cur; uint j=i; if (cur->object()==obj) continue; while (desired->object()!=obj) desired = topLevelItem(++j); insertTopLevelItem(i, takeTopLevelItem(j)); } else { ObjectsListTreeItem *newItem = new ObjectsListTreeItem(obj, fieldNames()); newItem->reloadFromObject(); insertTopLevelItem(i, newItem); _objectTab.insert(obj,newItem); } } reloadItemsSelection(); В качестве дополнительного примера снижения затрат поиска при введении индексной таблицы используем обработчик смены выделения графического объекта на схеме objectSelectionChange(), класс эффективности которого в результате был повышен от O(n) до O(1): void ObjectsListTree::objectSelectionChange(DataItem *object) { QObjectTab::iterator item; if ((item=_objectTab.find(object))==_objectTab.end()) return; (*item)->reloadSelectionFromObject(); } 2. Обработка изменения атрибутов объекта схемы Теперь перейдем к рассмотрению обработки изменения значений атрибутов графического объекта схемы ObjectsListTree::objectPropertiesChange(). Длительность его выполнения оказывает существенное влияние на интенсивность динамического отображения в отладочном режиме, требующем наличия панели ObjectsListPanel на экране. При отсутствии необходимости поддержки вывода

18 элементов в отсортированном по значениям текстовых меток виде его содержание составляют несколько строк кода: void ObjectsListTree::objectPropertiesChange(DataItem* object) { QObjectTab::iterator item; if ((item=_objectTab.find(object))==_objectTab.end()) return; (*item)->reloadFromObject(); } В случае же появления необходимости поддержки сортировки реализация обработчика также может остаться простой при условии использования в его теле в с т р о е н н о го м е т од а групповой с о р т и р о в к и э л е м е н т о в QTreeWidget:: sortItems(), всякий раз производящего упорядочение на уровне модели данных и проецирующего результат на уровень элементов. При этом частота обновления кадра будет резко снижена, что недопустимо с точки зрения удовлетворения требований по быстродействию, предъявляемых к системе динамического отображения. Таким образом, для оптимизации обработки с неизбежным повышением сложности алгоритма следует применять средства, позволяющие с малыми издержками определять новую позицию для единичной перестановки модифицированного элемента в перечне ObjectsListTree. Речь здесь идет об индексной таблице ViewOrderTab, реализующей поиск элемента по ключу, образованному строковыми значениями в ячейках ObjectsListTreeItem. 2.1. Обоснование выбора структуры данных таблицы ViewOrderTab Отдельное внимание следует уделить обоснованию выбора структуры данных для ViewOrderTab. В числе альтернатив – хеш-таблица, а также структуры данных, популярные в проектировании ассоциативных словарей, – список с пропусками [17] и сбалансированное дерево поиска [15, с. 341]. Применение принципов хеширования невозможно по двум причинам: во-первых, хеш-массив хранит данные неупорядоченными [14]. Во-вторых, составной ключ сравнения необходимо снабдить [14] не только оператором «==», но и качественной [16 с. 324] хеш-функцией, гарантирующей высокую эффективность хеширования отсутствием коллизий. Причем, если реализация оператора отношения не

19 вызывает проблем, то обеспечить надежность и быстродействие собственной хешфункции одновременно довольно сложно. Следующая в очереди на рассмотрение структура данных – список с пропусками, послуживший основой для создания словаря QMap [13]. Эта структура не поддерживает частичную реиндексацию по причине внутреннего у с т р о й с т ва . П од частичной реиндексацией подразумевается транзакция, включающая поиск элемента с измененным ключом, его извлечение и вставку в структуру на позицию, определяемую новым значением ключа. Рис. 3 иллюстрирует алгоритм вставки элемента с целочисленным ключом в список с пропусками. Заметим, что поиск сопровождается формированием массива указателей update[] на узлы, располженные правее. Предположим, что узел с ключом «7» меняет его значение на, скажем, равное «10». В таком случае нахождение этого узла в структуре остается возможным, но становится более длительным, поскольку будет осуществляться по значению, т. е. с линейным временем поиска. Невозможным же становится извлечение узла из списка, т. к. м е тод QMap::erase(QMap::iterator pos) использует поиск по ключу при формировании массива update[], необходимого для восстановления связности. Так, этот метод, имея ключ аргумента, равный «10», выйдет на узел с ключом «12», после чего предпримет безуспешную попытку последовательным перебором найти узел с соответствующим итератору pos адресом. В итоге будет возвращен итератор крайнего правого элемента. По всей видимости, описанная особенность списка с пропусками стала одной из причин выбора разработчиками Qt красночерного дерева в качестве структуры данных для реализации QMap [14].

20 Рис. 3. Вставка узла в список пропусками (источник [17]) Последней из перечисленных выше ассоциативных структур данных является сбалансированное дерево поиска, а конкретнее – красно-черное дерево, на базе которого разработан словарь std::multimap б и бл и от е к и STL, поддерживающий дублирование ключей. Процедура балансировки дерева при извлечении узла не требует поиска по ключу, следовательно, STL-реализация этой структуры данных может быть использована в качестве индексной таблицы ViewOrderTab. Здесь же следует отметить общий недостаток связных списков и словарей на основе древовидных структур: индекс узла с заданным ключом может быть определен лишь линейным перебором. 1.1. Модификация кода, обусловленная введением таблицы ViewOrderTab По скол ь ку и н дексн ая т аблица ViewOredrTab предназначена для упорядочивания экземпляров класса ObjectsListTreeItem, состав его методов необходимо дополнить оператором отношения «<». Именно оператор «<» используется STL-словарем как средство сравнения двух ключей по умолчанию (см. перечень параметров шаблона std::multimap). bool ObjectsListTreeItem:: operator<(const QTreeWidgetItem& other) const { ObjectsListTree* tree = (ObjectsListTree*)treeWidget(); if (!tree) return false; const QList<Qt::SortOrder>* orders = tree->sortOrders(); for (int col=0, cmp; col < _fieldNames->count(); ++col) { // Результат сравнения меток аргументов в столбце.

21 cmp = text(col).compare(other.text(col)); // Направление сортировки в столбце. Qt::SortOrder ord = (*orders)[col]; if (!cmp) continue; if ((ord == Qt::AscendingOrder && cmp<0) || (ord == Qt::DescendingOrder && cmp>0)) return true; if ((ord == Qt::AscendingOrder && cmp>0) || (ord == Qt::DescendingOrder && cmp<0)) return false; } return false; } Собственно ключом поиска в таблице не может являться ни объект ObjectsListTreeItem, ни указатель на него: в первом случае сравнивались бы локальные копии текстовых меток, во втором – адреса объектов. В роли первого аргумента шаблона std::multimap выступает структура KeyExtr, извлекающая ключ. Так, в ObjectsListTree появляется новый член: class ObjectsListTree : public QTreeWidget { ... struct KeyExtr { KeyExtr(ObjectsListTreeItem* it) : _it(it) { } bool operator< (const KeyExtr& ot) const { return *_it < *(ot._it); } private: ObjectsListTreeItem* _it; }; typedef std::multimap<KeyExtr,ObjectsListTreeItem*> STLViewOrderTab; STLViewOrderTab _viewOrderTab; }; При введении требования поддержки вывода элементов ObjectsListTree модификации также подвергается тело обработчика изменения состава объектов схемы ObjectsListTree::objectsListChange(). Эта модификация заключается в оптимизации алгоритма для режима «Сортировка включена», отличающегося большей степенью рассогласованности списков элементов ObjectsListTree и объектов схемы. В приведенном ниже листинге строки снабжены двойным индексом: второе значение идентифицирует строку кода на страницах 17-19. void ObjectsListTree::objectsListChange(Scheme* scheme) { /////////////// Удаление /////////////// ... (1-4) for (uint strIndex; !(++obj)->eol(); ) { (2) strIndex=0;

22 (3) (4) (5) (6) if (indexedView()) { // «Сортировка включена». QObjectTab::const_iterator otit = _objectTab.find(obj); if (otit==_objectTab.end()) continue; STLViewOrderTab::const_iterator vtit = _viewOrderTab.lower_bound(KeyExtr(*otit)), _vtit = _viewOrderTab.begin(); while ((*vtit).second!=*otit) ++vtit; while (_vtit!=vtit) { ++_vtit; ++strIndex; } } else { ... } presence[strIndex] = '1'; (7) (8) (9-5-12) (10-13) (11-14) } (12-15) for (uint i=presence.length()-1; i!=~0u; --i) { ... (13-18) _objectTab.remove(itm->object()); (14) _viewOrderTab.erase(KeyExtr(itm)); (15-19) delete itm; (16-20) } В строках 4-8 через посредство двух индексных таблиц вычисляется позиция элемента ObjectsListTree, соответствующего текущему объекту схемы, в упорядоченном списке для проставления символа в строке presence. Причем поиск в таблицах осуществляется с логарифмической эффективностью, а определение позиции – с линейной (строка 8). Цикл в строке 7 учитывает возможность наличия в перечне элементов с одинаковым ключом. /////////////// Обновление и вставка /////////////// (17-21) obj.start(); (18-22) QObjectTab::iterator tabIt; (19-23) for (uint i=0; !(++obj)->eol(); ++i) { (20-24) if ((tabIt=_objectTab.find(obj)) != _objectTab.end()) { (21-25) (*tabIt)->reloadFromObject(); (22-26) ObjectsListTreeItem *cur = topLevelItem(i), *desired = cur; uint j=i; (23-27) if (cur->object()==obj || indexedView()) continue; ... (24-32) } else { ... (25-34) insertTopLevelItem(indexedView() ? topLevelItemCount()-1:i, newItem); (26-35) _objectTab.insert(obj,newItem); (27) _viewOrderTab.insert(std::make_pair( KeyExtr(newItem),newItem)); (28-36) } (29-37) } (30) if (indexedView()) sortItems(0,Qt::AscendingOrder); (31-38) reloadItemsSelection(); }

23 П р и у с л о в и и у п о т р е б л е н и я м е т о д а групповой с о р т и р о в к и QTreeWidget::sortItems() (строка 30) в режиме «Сортировка включена» синхронизировать порядки следования в списках на этапе обновления и вставки текущего элемента не требуется (строки 23, 25). Необходимость в согласовании возникнет при выходе из режима сортировки, заметно увеличив длительность этого процесса. Существенным является значение второго аргумента sortItems(), определяющее какой из операторов отношения «<» или «>» (инвертированный «<») будет использован моделью данных при сравнении двух экземпляров ObjectsListTreeItem (см. реализацию QTreeWidget). В очередной раз следует отметить, что при введении дополнительной индексной таблицы для гарантии стабильной работы приложения важно обеспечить согласование (строки 14, 27) ее размерности с численностью элементов индексируемого набора данных всюду, где последняя может изменяться. 1.6144. Описание алгоритма обработки Завершим этот параграф описанием алгоритма обработки изменения атрибутов объекта схемы, поддерживающего вывод элементов ObjectsListTree в упорядоченном виде: void (1) (2) (3) (4) ObjectsListTree::objectPropertiesChange(DataItem* object) { QObjectTab::iterator item; if ((item=_objectTab.find(object)) == _objectTab.end()) return; bool needReindex=(*item)->reloadFromObject()&&indexedView(); if (!needReindex) return; (5) (6) (7) (8) (9) STLViewOrderTab::iterator vtit = _viewOrderTab.begin(); int oldIndex=0; while ((*vtit).second!=(*item)) { ++vtit; ++oldIndex; } _viewOrderTab.erase(vtit); vtit = _viewOrderTab.insert(std::make_pair( KeyExtr(*item), *item)); int newIndex=0; for (STLViewOrderTab::const_iterator _vtit = _viewOrderTab.begin(); _it!=_viewOrderTab.end(); ++_it) { if (_vtit == vtit) break; ++newIndex; } if (oldIndex != newIndex) { insertTopLevelItem(newIndex, takeTopLevelItem(oldIndex)); (*item)->reloadSelectionFromObject(); } (10) (11) (12) (13) (14) (15) (16) }

24 После того, как в строке 3 была установлена необходимость частичной реиндексации, в индексной таблице _viewOrderTab производится линейный поиск элемента, соответствующего модифицированному объекту схемы. Поиск указанного элемента с логарифмическими затратами времени мог быть осуществлен и до изменения его ключа в строке 3, однако, для вычисления его п р е ж н е й п о з и ц и и в ObjectsListTree в с е р а в н о п от р е б о ва л с я б ы последовательный перебор. В общем случае при условии поддержки функциональной возможности фильтрации перечня элементов ObjectsListTree наличие требуемого элемента во _viewOrderTab не является достоверным. Но поскольку в данной работе не рассматривается реализация средств фильтрации с помощью инструментария Qt и STL, в нашем рассуждении (цикл в строке 7) мы исходим из посылки присутствия элемента в таблице как до правки ключа, так и после его вставки с новым значением. В строках 8 и 9 производится частичная реиндексация таблицы _viewOrderTab с последующим перемещением элемента на линейно определенную позицию. ГЛАВА 2. РЕАЛИЗАЦИЯ ОБРАБОТЧИКОВ ВНЕШНИХ СОБЫТИЙ СРЕДСТВАМИ СПЕЦИАЛИЗИРОВАННЫХ БИБЛИОТЕК 1. Пример применения специализированной строковой библиотеки В качестве примера применения специализированной строковой библиотеки используем метод ObjectsListTreeItem::reloadFromObject: int ObjectsListTreeItem::reloadFromObject() { (1) if (!_obj) return 0; (2) int modified = 0; ... (3) for (int col = 0; col < _fieldNames->count(); ++col) {

25 (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) (17) } const SString &fieldName = (*_fieldNames)[col]; SString &cachedValue = _cachedValues[col]; if (!len(fieldName)) { if (!len(cachedValue)) continue; cachedValue.backsp(~0u); } else { const SString &fieldValue = _obj->ronly()(fieldName).asStr(); if (fieldValue==cachedValue) continue; cachedValue.backsp(~0u) << fieldValue; } setText(col, tr(cachedValue)); ++modified; } return modified; Контейнер графического объекта _obj предоставляет значения атрибутов по к л ю ч у fieldName в в и д е с т р о к т и п а SString, определенного в специализированной строковой библиотеке [5, 6]. В целях повышения производительности собственного отображения ObjectsListTreeItem содержит кэш значений текстовых меток _cachedValues. Предположим, что для поддержки кэширования здесь используются средства 16-битной Unicode-строковой системы Qt [13, 14], а именно: набор _cachedValues состоит из строк типа QString. В таком случае мы сталкиваемся с п р о я в л е н и я м и проблемы преобразования строковых типов, часто е возникновение которых снижает быстродействие приложения. Первым из них стало бы создание полноценного временного объекта класса QString от аргумента fieldValue в операторе сравнения «равно-равно» (строка 12) с сопутствующими размещением и удалением разделяемого буфера в куче (см. реализацию QString::operator==(const char*)). Второе проявление заключалось бы в дополнительном конструировании экземпляра QString для источника fieldValue и деструкции текущего буфера приемника cachedValue в операторе п р и с в а и в а н и я ( с м . р е а л и з а ц и ю QString::operator=(const char*)), обновляющем значение кэша после обнаружения несовпадения значений. Код в строке 13 при этом выглядел бы иначе: cachedValue = fieldValue;

26 Единственным достоинством употребления строкового типа QString в кэшсписке _cachedValues являлась бы возможность передачи легкой копии [9, с. 283] строки при установке текстовой метки (строка 15), т. е. в случае кэш-промаха, когда оба описанных выше проявления нивелировали бы преимущество передачи. Применение же средств специализированной строковой библиотеки позволяет полностью исключить обращения к динамической памяти в операторе сравнения двух однотипных строковых выражений [5, 6] (строка 12). Изменение значения кэша в строке 13 так же имеет минимум негативных последствий для быстродействия, поскольку значение буфера источника fieldValue копируется в текущий буфер приемника cachedValue непосредственно без уничтожения последнего с помощью метода SString::backsp(). Этот метод уменьшает длину строки на заданную величину, избегая изменения емкости буфера с нулевым счетчиком ссылок, т. е. востребованного одним объектом SString (устройство класса SString и его разделяемого буфера StringBuf описывается в [5, 6]): SString & SString::backsp(uint n){ register uint l=_buf->_length; // Длина буфера. // Ссылка на данные буфера. SubString bb(_buf->bufData(),l-=n>l?l:n); if (_buf->_shares) { // Число ссылок > 0 – создать новый буфер. --_buf->_shares; // Инициализация созданного буфера. _copyData((_buf = new(bb.length())StringBuf)->bufData(),bb); return *this; } // Установка длины без изменения емкости буфера. _buf->bufData()[_buf->_length=l]=0; return *this; } 2. Обработка изменения состава объектов схемы 1.33807. Модификация кода, обусловленная применением специализированных библиотек Отличия листингов глав 1 и 2 в основном обусловлены тем, что специализированный контейнерный класс [7, 8] используется в качестве хранилища элементов панели для выделения и снятия части вычислительной нагрузки, связанной с операциями поиска, перестановки и сортировки

27 экземпляров ObjectsListTreeItem, с ObjectsListTree как инструмента отображения. Так, обработчик изменения перечня объектов схемы objectsListChange() извлекает элементы из ObjectsListTree, производит синхронизацию средствами контейнера и вставляет их обратно в заданном порядке, оставляя за виджетом воспроизведение результата на экране. Применение специализированных библиотек накладывает ряд изменений в устройстве классов отображения: ObjectsListTreeItem, к а к э л е м е н т с п е ц и а л и з и р о ва н н о го ко н т е й н е р а , п р и о б р е т а е т с о от ве т с т ву ю щ у ю функциональность с введением дополнительной базы наследования – elem [8], а в наборе его свойств появляются указатели на соседние элементы списка, при этом определение оператора сравнения переходит на уровень параметров шаблона индексной таблицы контейнера: class ObjectsListTreeItem : public elem, public QTreeWidgetItem {...} Класс ObjectsListTree получает в свой состав список-владелец элементов _items, а также индексные таблицы _objectTab и _viewOrderTab. Аргументами шаблона индексной таблицы Idx являются тип элемента контейнера, тип ключа, а также типы функциональных классов, осуществляющих извлечение ключа из элемента, сравнение ключей и их фильтрацию [8]. class ObjectsListTree : public QTreeWidget { List<ObjectsListTreeItem> _items; // Макрос извлечения ключа. defExtractor(ObjPtrExtr,DataItem*,i.object()); typedef Idx<ObjectsListTreeItem, // Тип элемента. DataItem*, // Тип ключа. NumCmp, // Целочисленное сравнение. ObjPtrExtr, // Оператор извлечения ключа. NoFilter> ObjectTab; // Фильтр отсутствует. ObjectTab *_objectTab; // Специфические функциональные объекты, определяемые местно. struct ExprCmp; // Оператор сравнения. struct ExprFilter; // Оператор фильтрации. typedef Idx<ObjectsListTreeItem, ObjectsListTreeItem, ExprCmp, ObjRef, // Ключ – ссылка на элемент. ExprFilter> ViewOrderTab; ViewOrderTab *_viewOrderTab;

28 ... void takeItemsFromTree(); // Изъять элементы. void putItemsToTree(); // Вставить элементы. }; Популярные функциональные объекты определены в заголовочном файле специализированной контейнерной библиотеки: struct NumCmp { template <class Key1,class Key2> int operator()(const Key1 &k1,const Key2 &k2) { return k1==k2?0:(k1<k2?-1:1); } }; struct ObjRef { template <class Elem> const Elem& operator()(const Elem &i) const { }; #define defExtractor(id,type,expr) struct id { \ template <class Elem> \ type operator()(const Elem &e) const { return } struct NoFilter { template <class Elem> int operator()(const Elem&) const { return 1; }; const return i; } expr; } \ } Специфические функциональные объекты сортировки и фильтрации выполняют соответственно сравнение текстовых меток двух экземпляров ObjectsListTreeItem, а также проверку выполнения условия фильтрации: struct ObjectsListTree::ExprCmp { QList<SString> _fieldNames; // Имена столбцов. QList<Qt::SortOrder> _orders; // Направления сортировок. int _indexOn; // Признак режима «Сортировка включена». ExprCmp() { _indexOn = 0; } int operator() (const ObjectsListTreeItem &k1, const ObjectsListTreeItem &k2) const { int ret = 0; if (_indexOn) { for (int i=0; i< _fieldNames.count(); ++i) { const SString& value1 = k1.cachedValues()[i]; const SString& value2 = k2.cachedValues()[i]; // Лексикографическое сравнение [6]. ret = _orders[i] == Qt::AscendingOrder ? compare(value1, value2) : compare(value2, value1); if (ret) break; } } return ret; }

29 }; struct ObjectsListTree::ExprFilter { const QList<SString>* _fieldNames; // Таблица условий фильтрации. mutable QList< QList<QRegExp> > _patterns; Qt::CaseSensitivity _caseSensivity; int _filterOn; // Признак режима «Фильтрация включена». ExprFilter() : _caseSensivity(Qt::CaseSensitive) { _filterOn = 0; } int operator()(const ObjectsListTreeItem& item) const { if (!_filterOn) return 1; ... // Анализ соответствия условиям. } }; 1.1. Описание алгоритма обработки Рассмотрим код обработчика изменения состава объектов схемы. Метод, как и в п. 1.2 главы 1, состоит из блоков удаления и вставки, и начинает с изъятия элементов ObjectsListTreeItem из виджета (строка 1). Далее в строках 2-17 из списка-члена _items удаляются элементы, объекты которых отсутствуют на схеме. Отметим, что порядок следования элементов в _items не зависит от пребывания в режиме «Сортировка включена» – последовательность элементов, отображаемых в ObjectsListTree, определяется индексной таблицей _viewOrderTab. Следовательно, списки объектов схемы и элементов ObjectsListTree отличает более высокая степень согласованности, по сравнению с примером п. 1.2 главы 1, что, в свою очередь, уменьшает число линейных переборов в теле обработчика. Метод Idx::seekf() (строка 6) находит элемент с заданным ключом с помощью функции бинарного поиска [2, с. 180] и возвращает его позицию либо нуль в случае неудачи. Если в таблице присутствует несколько элементов с одним и тем же ключом, метод вернет позицию первого, т. е. крайнего левого элемента группы дубликатов. Нумерация элементов с полезной нагрузкой начинается с единицы – нулевой индекс имеет граничный «головной» элемент. Здесь же следует отметить, что для таблицы-массива Idx [8] определен метод operator[], возвращающий элемент по заданному индексу. Итераторы списка контейнера List и его индексных таблиц Idx на уровне и х общей базы cntr::__itr имеют целочисленный член cp [8], фиксирующий

30 текущую позицию, и предоставляют его значение посредством метода operator+ ( ) (строка 11). Таким образом, выяснение индекса итерируемого элемента становится значительно менее вычислительно-затратным. Итератор со значением cp, равным нулю, адресует левый граничный элемент списка либо индексной таблицы без полезной нагрузки. Оператор item.cutr() в строке 16 вырезает итерируемый элемент списка и переводит итератор левее: для неконстантных итераторов структур данных контейнерной библиотеки в отличие от итераторов в стиле STL определены операции вставки и удаления элементов [8]. При этом в результате выполнения последней итератор пригоден к использованию, поскольку его позиция установлена. Контейнерные структуры Qt, к примеру, поддерживают так называемые итераторы в стиле Java [9, с. 279], для которых также реализована операция удаления. Однако ее применение требует дополнительного вызова метода валидации позиции типа next() или previous(). Помимо этого оператор вырезки элемента в строке 16 может быть использован как иллюстрация мер защиты от утечек памяти, поддерживаемых на уровне контейнерной библиотеки. Так, возвращаемым значением здесь служит временный объект класса Lst, предназначенного для хранения и передачи вырезок элементов контейнера [8], уничтожающий содержимое в деструкторе: Lst<elem> List::itr::cutr(); Необходимость в явном вызове delete пропадает. Следует обратить особое внимание на отсутствие операторов удаления узлов индексных таблиц в цикле в строках 14-17. Дело в том, что индексные таблицы Idx контейнера организуются в кольцевую структуру вокруг списка List [8], чем обеспечивается возможность автоматического сопровождения изменения численности элементов списка соответствующей модификацией состава таблиц на уровне методов списка. Тем самым минимизируется риск возникновения ошибок индексирования, а с программиста-пользователя контейнерной библиотеки снимается ответственность за согласование размерностей индексируемой и индексирующей структур данных.

31 void ObjectsListTree::objectsListChange(Scheme *scheme) { /////////////// Удаление /////////////// (1) takeItemsFromTree(); (2) QString presence(topLevelItemCount(),'0'); // '0' – отсутствие. (3) Scheme::Iterator obj(*scheme); (4) List<ObjectsListTreeItem>::itr item(_items); (5) while (!(++obj)->eol()) { (6) if (!_objectTab->seekf(obj)) continue; (7) for (List<ObjectsListTreeItem>::itr fwd(item); !(++fwd)->eol(); ) (8) if (fwd->object() == obj) { item = fwd; goto found; } (9) for (List<ObjectsListTreeItem>::itr bwd(item); !(--bwd)->bol(); ) (10) if (bwd->object() == obj) { item = bwd; goto found; } (11) found: presence[+item-1] = '1'; (12) } (13) item.start(); (14) for (uint i=0; i<presence.length(); ++i) { (15) ++item; (16) if (presence[i]=='0') item.cutr(); (17) } Во второй части обработчика, как и ранее, производится обновление оставшихся в списке экземпляров ObjectsListTreeItem и добавление новых. При обнаружении в списке контейнера элемента, соответствующего текущему объекту схемы, значения его текстовых меток корректируются (строки 23-24). Если позиция элемента в списке контейнера не совпадает с позицией объекта в списке схемы, либо в случае потребности в частичной реиндексации, выполняется его перестановка за элемент --item, т. е. на текущую позицию (строка 29). Оператор в строке 33 вставляет созданный элемент, к нему же перемещается item. Перестановка элементов в списке обеспечивает автоматическое размещение ключей в индексных таблицах согласно установленным правилам сортировки и фильтрации (см. предыдущий абзац). По выходе из цикла перебора объектов схемы, т. е. по завершении синхронизации списков, осуществляется возврат элементов _items в ObjectsListTree для отображения (строка 36) в порядке, заданном индексной таблицей _viewOrderTab. (18) (19) (20) (21) (22) /////////////// Обновление и вставка /////////////// obj.start(); item.start(); List<ObjectsListTreeItem>::itr _item(_items); ObjectTab::itr tabIt(*_objectTab); while (!(++obj)->eol()) { ++item;

32 (23) (24) (25) (26) (27) (28) (29) (30) (31) if (tabIt.seekf(obj)) { bool needReindex = tabIt->reloadFromObject() && indexedView(); _item = item; if (item->object()!=obj) while ((++_item)->object()!=obj) ; else { if (!needReindex) continue; } --item<<_item.cutr(); } else { ObjectsListTreeItem *newItem = new ObjectsListTreeItem(obj, fieldNames()); newItem->reloadFromObject(); --item << newItem; } (32) (33) (34) (35) } (36) putItemsToTree(); } 3. Обработка изменения атрибутов объекта схемы 1.1. Описание алгоритма обработки Перейдем к рассмотрению обработчика изменений атрибутов объекта схемы. Воспроизведем алгоритм п. 2.3 главы 2 с помощью средств специализированной контейнерной библиотеки. Как и прежде, тело обработчика образуют операции: 1. поиска (строка 1) экземпляра ObjectsListTreeItem item, соответствующего аргументу метода – объекту схемы object, в таблице _objectTab; 2. обновления (строка 4) значений текстовых меток item, составляющих индексный ключ в таблице _viewOrderTab, и установления необходимости частичной реиндексации; 3. определения (строка 6) позиции item в о _viewOrderTab, отвечающей прежнему значению индексного ключа и совпадающей с позицией в дереве отображения ObjectsListTree; 4. выполнения (строки 7-9) частичной реиндексации – извлечение и вставка item во _viewOrderTab; 5. определения (строка 10) позиции item во _viewOrderTab, отвечающей новому значению индексного ключа; 6. перестановки (строки 11-17) item с прежней позиции на новую в дереве отображения ObjectsListTree. void ObjectsListTree::objectPropertiesChange(DataItem* object) {

33 (1) (2) (3) (4) (5) uint objectIndex = _objectTab->seekf(object); if (!objectIndex) return; ObjectsListTreeItem *item = (*_objectTab)[objectIndex]; bool needReindex = item->reloadFromObject()&&indexedView(); if (!needReindex) return; (6) (7) (8) (9) int oldIndex = (int)_viewOrderTab->seek(item)-1; List<ObjectsListTreeItem>::itr i(_items); i.seek(item); i<<i.cutr(); (10) int newIndex = (int)_viewOrderTab->seek(item)-1; (11) if (oldIndex != newIndex) { (12) if (oldIndex >= 0) takeTopLevelItem(oldIndex); (13) if (newIndex >= 0) { (14) insertTopLevelItem(newIndex,item); (15) item->reloadSelectionFromObject(); (16) } (17) } } Отличие приведенных листингов заключается в реализации операций 3-5, которая, в свою очередь, учитывает особенности устройства специализированного контейнера. Организация индексной таблицы Idx специализированного контейнера в виде сплошного упорядоченного массива позволяет эффективно использовать возможности программного и аппаратного кэширования [8]. Так, длительность линейного перебора элементов таблицы _viewOrderTab в поисках item по значению (операция 3, строка 6), оказывается меньше соответствующего результата для индексной таблицы на базе красно-черного дерева (см. выводы). По всей видимости, такое соотношение может объясняться более эффективным использованием аппаратного кэша [19], обусловленном локализованным [20, с. 359] размещением Idx на страницах памяти. Если прежнее значение ключа item не удовлетворяло заданному для _viewOrderTab условию фильтрации, поиск окажется неудачным, результат – равным минус единице. Частичная реиндексация (операция 4, строки 7-9) требует линейного розыска текущего элемента в списке контейнера для инициализации итератора. Затем производится вырезка и вставка item на ту же позицию, неявно сопровождаемая аналогичными операциями в обеих индексных таблицах. Сохранение позиции вставки означает сохранение порядка следования элементов

34 в списках _items и объектов схемы. Реиндексация всей совокупности таблиц индексируемого набора данных занимает более длительное время, но вместе с тем снижает вероятность возникновения ошибок индексирования. Разница времен реиндексации для двух реализаций алгоритма данного обработчика ощутима (см. выводы), поскольку определения ключей индексных таблиц не имеют пересечений и модификация текстовых меток item требует изменений лишь в одной из них. Примером результативности кэширования на программном уровне служит оператор вычисления новой позиции item (операция 5, строка 10). Процедура вставки в Idx запоминает индекс аргумента во внутренней переменной found, являющейся начальной позицией поиска, как по ключу, так и по значению. Следовательно, время работы метода поиска последнего вставленного элемента в строке 10 будет ничтожно малым и постоянным, т. е. не зависящим от числа элементов в таблице. В случае несоблюдения условия фильтрации поиск item с измененным значением ключа, как и ранее, будет неудачным, что в итоге будет означать отсутствие элемента в виджете ObjectsListTree. ВЫВОДЫ В главах 1 и 2 описана реализация обработчиков внешних событий с помощью инструментов двух групп: средств библиотек STL и Qt, а также средств специализированных библиотек. Воспользуемся критериями надежности и быстродействия для характеристики отличия эффективности реализации. При этом следует учитывать, что количественные оценки могут быть получены лишь для последнего из них. В качестве подтверждения повышения надежности приведем следующее соображение. Возможность беспрепятственного уничтожения экземпляров QTreeWidgetItem, хранимых QTreeWidget непосредственно, создает условия для рассогласования содержимого индексных таблиц и индексируемого набора данных. В то время как список ObjectsListTree::_items владеет собственными

35 элементами, что запрещает их деструкцию до извлечения из списка: попытка деструкции связанного элемента приведет к аварийному завершению работы [8]. Тем самым обеспечивается защита от ошибок индексирования и многократного освобождения памяти. Иллюстрацией увеличения быстродействия служит пример обработки последовательного дублирования общего числа объектов схемы в режиме « С о р т и р о в к а в к л ю ч е н а » : о ч е р е д н о й в ы з о в ObjectsListTree:: objectsListChange( ) удваивает число элементов в упорядоченном списке панели (см. рис. 4). Метки на оси абсцисс отмечают количество объектов схемы до дублирования. Соответствующие значения на оси ординат – время выполнения операции в секундах. Результат измерения на рис. 5 показывает, что разница в продолжительности обработки с помощью двух групп средств вставки растет и становится заметной при дублировании 800 объектов. Рис. 4. Панель «Список объектов схемы» до и после дублирования объектов схемы

36 Рис. 5. Оценка быстродействия операции дублирования объектов схемы Продемонстрируем разницу эффективности обработки изменения значений атрибутов графического объекта схемы с помощью следующего теста динамического отображения. Пусть группа примитивов перемещается горизонтально слева направо с заданной скоростью в поле однотипных объектов схемы с несовпадающей абсциссой (см. рис. 6). Если при этом в панели «Список объектов схемы» в числе прочих свойств отображается значение атрибута «Х», то составной ключ сортировки перемещаемых объектов будет всякий раз меняться. Таким образом, каждая обработка в режиме «Сортировка включена» потребует частичной реиндексации перечня элементов панели.

37 Рис. 6. Динамическое отображение горизонтального перемещения примитивов Условные результаты измерений продолжительности обработки перемещения группы примитивов из начальной в конечную точку представлены на рис. 7: в таблице перечислены составляющие тело обработчика операции (см. п. 3.1 главы 2) с указанием затраченного времени в секундах. Операция обработчика ObjectsListTree:: objectPropertiesChange() Обновление значений текстовых меток Определения прежней позиции Частичная реиндексация Определение новой позиции Перестановка в ObjectsListTree Общее время обработки Средства Средства специализированных библиотек библиотек STL и Qt 0,65483 0,67 0,00622 0,12382 0,16273 0,07058 0 0,12684 3,2201 3,2071 4,04388 4,19834 Рис. 7. Соотношения временных издержек компонент обработки изменения атрибутов графического объекта

38 Общая разница длительности обработки не существенна, поскольку ее основную часть занимают операции обновления текстовых меток экземпляра QTreeWidgetItem, его извлечения из QTreeWidget и вставки обратно. Время их выполнения не зависит от смены инструментальных средств. Результатом применения средств специализированных библиотек (см. п. 3.1 главы 2) с т а н о в и т с я сокращение продолжительности частичной реиндексации, обусловленное изменением соотношения временных издержек ее компонент. Так, уменьшение времени поиска элемента таблицы с модифицированным ключом объясняется тем, линейный перебор элементов сплошного массива оказывается быстрее аналогичной операции, выполняемой в дереве поиска. Причиной увеличения времени реиндексации является необходимость правки всех индексных таблиц контейнера – гарантия надежности требует некоторого снижения быстродействия. Отсутствие вычислительных затрат определения позиции элемента, соответствующей новому значению его ключа, обеспечивается эффективностью кэширования его индекса при вставке. ЗАКЛЮЧЕНИЕ Рассмотрен ряд примеров применения специализированных библиотек, позволившего унифицировать средства разработки функциональной и графической частей системы динамического отображения, обеспечить широкие функциональные возможности элементов пользовательского графического интерфейса, повысить производительность и надежность приложения, а также снизить издержки его сопровождения в сравнении со стандартными популярными средствами, предлагаемыми разработчиками библиотек STL и Qt.

39 Список литературы 1. Безлепкин В. И., Кухтевич В. О., Образцов Е. П., Мигров Ю. А., Шаленинов А. А., Деулин А. А. Программно-технический комплекс «Виртуальный энергоблок АЭС с ВВЭР» (ПТК «ВЭБ») для проверки проектных решений АЭС-2006 [ Эл е кт р о н . р е су р с ] U R L : h t t p : / / w w w. g i d r o p r e s s . p o d o l s k . r u / f i l e s / proceedings/mntk2013/documents/mntk2013-168.pdf (дата обращения: 21.10.2015). 2. Горизонты Атома (16.02.2013): Виртуальная АЭС // Информ. агентство «Российское атомное сообщество». [Электрон. ресурс] URL: http://www.atomicenergy.ru/video/40025 (дата обращения 15.09.2015). 3. Калинин Д. В. Многофункциональный графический редактор видеокадров БПУ в составе моделирующего комплекса «Виртуальный энергоблок» [Электрон. ресурс] URL: http://docs.google.com/viewer?a=v&pid=sites&srcid= ZGVmYXVsdGRvbWFpbnxzaGFyaW5nc3BhY2UxNnxneDo0YWI3NTRhM2JlZT MxODE5 (дата обращения 20.02.2016). 4. Orekhov M. Yu. Specialized Container and String Systems Employment in Vector G r a p h i c s E n v i r o n m e n t D e v e l o p m e n t [Электрон. ресурс] URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342211&searchWithin=

40 %22First%20Name%22:Mikhail&searchWithin=%22Last%20Name %22:Orekhov&newsearch=true (дата обращения: 15.02.2016). 5. Орехов М. Ю. Быстродействующая строковая система на С++ // Процессы управления и устойчивость. 2014. Т. 1, № 1. С. 363-368. 6. Орехов М. Ю. Применение подстроки в реализации быстродействующей строковой системы на С++ // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2015. Вып. 2. С. 134-149. 7. Орехов М. Ю. Контейнерный класс для задач отображения векторной графики // Процессы управления и устойчивость. 2015. Т. 2 (18), № 1. С. 473478. 8. Калинин Д. В., Орехов М. Ю. Специализированная контейнерная библиотека для задач динамического отображения векторной графики // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2016. Вып. 2. С. 45-61. 9. Бланшетт Ж., Саммерфилд М. Qt4: программирование GUI на C++. 2-е изд., доп. / пер. с англ. С. Лунина, В. Казаченко. М.: Кудиц-Пресс, 2008. 736 с. 10. Summerfield M. Advanced Qt Programming: Creating Great Software with C++ and Qt 4. Upper Saddle River, New Jersey: Addison-Wesley, 2010. 537 c. 11. Руководство по стандартной библиотеке шаблонов (STL) [Электрон. ресурс] URL: http://www.solarix.ru/for_developers/cpp/stl/stl.shtml (дата обращения: 28.05.2016). 12. Standard Template Library Programmer's Guide [Электрон. ресурс] URL: http://www.sgi.com/tech/stl/index.html (дата обращения: 29.05.2016). 13. Qt 4.8 All Classes // Qt Documentation [Электрон. ресурс] URL: http://doc.qt.io/ qt-4.8/classes.html (дата обращения: 03.06.2016). 14. Qt 5.6 All Classes // Qt Documentation [Электрон. ресурс] URL: http://doc.qt.io/ qt-5/classes.html (дата обращения: 03.06.2016). 15. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 3-е изд. / пер. с англ. И. В. Красикова. М.: Издат. дом «Вильямс», 2013. 1328 с. 16. Левитин А. Алгоритмы: введение в разработку и анализ / пер. с англ. С. Г. Тригуб, И. В. Красикова. М.: Издат. дом «Вильямс», 2006. 576 с. 17. Pugh W. Skip Lists: A Probabilistic Alternative to Balanced Trees // Communications of the ACM. 1990. Vol. 33, N. 6. P. 668-676.

41 18. Общие принципы функционирования кэш-памяти // НОУ ИНТУИТ [Электрон. р е с у р с ] URL: http://www.intuit.ru/studies/courses/604/460/lecture/10327 (дата обращения: 06.04.2016). 19. Бек Л. Введение в системное программирование / пер. с англ. Н. А. Богомолова, В. М. Вязовского и С. Е. Морковина; под ред. Л. Н. Королева. М.: Мир, 1988. 448 с.

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв