Специализированная контейнерная библиотека для задач динамического отображения векторной графики Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Калинин Дмитрий Владимирович, Орехов Михаил Юрьевич

Рассматриваются вопросы инструментальной поддержки разработки системы динамической визуализации векторных объектно-ориентированных 2D схем открытого текстового формата в составе комплекса моделирования сложных технических объектов на уровне проектирования надежной и быстродействующей контейнерной библиотеки. Обеспечение высокой скорости выполнения словарной операции поиска позволяет представлять графические объекты в виде гибких структур ассоциативных массивов атрибутов переменного типа со строковым индексом, упрощая создание и сопровождение системы отображения в условиях неопределенности перечня типов моделируемых объектов и правил их динамического поведения. Быстрый поиск атрибута по имени приобретает особую важность для функционирования системы в реальном времени при визуализации схем сложных объектов с численностью графических объектов в несколько десятков тысяч. Помимо этого ключевого свойства контейнерная библиотека должна удовлетворять ряду перечисленных в статье специфических требований. Предложен вариант реализации, учитывающий названные ограничения. Продемонстрированы оценки быстродействия операций вставки и поиска для разработанного контейнерного класса и его аналогов из популярных библиотек STL и Qt. Библиогр. 12 назв. Ил. 4.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Калинин Дмитрий Владимирович, Орехов Михаил Юрьевич

SPECIALIZED CONTAINER LIBRARY FOR PURPOSES OF VECTOR GRAPHICS DYNAMIC DISPLAYING

This paper considers instrumental support issues of complex technological objects modelling on the level of container library design for the purposes of vector object-oriented 2D open-text formatted schemes real-time dynamic displaying. Guaranteed rapid key-string search allows presenting the graphical objects as variable structures string-indexed associative containers of mutable-typed attributes, simplifying visualization system development and maintenance under simulated objects types and dynamic behavior patterns indeterminacy condition. Displaying system efficiency becomes critically dependent from attribute key-string look-up duration as modelled object complexity increases and reveals in great amount of scheme graphical objects, reaching several thousands. Besides this feature, container library must answer some other specific requirements. This article enumerates them and suggests applicable implementation. The present paper also adduces the results of test, estimating insertion and look-up speed, performed for designed container class and its analogues provided by STL and Qt. Refs 12. Figs 4.

Текст научной работы на тему «Специализированная контейнерная библиотека для задач динамического отображения векторной графики»

2016 ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА Сер. 10 Вып. 2

Д. В. Калинин1, М. Ю. Орехов1'2

СПЕЦИАЛИЗИРОВАННАЯ КОНТЕЙНЕРНАЯ БИБЛИОТЕКА ДЛЯ ЗАДАЧ ДИНАМИЧЕСКОГО ОТОБРАЖЕНИЯ ВЕКТОРНОЙ ГРАФИКИ

1 ФГУП «Научно-исследовательский технологический институт имени А. П. Александрова», Российская Федерация, 188540, Ленинградская обл., г. Сосновый Бор, Копорское шоссе, 72

2 Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7—9

Рассматриваются вопросы инструментальной поддержки разработки системы динамической визуализации векторных объектно-ориентированных 2D схем открытого текстового формата в составе комплекса моделирования сложных технических объектов на уровне проектирования надежной и быстродействующей контейнерной библиотеки. Обеспечение высокой скорости выполнения словарной операции поиска позволяет представлять графические объекты в виде гибких структур — ассоциативных массивов атрибутов переменного типа со строковым индексом, упрощая создание и сопровождение системы отображения в условиях неопределенности перечня типов моделируемых объектов и правил их динамического поведения. Быстрый поиск атрибута по имени приобретает особую важность для функционирования системы в реальном времени при визуализации схем сложных объектов с численностью графических объектов в несколько десятков тысяч. Помимо этого ключевого свойства контейнерная библиотека должна удовлетворять ряду перечисленных в статье специфических требований. Предложен вариант реализации, учитывающий названные ограничения. Продемонстрированы оценки быстродействия операций вставки и поиска для разработанного контейнерного класса и его аналогов из популярных библиотек STL и Qt. Библиогр. 12 назв. Ил. 4.

Ключевые слова: контейнерный класс, гибкая структура, поиск по строковому ключу, ассоциативный массив, векторная графика.

D. V. Kalinin1, M. Yu. Orekhov1'2

SPECIALIZED CONTAINER LIBRARY FOR PURPOSES OF VECTOR GRAPHICS DYNAMIC DISPLAYING

