Increase the temporal efficiency of data structures in memory based on adaptation
Scientific concept of time’s efficiency of data structures was proposed. Methods of determining parameters of appropriate properties of data structures were developed. The method of synthesis of adaptive data structures in memory has been proposed. The physical imple-mentations of data structures ha...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2015
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/71 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-71 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/6a/0c28dc45f7b75ea45a9d15ad79dafe6a.pdf |
| spelling |
pp_isofts_kiev_ua-article-712018-09-18T13:51:29Z Increase the temporal efficiency of data structures in memory based on adaptation Повышение временной эффективности структур данных в оперативной памяти на основе адаптации Підвищення тимчасової ефективності структур даних у оперативній пам'яті на основі адаптації Shinkarenko, V.I. Zabula, G.V. UDC 004.05+004.416.3+004.422.63 УДК 004.05+004.416.3+004.422.63 УДК 004.05+004.416.3+004.422.63 Scientific concept of time’s efficiency of data structures was proposed. Methods of determining parameters of appropriate properties of data structures were developed. The method of synthesis of adaptive data structures in memory has been proposed. The physical imple-mentations of data structures have been adapted with respect to the software, hardware and operations with the data. Tools tailored for syn-thesis of data structures for virtual machines were developed. They substantially increase data structures time's efficiency in solving problems of distributed computing in heterogeneous computing networks. The main results are confirmed through computer experiments. Сформулировано понятие временной эффективности структур данных. Разработаны методы определения показателей соответст-вующего свойства структур данных. Предложен метод адаптивного синтеза структур данных в оперативной памяти. Физическая реализация структур данных адаптируется к программно-аппаратной среде эксплуатации и особенностям использования данных. Разработаны инструментальные средства синтеза адаптированных структур данных для виртуальных машин. Они позволяют су-щественно повысить временную эффективность структур данных при решении задач распределенных вычислений в гетероген-ных вычислительных сетях. Основные результаты подтверждаются выполненным компьютерным экспериментом. Сформулировано поняття тимчасової ефективності структур даних. Розроблені методи визначення показників відповідної властивості структур даних. Запропонована методика адаптивного синтезу структур даних у оперативній пам'яті. Фізична реалізація структур даних адаптується до програмно-технічного середовища експлуатації та особливостей використання даних. Розроблені інструментальні засоби синтезу адаптованих структур даних для віртуальних машин. Вони дозволяють істотно підвищити часову ефективність структур даних при вирішенні задач розподілених обчислень у гетерогенних обчислювальних сетях. Основні результати підтверджуються виконаними комп'ютерними експериментами. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2015-09-10 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/71 PROBLEMS IN PROGRAMMING; No 2-3 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2012) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/71/73 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-09-18T13:51:29Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
UDC 004.05+004.416.3+004.422.63 |
| spellingShingle |
UDC 004.05+004.416.3+004.422.63 Shinkarenko, V.I. Zabula, G.V. Increase the temporal efficiency of data structures in memory based on adaptation |
| topic_facet |
UDC 004.05+004.416.3+004.422.63 УДК 004.05+004.416.3+004.422.63 УДК 004.05+004.416.3+004.422.63 |
| format |
Article |
| author |
Shinkarenko, V.I. Zabula, G.V. |
| author_facet |
Shinkarenko, V.I. Zabula, G.V. |
| author_sort |
Shinkarenko, V.I. |
| title |
Increase the temporal efficiency of data structures in memory based on adaptation |
| title_short |
Increase the temporal efficiency of data structures in memory based on adaptation |
| title_full |
Increase the temporal efficiency of data structures in memory based on adaptation |
| title_fullStr |
Increase the temporal efficiency of data structures in memory based on adaptation |
| title_full_unstemmed |
Increase the temporal efficiency of data structures in memory based on adaptation |
| title_sort |
increase the temporal efficiency of data structures in memory based on adaptation |
| title_alt |
Повышение временной эффективности структур данных в оперативной памяти на основе адаптации Підвищення тимчасової ефективності структур даних у оперативній пам'яті на основі адаптації |
| description |
Scientific concept of time’s efficiency of data structures was proposed. Methods of determining parameters of appropriate properties of data structures were developed. The method of synthesis of adaptive data structures in memory has been proposed. The physical imple-mentations of data structures have been adapted with respect to the software, hardware and operations with the data. Tools tailored for syn-thesis of data structures for virtual machines were developed. They substantially increase data structures time's efficiency in solving problems of distributed computing in heterogeneous computing networks. The main results are confirmed through computer experiments. |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2015 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/71 |
| work_keys_str_mv |
AT shinkarenkovi increasethetemporalefficiencyofdatastructuresinmemorybasedonadaptation AT zabulagv increasethetemporalefficiencyofdatastructuresinmemorybasedonadaptation AT shinkarenkovi povyšenievremennojéffektivnostistrukturdannyhvoperativnojpamâtinaosnoveadaptacii AT zabulagv povyšenievremennojéffektivnostistrukturdannyhvoperativnojpamâtinaosnoveadaptacii AT shinkarenkovi pídviŝennâtimčasovoíefektivnostístrukturdanihuoperativníjpamâtínaosnovíadaptacíí AT zabulagv pídviŝennâtimčasovoíefektivnostístrukturdanihuoperativníjpamâtínaosnovíadaptacíí |
| first_indexed |
2025-07-17T09:53:25Z |
| last_indexed |
2025-07-17T09:53:25Z |
| _version_ |
1850410799205449728 |
| fulltext |
Формальні методи програмування
УДК 004.05+004.416.3+004.422.63
ПОВЫШЕНИЕ ВРЕМЕННОЙ ЭФФЕКТИВНОСТИ СТРУКТУР
ДАННЫХ В ОПЕРАТИВНОЙ ПАМЯТИ НА ОСНОВЕ АДАПТАЦИИ
В.И. Шинкаренко, Г.В. Забула
Днепропетровский национальный университет железнодорожного транспорта
им. академика В. Лазаряна 49010, Днепропетровск, ул. академика Лазаряна, 2
e-mail: ccp@diit-70.dp.ua
Сформулировано понятие временной эффективности структур данных. Разработаны методы определения показателей соответст-
вующего свойства структур данных. Предложен метод адаптивного синтеза структур данных в оперативной памяти. Физическая
реализация структур данных адаптируется к программно-аппаратной среде эксплуатации и особенностям использования данных.
Разработаны инструментальные средства синтеза адаптированных структур данных для виртуальных машин. Они позволяют су-
щественно повысить временную эффективность структур данных при решении задач распределенных вычислений в гетероген-
ных вычислительных сетях. Основные результаты подтверждаются выполненным компьютерным экспериментом.
Scientific concept of time’s efficiency of data structures was proposed. Methods of determining parameters of appropriate properties of
data structures were developed. The method of synthesis of adaptive data structures in memory has been proposed. The physical imple-
mentations of data structures have been adapted with respect to the software, hardware and operations with the data. Tools tailored for syn-
thesis of data structures for virtual machines were developed. They substantially increase data structures time's efficiency in solving
problems of distributed computing in heterogeneous computing networks. The main results are confirmed through computer experiments.
Введение
При решении задач связанных с обработкой больших объемов данных и необходимостью хранения зна-
чительной их части в оперативной памяти, с повышенными требованиями к временной эффективности огром-
ное значение имеет насколько эффективным по временным характеристикам является эксплуатируемое ПО. В
частности, это касается задачи распределенных вычислений в гетерогенных программно-аппаратных средах.
В таких случаях необходимо особое внимание обратить на разработку эффективных алгоритмов и эф-
фективных структур данных. И хотя существует множество методов и способов адаптации и оптимизации ал-
горитмов к конкретным программно-аппаратным средам, однако они не оптимизируют, не адаптируют и не
изменяют заданные в программе структуры данных [1]. Практика программирования указывает на то, что про-
граммисты решают задачу проектирования структур данных в значительной степени интуитивно, на основе
опыта либо общих соображений.
Целью работы является разработка методологии структурной адаптации данных, а также создание со-
ответствующего инструментального обеспечения. В ней рассматриваются возможности автоматизированного
проектирования структур данных на физическом уровне с улучшенной временной эффективностью.
Учитывая это необходимо решить следующие задачи: разработать метод синтеза адаптированных в
процессе эксплуатации структур данных с улучшенными временными характеристиками, совершенствовать
технологию их проектирования, реализации и эксплуатации. Решение этих задач подразумевает необходимость
разработки показателей временных характеристик структур данных, а также определиться, что считать време-
нем обработки структур данных.
Жизненный цикл структур данных
Жизненный цикл структур данных неразрывно связан с жизненным циклом программных систем [2],
составной частью которых они являются.
Рассмотрим традиционные этапы жизненного цикла структур данных и предлагаемые модификации с
целью улучшения их эксплуатационных характеристик.
Этап анализа данных можно отождествить с проектированием данных на абстрактном уровне [3, 4]. На
этом уровне определяют физическую сущность данных (семантику), связи между элементами на уровне пред-
ставления пользователя и операции над данными, абстрагируясь от структур данных и их реализаций.
Результатом проектирования являются спецификации данных. Порядок разработки регламентирован-
ных спецификаций и анализа абстрактных данных представлен в [3]. Абстрактные спецификации учитывают
только внешние аспекты представления данных.
Этап проектирования структур данных может включать проектирование логической структуры дан-
ных. Результатом проектирования является разработанная и обоснованная логическая организация данных
(концептуальная модель). Проектирование выполняется на основе, выработанных на этом этапе, требований по
эффективности [3], безопасности, ограничениям [5] и др. Логическая организация данных должна органично
сочетаться с алгоритмами и способствовать упрощению процесса проектирования и разработки программных
средств.
Методология проектирования данных на различных носителях и для различных способов использова-
ния существенно различается. Проектирование данных в оперативной памяти (ОП) основывается на выборе из
211
©В.И. Шинкоренко, Г.В. Забула, 2012
ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний випуск
Формальні методи програмування
базовых структур данных, либо конструировании других композиционных структур на основе базовых. Базо-
выми являются хорошо известные массивы, списки, деревья и т. п., множества на основе хеш-функций и др.,
которые широко представлены и исследованы в [4, 6–9]. Конструирование выполняется путем следования или
включения базовых структур друг в друга.
Этап реализации структур данных [10] предусматривает представление концептуальной модели средст-
вами и в терминах среды разработки. Для данных в ОП это среда программирования [10], структуры данных и
операции над ними определяют средствами языка программирования с учетом его возможностей и ограничений.
На этапе эксплуатации или сопровождения программных систем проявляются эксплуатационные ха-
рактеристики структур данных. Последние определяются представлением структур данных на физическом
уровне [5, 10], т. е. порядком размещение данных на носителях информации и организацией связей между эле-
ментами структур. Представление структур данных на физическом уровне в ОП для динамических данных
определяется порядком выделения и утилизации памяти, для массивов – порядком размещения элементов (по
строкам или столбцам).
Реализация структур данных в ОП, в большинстве случаев, предопределена средствами разработки
программных систем, в частности, трансляторами. И лишь иногда предъявленные повышенные требования к
эффективности вынуждают на этапе проектирования разрабатывать проект структур данных на физических
носителях.
Результатом проектирования является схема размещения данных на носителях, включая вспомогатель-
ные данные, такие как адреса, индексы и т. п., а также порядок доступа к элементам данных.
Каждый этап жизненного цикла подразумевает проектирование соответствующих операций обработ-
ки данных. На абстрактом уровне определены все операции над данными, которые представлены в виде специ-
фикаций соответствующих процедур и функций. Например, для абстрактных данных "множество вагонов на
станции" такими операциями могут быть поступление вагона на станцию, поступление группы вагонов, опре-
деление наличия вагона на станции и т. п.
На этапе проектирования – это операции над структурированными данными. Например, если для "мно-
жества вагонов на станции" принята структура в виде массива записей, то операциями будут – добавление эле-
мента в массив записей, добавления списка элементов в массив записей, поиск элемента и т. п.
На уровне реализации операции определяются соответствующими методами (процедурами), разрабо-
танными средствами среды разработки (языка программирования) на основе их базовых операций, таких как
присваивание, сравнение, сложение и т. п. На физическом уровне операции представлены машинными коман-
дами процессора, контроллера и т. п.
Предлагаемая в работе методика изменяет жизненный цикл структур данных (табл. 1).
Таблица 1. Особенности предлагаемого подхода в сравнении с традиционным
Модели и реализации структур данных Этап жизненного
цикла Традиционная технология Предлагаемая технология с адаптацией
структур данных на физическом уровне
Анализ Спецификации структур данных и операций
обработки данных
Спецификации структур данных и опера-
ций обработки данных
Проектирование Логические модели на основе выбора базовых
структур или конструирования на их основе
Концептуальная модель: элементы данных,
логические связи, ограничения
Реализация Структуры данных и операции над ними
терминами средств разработки (языков про-
граммирования)
Отсутствует (при наличии специализиро-
ванных инструментальных средств)
Эксплуатация или
сопровождение
Данные на физических носителях Данные на физических носителях с повы-
шенной временной эффективностью сово-
купности операций их обработки
Временная эффективность структур данных
Структуры данных не обладают функциональностью, поэтому говорить об их временных характери-
стиках в этом смысле некорректно. Однако физическая реализация структур данных может в значительной
степени влиять на временную эффективность программ и программных систем, использующих структуриро-
ванные данные. В работах [1, 11] показано, что время операции доступа к позиции в зависимости от физическо-
го размещения данных в ОП может отличаться на два порядка.
Под временной эффективностью структур данных будем понимать временную эффективность сово-
купности операций (алгоритмов) обработки данных.
Уточним, что понимается под операциями обработки данных. В соответствии с современными прин-
ципами программирования обработка данных выполняется на основе атомарных или примитивных операций
обработки. Все примитивные операции обработки структур данных можно классифицировать как:
− операции не связанные с изменением структуры и значений ее элементов. Такие операции должны
быть ограничены исключительно выборкой или поиском значений и исключать другую функциональность,
такую как, например, определение средних значений по выборке и т. п.;
212
Формальні методи програмування
− операции связанные с преобразованием структуры данных в том числе:
− изменение логической структуры (например, замена массива списком, уравновешивание дерева);
− добавление/удаление элемента (ов);
− операции связанные с изменением значений ее элементов без изменения структуры. Такие опе-
рации должны быть ограничены исключительно поиском (при необходимости) позиции и заменой значения и
исключать преобразование данных;
− операции связанные с изменением значений ее элементов и связанной с этим изменением струк-
туры. Например, добавление элемента в упорядоченный список.
Использование структур данных некоторым конкретным приложением можно представить в виде алго-
ритма (нотация [12]):
)||(| ∏ ⋅=
i
Y
Xi
Y
Xi
Y
X
i
i
i
i
CBA ,
где – алгоритмы обработки исследуемой структуры данных (согласно вышеприведенной классификацией),
– алгоритмы преобразования данных и обработки других данных и структур,
iB
iC X и – их области опреде-
ления и значения, соответственно. Часть алгоритмов могут быть пустыми.
Y
iC
Тогда временную эффективность структуры данных можно определить на основе временной эффек-
тивности алгоритмов вида:
∏=
i
Y
Xi
Y
X
i
i
|B|A . (1)
Для сравнения временной эффективности двух алгоритмов можно воспользоваться показателем степе-
ни превосходства одного (i-го) алгоритма над другим (j-тым) на ограниченных подмножествах ×⊆=Ω )VV(( *
))()()()( **** ℜ⊆ℜ×Ψ⊆Ψ×⊆×⊆ XXUU [13]:
∑∑∑∑∑
∈ ∈ ∈ Ψ∈ ℜ∈
−
=ℜΨ
Vv Uu Xx r ji
ij
ij rxuvtrxuvt
rxuvtrxuvt
N
XUVSUP
ψ ψψ
ψψ
,
)),,,,(),,,,,((max
),,,,(),,,,(1,,,,
где – множество возможных значений объема данных, – множество возможных типов данных, *V *U *X –
множество возможных значений данных, – множество возможных программных сред, – множество
архитектур ЭВМ, на которых возможна реализация алгоритмов.
*Ψ *ℜ
С учетом размещения и эксплуатации структуры данных в конкретной программно-аппаратной среде и
фиксированных типов данных ее элементов:
∑∑
∈ ∈
−
=
Vv Xx ji
ij
ij xvtxvt
xvtxvt
N
XVSUP
)),(),,((max
),,(),(1, .
Воспользуемся предложенным там же [13] методом оценки этого показателя, самой оценкой и оценкой
ее доверительного интервала. S-оценка степени превосходства i-го алгоритма над j-м на основании N выпол-
нений алгоритмов в области Ω :
∑
=
⋅
−
=
N
k jkik
ikjk
ij xvtxvt
xvtxvt
N
XVS
1
%100
)),(),,((max
),,(),(1, , (2)
где ikt – время выполнения i-го алгоритма при k-й реализации в области Ω .
Аналогично, показатель области превосходства [13] i-го алгоритма над j-м:
⎩
⎨
⎧
≤
>
=⋅−= ∑
= 0если,0
0если,1
)(,%100)),,(),((1,
1 a
a
asignxvtxvtsign
N
XVR
N
k
ikjkij . (3)
Оценка степени превосходства и области превосходства i-й структуры данных над j-й по критерию
временной эффективности выполняется в области ))()()(( **** AAXXVV ⊆×⊆×⊆==Ω , в которой различие
объема и значений данных определяется различным состоянием структуры данных перед и в процессе выпол-
нения различных алгоритмов . Y
X|A
Для измерения ikt и jkt необходимо моделирование среды эксплуатации структуры данных. Естествен-
но, лучшим вариантом является выполнение замеров в той же программно-аппаратной среде, где структура экс-
плуатируется (ЭВМ, ОС, совместно выполняемые прикладные программы). Остается моделировать лишь процесс
работы со структурой, то есть алгоритм . И здесь возможны варианты. Y
X|A
213
Формальні методи програмування
Первый подход заключается в следующем. Пусть заранее известно количественное соотношение опе-
раций обработки структур данных, заданное вектором:
, (4) ][ 21 m
T n,,n,n K=N
где – ориентировочное количество выполнений i -ой базовой операции обработки структур данных в кон-
кретной среде эксплуатации, m – количество разнотипных операций обработки данных. Тогда можно
представить как
in
Y
X|A
(5) p
p
Y
Xp
m
p
p
Y
X |Bn|A ⋅=∏
=1
и, исходя из (2) и (4), ikt можно определить как:
∑
=
=
m
p
ikppik t~n
m
t
1
1 , (6)
где ikpt~ – время выполнения p -ой базовой операции обработки структур данных операции при k-й реализации
при эксплуатации i-й структуры.
При таком подходе необходимо выполнить множество замеров времени выполнения базовых алгорит-
мов обработки структур данных.
Однако следует учитываь, что время зависит не только от V и X, а и от последовательности выпол-
нения операций . Например, порядок выполнения операций добавления и удаления элементов в/из стека
может быть достаточно существенным. Результат (и время) добавления трех элементов в пустой стек и затем
удаление из него двух элементов будет отличным, чем при удалении двух элементов из пустого стека, а затем
добавления трех.
ikpt~
p
p
Y
Xp |B
Второй и последующий подходы основываются на моделировании алгоритма по (1), что в отмеченном
смысле предпочтительнее, чем по (5). Моделируемую последовательность операции обработки данных назовем
сценарием работы со структурой данных (или просто сценарием).
При втором подходе предлагается такой способ формирования сценария. Заданы ориентировочные гра-
ницы количества операций обработки структур данных ( in – нижняя, in – верхняя граница ожидаемого коли-
чества выполнений i -ой базовой операции обработки структур данных):
]),(,,),(,),[( 2211 mm
T nnnnnn K=N .
Для конкретного сценария случайным образом (применяя равномерный закон распределения) опреде-
ляется количество повторений каждой базовой операции в пределах заданных границ. Последовательность
операций строится случайным образом в соответствии с частотой их использования . При этом ∑
=
m
k
ki n/n
1
b
ik
e
ikik ttt −= , (7)
где , – начальное и конечное время выполнения k-го сценария при обработке i-й структуры. b
ikt e
ikt
Другие подходы формирования сценария:
− произвольные сценарии формируются пользователем, с использованием соответствующего интер-
фейса. В этом случае можно учитывать особенности работы со структурами данных;
− сценарий строиться автоматически при наличии средств отслеживания операций обработки структур
данных в процессе их эксплуатации (фиксация истории работы со структурой данных).
Применение этих подходов (как и второго) предполагает оценку временной эффективности структур
данных по (2) и (7).
Особенности проектирования логической структуры данных
Концептуальная модель логической структуры данных должна отображать составляющие, их свойства
и связи между составляющими.
На рисунке показан пример такой модели. Данное представление основано на известных средствах ER-
диаграмм [14] и представляют собой модифицированные ER- диаграммы нагруженные атрибутами – MERA-
диаграммы.
В качестве составляющих (обозначены в виде прямоугольников) могут быть элементарные, неделимые
неструктурированные данные, а также части структур (подструктуры).
Составляющие структуры определяется одним из отношений MERA- диаграмм (обозначены ромбом):
214
Формальні методи програмування
− упорядоченная последовательность однородных, однотипных элементов или подструктур. Примеры
таких структур: массивы, хеш-таблицы;
− неупорядоченная последовательность разнотипных элементов или подструктур, например, записей;
− варьируемый состав элементов или подструктур (записи с вариативной частью).
Имеется возможность задания свойств элементов, подструктур и связей в виде их атрибутов (на рисун-
ке – овалы). Атрибуты могут накладывать ограничения на значения элементов, их количество, связи между
значениями различных элементов, вычислимые значения элементов и т. п.
Рисунок. Фрагмент концептуальной модели логической структуры файла формата BMP
BMP файл
без файлового
заголовка
Разнотипные
Информационный
заголовок BMP
Данные
изображения
Разнотипные
Количество
битов на пиксель
Одно из
Однотипные
Индексированные
данные
Пикселизированные
данные
Тип: индекс
палитры(Байт)
Количество=256
Однотипные
Высота
изображения
Ширина
изображения
Тип: пиксель
(RGBQUAD)
Количество =
ширина изображения *
высота изображения
Ограничение:
если количество битов на
пиксель=8, то 1, иначе 0
10
Разнотипные
ПалитраИзображения
Тип: пиксель
(RGBQUAD)
Однотипные
Количество=
ширина изображения *
высота изображения
. . .
Таким образом, концептуальная модель отображает все особенности структуры данных, ее составляю-
щих и связей между ними, не привязываясь в то же время к порядку обработки данных и к традиционным при-
митивным логическим структурам данных.
Возможности размещения структур данных в оперативной памяти
Любая логическая структура может быть преобразована в разнообразные физические представления
(физические структуры). Физическая структура сохраняет семантические связи между элементами логической
структуры и добавляет связи связанные с размещением элементов на физическом носителе.
Возможности вариативности физических структур предопределяется следующим: однотипные связи
логической структуры могут быть физически реализованы в виде массива (последовательности ячеек). Если
массив двух и более размерностей, то вариативным является способ расположения строк и столбцов массива.
Кроме того, существуют варианты размещения нескольких массивов с чередованием элементов. Связь между
элементами неявно задается последовательной адресацией ячеек. Эта же логическая структура может быть
представлена в виде: одно-, двунаправленных списков, деревьев, графов и других динамических структур, в
которых элементы связаны явной адресацией. Поиск элементов в первом случае осуществляется вычислением
адреса элемента. Во втором случае происходит переход по адресам. Оба эти способа могут комбинироваться.
Например, расширяемые массивы без релокации данных. Массив с фиксированным количеством строк и
столбцов в случае необходимости увеличения кол-ва элементов может расширяться таким же массивом или
215
Формальні методи програмування
другой размерности в другом месте памяти, при этом строится динамическая последовательность массивов.
Второй пример: известные хеш-таблицы с различными методами разрешения коллизий. Одним из атрибутов
однотипной связи является количество и размерность, которые могут быть, как фиксированы, так и изменятся
во время работы программы.
В случае разнотипных связей данные могут размещаться в совершенно произвольных местах памяти.
Удачное проектирование физической структуры данных в оперативной памяти может в значительной
мере повысить временную эффективность в первую очередь по причине эффективного использования кэша
памяти. Размещение данных, использующихся почти одновременно, на одной или соседних линейках кэша
позволит снизить количество промахов кэша и ускорить обработку структур данных теоретически на один два
порядка. Так как операция доступа к данным в оперативной памяти может занимать порядка 100-300 тактов
процессора, а в кэш памяти – ноль тактов.
Процесс формирования физической структуры данных на основе логического представления заключа-
ется в следующем. На основе простых элементов: целое, вещественное, символ и т.п., применяя различные
примитивные структуры: массивы, списки, хеш-таблицы и т. п., формируется множество составных физических
структур данных. Все физические структуры данных имеют одинаковый интерфейс (одинаковые методы обра-
ботки данных), но различное физическое представления.
Инструментальные средства адаптации
В разработанных инструментальных средствах адаптации структур данных к программно-аппаратной
среде эксплуатации предусмотрена следующая функциональность:
− формирование концептуальной модели логической структуры данных;
− построение интерфейсов физических реализаций структур;
− обеспечение формирования и выполнения различных алгоритмов обработки структур данных (1);
− задание и использование данных и/или их особенностей используемых в качестве обучающей вы-
борки;
− выполнение адаптации, т. е. поиск структуры данных, обладающей повышенной временной эффек-
тивностью в данной программно-аппаратной среде эксплуатации.
Для формирования концептуальной модели логической структуры данных была использована freeware
программное обеспечение Dia [15]. Для подготовки модели использованы стандартные функциональные воз-
можности редактора диаграмм со следующими ограничениями:
− MERA диаграмма должна состоять только из объектов библиотеки ER пакета Dia;
− MERA диаграмма должна содержать только один главный элемент, все остальные элементы долж-
ны быть подчиненными ему;
− подчинение объектов обозначается с помощью отношений;
− отношения должны идентифицироваться как «разнотипные» или «однотипные»;
− количество подчиненных элементов для отношения «разнотипные» может быть не ограничено;
− количество подчиненных элементов для отношения «однотипные» должно быть равным одному;
− главный элемент отношения задается с помощью смены типа участия на «общий»;
− для создания поля в отношении «разнотипные», нужно создать сущность, имя которой будет отве-
чать имени поля. К этой сущности нужно добавить атрибут типа поля. Атрибут должен иметь имя «Тип: <тип>»,
где тип – один из следующих: dword, byte, string, float.
Для использования адаптированных структур данных из произвольной программы пользователя необ-
ходимо создание соответствующего интерфейса. Для доступа к структурам данных и их подструктурам приме-
няются автоматически формируемые классы. Для каждой сущности из концептуальной модели строится свой
класс, имя класса совпадает с именем сущности. Имена и параметры методов классов для однотипных данных
совпадают с соответствующими методами класса ICollection из .NET. А для разнотипных данных одинаковый
фиксированный интерфейс из двух методов для каждого поля: get_<имя_поля> и set_<имя_поля>.
Для построения интерфейсов, формирования физических структур данных и выполнения методов фи-
зической реализации используется рефлексия [16] и программные шаблоны. Рефлексия – способ метапрограм-
мирования, при котором программа знает свою структуру и имеет возможность изменить ее. Языки,
основанные на промежуточном коде, поддерживают работу с рефлексией. Программный шаблон – часть мета-
программы, которая создает программный код, для реализации той или иной примитивной структуры данных.
Реализация шаблонов осуществляется от обратного в несколько этапов:
− разрабатывается класс, который обеспечивает результат работы программного шаблона с одной из
физических реализаций структур данных;
− компилируется библиотека, которая содержит этот класс. Затем библиотека дизассемблируется,
чтобы получить IL-код;
− полученный код затем используется в реализации программного шаблона с помощью рефлексии.
Созданный с помощью программных шаблонов код впоследствии может быть сохранен в виде .NET
библиотеки и использоваться в дальнейшей разработке сторонних приложений.
Адаптация предполагает поиск предпочтительной по временной эффективности структуры данных.
Применяется метод случайного поиска на основе генетического алгоритма. [17]. Пользовательский интерфейс
программы позволяет изменять основные параметры генетического алгоритма, что при наличии опыта у поль-
216
Формальні методи програмування
зователя может способствовать сокращению временных затрат на адаптацию. Установленные на предваритель-
ных экспериментах параметры генетического алгоритма показывают достаточно высокую его временную эф-
фективность.
Реализация инструментальных средств выполнена на C#, в виду его возможности поддержки реф-
лексии.
Экспериментальные исследования
Целью эксперимента являлась апробация разработанных инструментальных средств и предвари-
тельная оценка возможностей адаптации. Выполнялась адаптация физической структуры данных в ОП из BMP-
файлов.
Экспериментальная база состояла с технической стороны из трех компьютеров, основные характери-
стики которых приведены в табл. 2. Информационная база состояла из 3037 файлов в формате BMP общим
объемом 2,1 Гб размером от 104 байт до 5,7 Мб.
Таблица 2. Технические характеристики компьютеров
ЭВМ Процессор
Кэш L1 кода
/ L1 данных /
L2, Кб
Тактовая частота/частота
системной шины /
частота памяти, МГц
Время доступа
к ОП: чтение /
запись, Мб/с
Операцион-
ная система
1C Intel Core 2 Duo E4600 32/32/2048 2 400 (12 * 200) / 800 /
400
5350 / 1962 Windows 7
Ultimate Prof
2C Intel Celeron G530 64/64/512 2 400 (24 * 100) / 100 /
532
6670 / 3220 Windows XP
Ultimate Prof
3C AMD Athlon 64× 2 3800
Dual Core
128/128/1024 2 000 (10 * 200) / 200 /
400
5400 / 1860 Windows XP
Prof
Согласно концептуальной модели было сгенерировано шесть классов с 5, 10, 4, 6, 6 и 4 методами.
Различные физические реализации структур данных формировались по хромосомам генетического
алгоритма. Сценарий обработки структур данных формировался случайным образом согласно заданным
ограничениям количества операций обработки. Были установлены следующие ограничения: для методов доба-
вить и удалить пиксель, определить текущее количество пикселей, найти пиксель в изображении класса
«данные изображения» 1000) (1000,),( =ii nn , для всех остальных методов 0) (0,),( =ii nn . Сценарии
выполнялись для случайно выбранного файла из информационной базы. Последовательность выполнения экс-
перимента такова:
− формирование сценария случайным образом;
− выбор файла из информационной базы;
− адаптация физической реализации логической структуры данных;
− формирование контрольных структур данных;
− измерение времени выполнения сценария на адаптированной и контрольных структурах данных;
− на основе полученных измерений вычислялись SR- оценки показателей временной эффективности.
В качестве контрольных использовались такие структуры: – размещение данных в ОП как в
файле, – размещение самого изображения как в файле, – структура на основе хеш-таблицы
(функции хеширования) и – случайным образом сформированная структура.
1STRUCT
2STRUCT 3STRUCT
4STRUCT
Выполнено 64 реализации эксперимента (адаптаций).
Оценка эффективности адаптированной структуры данных выполнялась по SR- показателям (2) и (3).
Найденные показатели и доверительные интервалы (с коэффициентом доверия 0,95) приведены в табл. 3.
Таблица 3. Сравнительные оценки временной эффективности адаптированной структуры данных
1STRUCT 2STRUCT 3STRUCT 4STRUCT
ЭВМ
S- оценка R- оценка S- оценка R- оценка S- оценка R- оценка S- оценка R- оценка
1C 16
4483+
− 100 16
4483+
− 100 19
05+
− 100 21
2167+
− 100
2C 11
1689+
− 100 11
1689+
− 100 1
01+− 100 33
4367+
− 100
3C 6
1193+
− 100 6
1193+
− 100 9
03+
− 100 20
6480+
− 100
Все 11
1288+
− 100 11
1288+
− 100 6
03+
− 100 14
1471+− 100
Как и следовало ожидать, адаптированная структура данных по временной эффективности превосходит
все контрольные и во всей области исследования. Показательной является степень превосходства на уровне
90 %, что соответствует разнице во времени выполнения сценария примерно в 10 раз.
217
Формальні методи програмування
Выводы
Выполненная работа позволяет повышать временную эффективность программных систем, эксплуа-
тируемых в гетерогенных компьютерных сетях, если предполагается обработка больших объемов данных и
выдвигаются повышенные требования к временным характеристикам. Однако разработанные инструменталь-
ные средства пока ограничены в функциональности и ориентированы на исследования, а не производство ПО.
Проект, связанный с автоматическим повышением эффективности структур данных, только открыва-
ет определенные перспективы. Можно отметить направления дальнейших исследований:
− оценка возможностей повышения временной эффективности структур данных при адаптации в
различных программно-аппаратных средах;
− разграничение возможностей адаптивного синтеза структур данных с необходимостью «ручно-
го» проектирования структур данных на физических носителях;
− выявление предпосылок проведения адаптации, когда временные затраты на адаптацию будут
меньше разницы во времени выполнения адаптированного и неадаптированного алгоритмов за определен-
ный срок эксплуатации;
− изучение возможностей повышения эффективности адаптации путем совершенствования (а воз-
можно и адаптации) генетического алгоритма.
1. Шинкаренко В. И. Экспериментальные исследования алгоритмов в программно-аппаратных средах : монография. – Днепропетровск:
Изд-во Днепропетр. нац. ун-та ж.-д. трансп. им. акад. В. Лазаряна, 2009. – 279 с.
2. Бабенко Л.П., Лавріщева К.М. Основи програмної інженерії: Навч. посіб. – К.: Т-во "Знання", КОО, 2001. – 269 с.
3. Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ. – М.: Мир, 1989. – 424 с.
4. Ахо А.В., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Изд. дом «Вильямс», 2001. – 384 с.
5. Конноли Т. Бегг К., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика. – М.: Издательский дом
"Вильямс", 2000. – 1120 с.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с.
7. Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах. – СПб.: ООО
"ДиасофтЮП", 2003. – 1136 с.
8. Кнут Д. Искусство программирования, том 1. Основные алгоритмы. – [3-е изд.]. – М.: Издательский дом "Вильямс", 2000. – 720 с.
9. Вирт Н. Алгоритмы + структуры данных = программа. – М.: Мир, 1985. – 406 с.
10. Зиглер К. Методы проектирования программных систем. – М.: Мир, 1985. – 328 с.
11. Шинкаренко В.И. Временная оценка операций обработки структурированных данных с учетом конвейеризации и кэширования //
Проблеми програмування. –2006 – № 2-3. – С. 43–52.
12. Шинкаренко В.И., Ильман В.М., Скалозуб В.В. Структурные модели алгоритмов в задачах прикладного программирования Часть I.
Формальные алгоритмические структуры // Кибернетика и системный анализ. – 2009 – № 3. – С. 3–14.
13. Шинкаренко В.И. Сравнительный анализ временной эффективности функционально эквивалентных алгоритмов // Проблемы про-
граммирования. – 2001. – № 3-4. – С. 31–39.
14. Чен П. The Entity-Relationship Model – Toward a Unified View of Data (англ.) // ACM Transactions on Database Systems (TODS) . –Нью-
Йорк: ACM, 1976. –V. 1. – P. 9–36.
15. Dia – GNOME Live! – http://live.gnome.org/Dia.
16. Шилдт Г. C# 4.0: полное руководство.– М.: Вильямс, 2010. – 1056 с.
17. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. – 2-е изд. – М: Физматлит, 2006. – 320 с.
218
http://ru.wikipedia.org/w/index.php?title=%D0%A7%D0%B5%D0%BD,_%D0%9F%D0%B8%D1%82%D0%B5%D1%80&action=edit&redlink=1
http://portal.acm.org/ft_gateway.cfm?id=320440&type=pdf&coll=GUIDE&dl=GUIDE&CFID=72010946&CFTOKEN=54542835
http://www.acm.org/publications
http://live.gnome.org/Dia
http://ru.wikipedia.org/w/index.php?title=%D0%92%D0%B8%D0%BB%D1%8C%D1%8F%D0%BC%D1%81_%28%D0%B8%D0%B7%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE%29&action=edit&redlink=1
Введение
Жизненный цикл структур данных
Временная эффективность структур данных
Особенности проектирования логической структуры данных
Возможности размещения структур данных в оперативной памяти
Инструментальные средства адаптации
Экспериментальные исследования
Выводы
|