1 Alexandrov Research Institute of Technology, 72, Koporskoe highway, Sosnovy Bor, Leningrad region, 188540, Russian Federation

2 St. Petersburg State University, 7—9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation

Калинин Дмитрий Владимирович — начальник группы лаборатории систем автоматизации разработки моделирующих комплексов и тренажеров; kdv2112@mail.ru

Орехов Михаил Юрьевич — инженер лаборатории систем автоматизации разработки моделирующих комплексов и тренажеров, аспирант; genazvale2005@yandex.ru

Kalinin Dmitriy Vladimirovich — training and engineering simulators computer-aided design laboratory head of group; kdv2112@mail.ru

Orekhov Mikhail Yurievich — training and engineering simulators computer-aided design laboratory programmer, post-graduate student; genazvale2005@yandex.ru

© Санкт-Петербургский государственный университет, 2016

This paper considers instrumental support issues of complex technological objects modelling on the level of container library design for the purposes of vector object-oriented 2D open-text formatted schemes real-time dynamic displaying. Guaranteed rapid key-string search allows presenting the graphical objects as variable structures — string-indexed associative containers of mutable-typed attributes, simplifying visualization system development and maintenance under simulated objects types and dynamic behavior patterns indeterminacy condition. Displaying system efficiency becomes critically dependent from attribute key-string look-up duration as modelled object complexity increases and reveals in great amount of scheme graphical objects, reaching several thousands. Besides this feature, container library must answer some other specific requirements. This article enumerates them and suggests applicable implementation. The present paper also adduces the results of test, estimating insertion and look-up speed, performed for designed container class and its analogues provided by STL and Qt. Refs 12. Figs 4.

Keywords: container class, variable structure, key-string search, associative array, vector graphics.

Введение. Статья посвящена вопросам проектирования надежной и быстродействующей специализированной контейнерной библиотеки. Устройство контейнерного класса представлено как сочетание двусвязного списка, непосредственно содержащего размещенные объекты, и набора индексных таблиц поиска объекта по заданному ключу с поддержкой сортировки и фильтрации.

Из накопленного запаса идей, терминов и подходов в области программной реализации словарей — конечных динамических множеств с определенными операциями вставки, поиска и удаления элементов — для индексной таблицы выделены альтернативные структуры данных: хеш-таблица [1, c. 285; 2, с. 323], вариант сбалансированного дерева поиска [1, с. 341], список с пропусками [3] и сплошной массив упорядоченных идентификаторов с функцией бинарного поиска [2, с. 180].

В настоящей работе обоснован выбор массива ключей в качестве индексной таблицы: перечислены решения, позволившие уменьшить время выполнения словарной операции поиска в сравнении с древовидными структурами и обеспечить функциональность сортировки и фильтрации ключей, недоступную для хеш-таблиц.

Примером области приложения контейнерной библиотеки как инструмента разработки является среда динамической визуализации векторных объектно-ориентированных 2D схем открытого текстового формата — компоненты программно-вычислительного комплекса. Одним из условий проектирования среды был учет неопределенности палитры типов графических примитивов, объектов и перечня их атрибутов, обусловленной тем, что состав моделируемого оборудования, а также набор специфических свойств каждой единицы могут быть расширены на дальнейших этапах разработки и эксплуатации комплекса. Число размещенных на схеме графических объектов может достигать нескольких тысяч, суммарное количество их графических атрибутов — десятков тысяч. Среда визуализации должна обеспечивать редактирование и динамическое отображение объектов схемы в реальном времени (с частотой обновления не менее 5 FPS). Описание контекста применения среды визуализации приводится в работе [4] и видеоролике [5]. Конкретная задача, обусловившая создание среды в этом контексте, сформулирована в статьях [6, 7].

В п. 1 данной статьи предложен способ организации разнородных атрибутов графического объекта в виде контейнерного класса. Характерные для области приложения требования к выбору структур данных его реализации перечислены в п. 2. Модель контейнера, удовлетворяющая названным требованиям с гарантией высокого быстродействия, описана в п. 3. В п. 4 представлены сравнительные результаты

тестов оценки времени выполнения операций вставки и поиска для разработанного контейнерного класса и его аналогов из библиотек STL и Qt.

1. Графический объект — контейнер атрибутов. В рамках использования открытого текстового формата схемы графические примитивы и объекты задаются SVG-подобными определениями собственных атрибутов:

CLASS=obj TYPE=Std_ana_veu NAME= ВЕ8СЯ=МощнПотребл X=2102 Y=209 Z=822 . TYPE=ellipse NAME= DESCR=Обмотка!32трансформатора X=2610.42 .

Рассмотрим подход к построению иерархии графических сущностей с неопределенным набором свойств (примитив, составной объект, схема) в виде объектов гибкой структуры — ассоциативных контейнеров: таблиц идентификаторов атрибутов произвольного типа со строковым индексом-ключом поиска, формируемых в процессе разбора текстового определения. Под гибкостью структуры здесь подразумевается возможность изменения как количества элементов, так и их качества — тип хранимого значения атрибута (строковый, целочисленный или вещественный) определяется последней операцией присваивания. Класс «таблица идентификаторов» имеет вид

template<class Attr> class IdentifierTable

static int nol(const item *i) < .. public:

item(const item &) < link(this); >void operator=(const item &) < >virtual

3.2. База наследования элементов контейнера elem. Производство элементов от общего предка допускает совместное хранение объектов разных уровней иерархии. Наследование с ключом private делает «происхождение» от item скрытым как для потомков elem, так и для внешних классов за исключением дружественных:

class elem : private item

elem(const elem&) : item(*this) < >//

elem() < if(!item::nol()) err("linked somewhere"); >// Аварийный выход . // при попытке деструкции связанного элемента.

3.3. Список временного хранения 1st. Описываемая реализация линейного двусвязного списка предполагает владение элементами для предотвращения их многократного уничтожения: два контейнера не могут иметь общих элементов, деструкция контейнера предусматривает деструкцию данных. Поэтому передача части элементов между списками-владельцами возможна либо созданием «глубокой» копии, либо путем вырезки. Вырезки перемещаемых (move) элементов организуются в виде кольцевых списков промежуточного хранения — объектов класса lst:

mutable uint len; // Число элементов.

static void ins(const item *m,const elem *e); // Вставить e перед m. static uint ins(const item *m,const lst &l); // Вставить содержимое l protected: // перед m. Замкнуть l.

struct _cut_p < >; // Абстрактная граница вырезки.

typedef void _cut_f (lst *out,_cut_p *from); // Методы вырезки в out. typedef void _cut_to_f(lst *out,_cut_p *from,const _cut_p *to); //

lst &operator=(const lst &l); // Переместить (move) содержимое l.

lst(const lst &l); // Переместить содержимое l. // «Виртуальные» конструкторы lst.

lst(_cut_f *fn,_cut_p *from)

. > // Элемент не связан (замкнут).

// Замкнуть созданную копию.

lst(_cut_to_f *fn,_cut_p *from,const _cut_p *to)

lst(); // Деструкция содержимого.

Возможность вырезки элементов из заданного источника обеспечивается применением механизма «виртуального» (фактического) конструирования, избавляющего от необходимости включения в состав lst специфических конструкторов для каждого вероятного потребителя: конкретный способ вырезки сообщается экземпляру lst в момент создания параметрически. Механизм использует стандартное свойство языка [10] опускать промежуточные конструкторы, поддерживаемое оптимизирующим компилятором. Вызов «виртуальных» конструкторов разрешен объектам классов, имеющих доступ к определению абстрактных границы и методик вырезки.

Контроль типов хранимых элементов осуществляется введением шаблона Lst с опубликованными операторами присваивания и вставки. Так, конкретная инстанция Lst может содержать потомков elem одного уровня и ниже, попытка же размещения в Lst более абстрактного представителя иерархии будет блокирована компилятором:

template <class Elem> class Lst : public lst < public:

3.4■ База наследования структур данных контейнера cntr. Каждый список-владелец элементов контейнера ассоциируется с одной или несколькими индексными таблицами. Для упрощения взаимодействия этих сущностей и управления ими предлагается использовать единую базу наследования — node, что позволяет организовывать индексные таблицы в кольцевой список вокруг головного элемента — списка контейнера — с автоматической регистрацией при создании и извлечением при деструкции:

node() : item(*this) < >// Головной элемент списка.

node(const node &n) : item() < ins(&n,this); >// Вставка перед n.

node( ) < unlink(this); >// Деструкция с извлечением.

node &operator=(const node &n) // Смена списка.

Класс cntr, как общий предок линейного двусвязного списка-владельца элементов контейнера и индексной таблицы, поддерживает константные (RO — read-only) и неконстантные (RW — read-write) итераторы. RO-итератор на время своего существования блокирует модификации объекта cntr, увеличивая счетчик cntr::lock. RW-итераторы, порожденные от node, формируют кольцевой список для автоматической проверки и коррекции их позиций при вставке и вырезке элементов экземпляра cntr. Попытка вырезки итерируемого фрагмента списка приводит к явному аварийному завершению работы, чем обеспечивается надежность итерирования:

node itrs; // Головной элемент кольцевого списка RW-итераторов.

mutable uint lock; // Счетчик блокировок модификаций. uint len; // Число хранимых элементов.

elem *h,*t; // Граничные элементы («до первого» и «за последним»).

typedef lst::_cut_p _cut_p; // Поддержка «виртуального» конструирования typedef lst::_cut_f _cut_f; // lst для потомков и RW-итераторов. typedef lst::_cut_to_f _cut_to_f; //

cntr() : node() < init(); >// Головной элемент кольцевого списка. cntr(const cntr &n) : node(n) < init(); >// Элемент списка перед n. public:

class __itr; friend class __itr; // База наследования итераторов.

Дополнительным преимуществом проектирования структур данных контейнера на едином основании является возможность выделения общих свойств и методов константных и неконстантных итераторов списка и индексной таблицы в корне иерархии наследования — классе cntr::__itr:

friend class cntr; protected:

elem *c; // Текущий элемент.

cntr *r; // Итерируемая структура данных.

mutable uint cp; // Текущая позиция.

__itr(const cntr &l) < *this=l; >// К элементу h.

__itr(const __itr &m) < *this=m; >// К элементу m.c.

void operator=(const cntr &l) < c=l.h;r=(cntr*)&l;cp=0; >void operator=(const __itr &m)

3.5. Список элементов контейнера list. Функциональное содержание индексируемого итерируемого двусвязного линейного списка, реализованное в классе list, гарантирует автоматическую реиндексацию таблиц своих элементов и правку позиций RW-итераторов в методах вставки и вырезки. Контейнер list определяет собственные итераторы через общую базу list::_itr, дополняющую возможности cntr::__itr методами инкремента, смещения и т. п. Контроль типов хранимых элементов обеспечивается на уровне шаблона List с открытыми операторами присваивания и вставки:

class _itr; friend class _itr; // База наследования итераторов.

void init(uint sz); // Разместить и связать элементы h и t размером sz.

static void _cut(lst *out,list *l); // Вырезать все элементы.

list &operator=(const lst &l)

list &operator<<(elem *e); // Вставка в конец списка.

list &operator<<(const lst &l); // Присвоить содержимое l. public:

class citr; friend class citr; // Декларация RO-итератора.

class itr; friend class itr; // Декларация RW-итератора.

list(uint sz=sizeof(elem)) : cntr()

list(const lst &l,uint sz=sizeof(elem)); // Заимствовать элементы l.

list(); // Деструкция элементов.

lst cut() < return lst((_cut_f*)_cut, (_cut_p*)this); >// Вырезать. list &del(); // Вырезав, уничтожить содержимое.

Неконстантный итератор list::itr определяет операторы вставки за текущий элемент и ряд методов «виртуального» конструирования хранилищ вырезок lst:

class list::itr : private node, private _itr

itr(const itr &m) : node(m), _itr(m) < >// при создании

itr &operator=(list &l); // и смене контейнера.

itr() < >// Извлечение из списка итераторов.

3.6. Индексная таблица списка контейнера idx. Перечислим возможные варианты реализации индексной таблицы, поддерживающие дублирование ключей:

• популярные при проектировании ассоциативных контейнеров структуры данных: красно-черное дерево [1] и список с пропусками [3], используемые разработчиками библиотек STL (std::multimap) и Qt (QMultiMap) соответственно [11, 12], гарантирующие вставку и поиск с логарифмическими затратами времени в худшем случае;

• сплошной упорядоченный массив с бинарным поиском объектов: при логарифмическом порядке роста временных издержек поиска в худшем случае время вставки будет меняться линейно: сортировка потребует перемещения элементов вправо.

Отказ от применения хеш-таблиц мотивируется, во-первых, принципиальной невозможностью представления ключей в отсортированном виде с сохранением эффективности выполнения словарных операций и, во-вторых, высокими издержками обращения с составным ключом. Рассмотрим пример поиска записи в таблице по ключу, образованному строковыми значениями нескольких полей. В этом случае для использования хеш-функции от строкового ключа, поставляемой с реализацией хеш-таблицы, необходима конкатенация значений данных полей с неизбежным обращением к динамической памяти для создания и уничтожения буфера результирующей строки. Альтернативой объединению строк является дооснащение реализации собственными качественными хеш-функциями генерации индекса для каждой комбинации полей ключа поиска.

Основанием выбора сплошного массива служит его превосходство по результатам теста быстродействия операции поиска, приведенным в п. 4. Здесь же назовем ряд факторов, обеспечивающих этот результат:

• возможность хранения индекса последнего найденного элемента в качестве начальной позиции повторного поиска;

• меньшее по отношению к древовидным структурам число операций сравнения в худшем случае, равное |_log2(n)J +1 [2];

• локализованное размещение как самого массива, так и объектов списка, находящихся близко друг к другу в виду малой фрагментированности кучи, позволяющее более эффективно использовать кэш процессора. В то же время издержки операции разыменования указателей на служебные объекты («узлы») древовидной структуры, расположенные на страницах памяти разреженно, при интенсивном поиске оказываются весьма высокими.

Отметим принципиальные особенности разработанной индексной таблицы. Класс idx включает массив указателей на элементы контейнера. Крайние элементы массива хранят указатели на граничные элементы списка. Состав и очередность указателей в массиве определяются согласно заданным условиям фильтрации и сортировки. Наборы элементов с равными ключами образуют в массиве группы дубликатов.

Положение элемента контейнера в индексной таблице вычисляет функция бинарного поиска с непосредственной передачей ключа поиска. Функция возвращает позицию первого найденного элемента списка с заданным ключом, кэшируя ее в поле idx::found, либо 0, если поиск оказался неуспешным. В случае же неудачного поиска в found записывается индекс элемента с ближайшим снизу ключом. В дальнейшем значение found используется как начальная позиция бинарного поиска.

Таблицы idx, имея предком класс node, при создании связываются в кольцевую структуру для обновления в обработчиках модификации списка элементов контейнера. Наследование idx от cntr обеспечивает поддержку константных и неконстантных итераторов произведением их от общей базы cntr::__itr, делает возможным

применение механизма блокировки на время реиндексации и константного итерирования, предоставляет доступ к «виртуальным» конструкторам промежуточных хранилищ lst. Процедура вырезки из таблицы подразумевает формирование связанной последовательности извлекаемых элементов основного списка в заданном таблицей порядке:

class idx : private cntr

. // Доступ к «виртуальным» конструкторам lst.

list *r; // Основной список контейнера.

elem **tbl; // Упорядоченный массив указателей на элементы контейнера. mutable uint found; // Кэшируемый индекс найденного элемента. class _itr; friend class _itr; // База наследования итераторов

// Методы сортировки и фильтрации.

virtual int _cmp(const key &k,const elem *e) const = 0; virtual int _filter(const elem *e) const = 0;

uint seek(const key& k) const; // Функция бинарного поиска. // Обновить таблицу при модификации основного списка: void insx(elem *p,elem *n); // вставить

void cutx(elem *p,elem *n); // удалить последовательность (p,n).

// Методы вырезки. // static void __cut(lst *out,idx *x,uint start,uint end);

static void _cut (lst *out,idx *x)

class citr; friend class citr; // RO-итератор : private _itr. class itr; friend class itr; // RW-итератор : private node,

3.7. Средства сортировки и фильтрации. В теле функции бинарного поиска вызывается метод сравнения аргумента с содержащимся в элементе контейнера ключом. Поскольку способ извлечения ключа из элемента на этом уровне абстракции не задан, метод сравнения idx::_cmp является чисто виртуальным:

Проверка адекватности условию фильтрации выполняется при обработке добавления элементов в основной список чисто виртуальным методом idx::_filter:

if (!_filter(i)) continue; // Анализ выполнения условия.

. // Поиск позиции для вставки в таблицу.

Конкретное содержание абстрактные члены получают в составе шаблона Idx, которому при создании кроме типа элемента контейнера сообщаются тип ключа поиска, а также типы функциональных классов, устанавливающих методику сравнения двух ключей, правило извлечения ключа из элемента контейнера и критерий фильтрации:

template <class Elem,class Key,class Cmp,class Extr,class Filter> class Idx : public idx

Проиллюстрируем работу средств сортировки и фильтрации:

struct Attribute : public elem < // Сущность для хранения.

Attribute(const SString &name,int val): _name(name), _value(val) < >SString _name;

int _value; // Значение - целое, методы смены типа опущены.

defExtractor(AttrKey,const SubString&,subString(e._name); // Строковый ключ. defComparer(AttrCmp,compare(k1, k2)); // Сравнить ключи лексикографически. defFilter(AttrFilter,e._value >5); // Значение > 5. typedef Idx<Attribute, SubString, AttrCmp, AttrKey, AttrFilter> AttrTab;

int main(int argc, char** argv)