Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде
Описывается усовершенствованный алгоритм произвольно-последовательной обработки упорядоченного файла. Приводятся результаты имитационного моделирования алгоритма и сравнительные оценки его быстродействия в однородной запоминающей среде....
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2009
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/46905 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2009. — № 1. — С. 138–143. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-46905 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-469052013-07-08T03:05:28Z Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. Моделювання і управління великими системами Описывается усовершенствованный алгоритм произвольно-последовательной обработки упорядоченного файла. Приводятся результаты имитационного моделирования алгоритма и сравнительные оценки его быстродействия в однородной запоминающей среде. Описується удосконалений алгоритм довільно-послідовної обробки упорядкованого файла. Приводяться результати імітаційного моделювання алгоритму і порівняльні оцінки його швидкодії в однорідному запам’ятовуючому середовищі. It is described the advanced algorithm of the direct-sequential processing of an ordered file. The results of the imitation modeling the algorithm and comparative estimations of its speed of response in homogeneous memory are given. 2009 Article Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2009. — № 1. — С. 138–143. — Бібліогр.: 3 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/46905 681.3.06 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде Математичні машини і системи |
| description |
Описывается усовершенствованный алгоритм произвольно-последовательной обработки упорядоченного файла. Приводятся результаты имитационного моделирования алгоритма и сравнительные оценки его быстродействия в однородной запоминающей среде. |
| format |
Article |
| author |
Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. |
| author_facet |
Литвинов, В.А. Майстренко, С.Я. Ходак, В.И. |
| author_sort |
Литвинов, В.А. |
| title |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| title_short |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| title_full |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| title_fullStr |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| title_full_unstemmed |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| title_sort |
имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2009 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/46905 |
| citation_txt |
Имитационное моделирование алгоритма произвольно-последовательной обработки файлов в однородной запоминающей среде / В.А. Литвинов, С.Я. Майстренко, В.И. Ходак // Мат. машини і системи. — 2009. — № 1. — С. 138–143. — Бібліогр.: 3 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT litvinovva imitacionnoemodelirovaniealgoritmaproizvolʹnoposledovatelʹnojobrabotkifajlovvodnorodnojzapominaûŝejsrede AT majstrenkosâ imitacionnoemodelirovaniealgoritmaproizvolʹnoposledovatelʹnojobrabotkifajlovvodnorodnojzapominaûŝejsrede AT hodakvi imitacionnoemodelirovaniealgoritmaproizvolʹnoposledovatelʹnojobrabotkifajlovvodnorodnojzapominaûŝejsrede |
| first_indexed |
2025-07-04T06:26:27Z |
| last_indexed |
2025-07-04T06:26:27Z |
| _version_ |
1836696614168690688 |
| fulltext |
138 © Литвинов В.А., Майстренко С.Я., Ходак В.И., 2009
ISSN 1028-9763. Математичні машини і системи, 2009, № 1
УДК 681.3.06
В.А. ЛИТВИНОВ, С.Я. МАЙСТРЕНКО, В.И. ХОДАК
ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ АЛГОРИТМА ПРОИЗВОЛЬНО-
ПОСЛЕДОВАТЕЛЬНОЙ ОБРАБОТКИ ФАЙЛОВ В ОДНОРОДНОЙ
ЗАПОМИНАЮЩЕЙ СРЕДЕ
Abstract: It is described the advanced algorithm of the direct-sequential processing of an ordered file. The results of
the imitation modeling the algorithm and comparative estimations of its speed of response in homogeneous memory
are given.
Key words: file processing, key search, imitation modeling.
Анотація: Описується удосконалений алгоритм довільно-послідовної обробки упорядкованого файла.
Приводяться результати імітаційного моделювання алгоритму і порівняльні оцінки його швидкодії в
однорідному запам’ятовуючому середовищі.
Ключові слова: обробка файлів, пошук по ключу, імітаційне моделювання.
Аннотация: Описывается усовершенствованный алгоритм произвольно-последовательной обработки
упорядоченного файла. Приводятся результаты имитационного моделирования алгоритма и
сравнительные оценки его быстродействия в однородной запоминающей среде.
Ключевые слова: обработка файлов, поиск по ключу, имитационное моделирование.
1. Введение
Для повышения эффективности (скорости) обработки последовательного упорядоченного файла,
расположенного во внешней памяти, в [1] был предложен алгоритм произвольно-последовательной
обработки (ППО), значительно ускоряющий процесс поиска-выборки элементов файла по
сравнению как с дихотомическим поиском, так и чисто последовательной обработкой. Сокращение
времени поиска-выборки в рассматриваемом случае обусловлено уменьшением количества
обращений к файлу (в определенной области значений параметров процесса до 2х – 3х раз).
В современных компьютерах оперативная память позволяет хранить и обрабатывать
файлы очень большого объема, на порядок уменьшилось и время доступа к внешней памяти на
жестких магнитных дисках. В этих условиях пренебрежение затратами времени на выполнение
операций в оперативной памяти, принятое в [1] (достаточно обосновано), оказывается
неприемлемым.
Ставится задача оценки эффективности реализации алгоритма ППО на современных
технических платформах, характеризующихся совершенно иными скоростными параметрами, в
запоминающей среде, близкой к однородной.
2. Сущность алгоритма ППО и критерий оптимальности
Примем следующие обозначения и определения.
Основной файл ОФ – файл объемом N записей, в котором производится поиск и выборка
нескольких записей по заданным ключам (идентификаторам).
Ключевой файл КФ – список K ключей искомых записей, упорядоченный синфазно с ОФ.
Активная запись – запись ОФ, ключ которой содержится в КФ.
Поле ),( jiF объема 1),( +−= ijjiV – совокупность последовательных записей ОФ,
заключенных в интервале порядковых номеров от i до j включительно.
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 139
Активность ),( jiA поля ),( jiF – количество активных записей, входящих в поле. Если
),( jiA 0= , то поле ),( jiF – пустое, если ),( jiA 1= , то поле единичное, если ),( jiA 1> , то
поле групповое.
В смысле приведенных определений, ОФ – это групповое поле ),1( NF объема N и
активности K . Сущность алгоритма ППО состоит в разбиении заданного группового поля на
некоторое количество производных полей (подполей) меньшего объема и последовательной
проверке их активностей путем просмотров ключей граничных записей. Если в результате проверки
оказывается, что проверяемое поле пустое, то над ним никакой дальнейшей обработки не
производится. Если поле единичное, то активная запись ищется методом дихотомии (″бинарного″
поиска [2]). Если поле групповое, то оно вновь подвергается аналогичному разбиению.
Формально рекурсивная процедура реализации алгоритма ППО включает следующую
последовательность этапов, начиная с обработки поля ),1( NF .
1. ;1:=i ;: Nj = ;:),( KjiA = NjiV =:),( .
2. Определение оптимального объема ),1( 1jV первого подполя, вычисляемого как
некоторая функция )],(),,([ jiVjiAf , и номера его нижней граничной записи 1j .
3. Определение активности подполя ),1( 1jA . Выполняется путем последовательных
сравнений ключа граничной записи 1j с ключами КФ, начиная с первой. Если 01 1 ====),( jA , то
выполняется п.4; иначе, если 1),1( 1 =jA , то выполняется п.5; иначе выполняется п.6.
4. Задача сводится к первоначальной задаче обработки поля ),1( 1 NjF + активностью K ,
то есть к повторению пп. 2, 3 с измененными исходными данными.
5. Активная запись ищется методом дихотомии, после чего задача сводится к обработке
поля ),1( 1 NjF + активностью 1−K .
6. Задача сводится к обработке поля ),1( 1jF активностью ),1( 1j , т.е. к повторению пп. 2, 3
и т.д. с исходными данными: ;1:=i ;: 1jj ==== );,1(:),( 1jAjiA = ),1(:),( 1jVjiV = .
После ее решения происходит возврат на первоначальный уровень разбиения и переход к
обработке поля ),1( 1 Nj + . При этом ;1: += ji ;: Nj = ),( jA 1 ),1( 1jAK −= и повторно
выполняются пп. 2, 3 и т.д. Обработка подполей заканчивается, когда исчерпывается КФ и
активность остающейся части ОФ становится равной нулю.
В [1] исследована более простая схема обработки, не требующая вычисления
оптимального объема очередного подполя на каждом шаге. В упрощенной схеме оптимальное
разбиение группового поля на m равных подполей на каждом уровне производится один раз на
первом этапе и в дальнейшем изменениям не подвергается. Разница эффективностей общей и
упрощенной схемы иллюстрируется следующим примером. Пусть ,16=N 4=K и активными
являются записи с номерами 10, 11, 14, 16. Пусть далее ( ) ( )[ ] ( )
( )jiA
jiV
ji,V jiAf
,
,
,, = . Тогда в
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 140
упрощенной схеме последовательно обрабатываются подполя (1,4), (5,8), (9,12), (13,16), а в общей
схеме – подполя (1,4), (5,7), (8,9), (10,11), (12,13), (14,15), (15,16). В первом случае количество
обращений к ОФ равно 12, во втором – 10. Отметим попутно, что для чисто последовательной
обработки и «простого» дихотомического (бинарного) поиска этот показатель равен 16.
В [1] показано, что для упрощенной схемы при допущении о равномерном распределении
активных записей и пренебрежении целочисленностью значения m минимальное количество
обращений к ОФ достигается при 2ln0
Km = . Анализ более эффективной общей схемы
показывает, что минимум обращений к ОФ достигается в «узловых» точках, соответствующих
целым значениям
( )
( )jiA
jiV
,
,
log2 . Искомая узловая точка соответствует функции
( ) ( )[ ] ] [
..
2,,
цб
divji,V jiAf α= , (1)
где
( )
( )jiA
jiV
,
,
log2=α ,
а ] [
..цб
x означает ближайшее целое, большее x .
Оптимальное значение 0m на каждом шаге разбиения равно
( )
] [ .
2
,
..
0
цб
div
jiV
m α= (2)
В частности, если
( )
( ) ( )1,2,...n
jiA
jiV n == ,2
,
,
, то ijo Am = .
Для начального разбиения ( ) ,, NjiV = ( ) KjiA =, , и если n
K
N
2= , то .0 Km =
Соотношения (1), (2) определяют оптимальные параметры алгоритма ППО в терминах
количества обращений к ОФ (т.е. без учета обработки КФ).
3. Имитационная модель и результаты моделирования
Аналитическая оценка полных затрат времени на выполнение программы ППО в однородной
памяти для КФ и ОФ представляет значительные сложности. Поэтому в качестве более простого
инструмента исследования выбрано имитационное моделирование процесса ППО. Целью
моделирования является сравнение реальных скоростей работы программы ППО с программами
дихотомического поиска и чисто последовательно совместной обработки КФ и ОФ в широком
диапазоне значений коэффициента активности NKa /= и разных значений коэффициента m .
При оценке результатов моделирования возникает необходимость учета двух
особенностей. Первая связана с высоким быстродействием и сравнительно низкой разрешающей
способностью измерения времени работы компьютера (единицы миллисекунд). Вторая
особенность связана с определенной нестабильностью времени выполнения программы и,
следовательно, результатов измерения при малых значениях времени.
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 141
Для учета обеих особенностей процесс моделирования для ОФ заданного объема
выполняется многократно, составляя сеанс моделирования из 1k суммируемых измерений, а сеанс
повторяется 2k раз, составляя серию сеансов, и результаты 2k сумм усредняются.
Моделирование проведено на компьютере 4P , язык программирования Паскаль (Delphi).
Схема имитационной модели показана на рис. 1.
Результаты моделирования отражены в табл. 1 и на рис. 2.
Таблица 1. Данные отдельной серии сеансов
a 142− 122− 102− 82− 62− 42−
1
τ 0,21333 0,22413 0,25790 0,25894 0,20103 0,14780
1t 0:0:6 0:0:26 0:0:126 0:0:505 0:1:560 0:4:472
2τ 0,21333 0,23305 0,26981 0,29007 0,23877 0,21641
2t 0:0:6 0:0:28 0:0:131 0:0:564 0:1:849 0:6:542
3
τ 160,27586 38,7355 9,95072 2,59835 0,69389 0,19172
3t 0:4: 648 0:4: 687 0: 4:846 0:5: 059 0:5:368 0:5: 791
Таблица содержит следующие данные для серии сеансов с конкретным значением
5105 ⋅=N и коэффициентом деления ( ) ( )
:
2ln
,1
0
jiA
m ≈
– абсолютные значения усредненной продолжительности сеансов 321 ,, ttt (формат мин:сек:
мсек для ППО, дихотомии и совместной последовательной обработки (СПО) соответственно при
разных значениях коэффициента активности a ;
Генерация
упорядоченных
ключей
Генерация
случайных
чисел 0÷q12
Сеанс
ППО
)(1
0m
k1=100
Сеанс
ППО
)(2
0m
k1=100
К
КФ
N
ОФ Управление
серией сеансов
1002 ====k
Сеанс
ППО
m(3)
k1=100
Сеанс
дихото-
мии
k1=100
Сеанс
СПО
k1=100
Рис. 1. Схема моделирования
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 142
– удельные значения продолжительности сеансов 321 ,, τττ (мсек), отнесенные к одному
искомому ключу.
Рис. 2. Усредненные значения 3121 ττττ /,/
Рис. 2 представляет усредненные зависимости относительных значений 21 ττ для
коэффициентов деления ( ) ( )
2ln
,1
0
jiA
m ≈ , ( ) ( )
] [
..
2
0 2
,
цб
div
jiV
m α≈ , ( ) ),(7,03 jiAm ≈ и 31 ττ от значений
коэффициента активности для ОФ=2·105, 5·105, 8·105. Значение ( )3m выбрано произвольно для
сопоставления результатов с ( )1
0m , )2(
0m .
Проанализировав таблицу и рис. 2, можно сделать следующие выводы:
1. Алгоритм ППО обеспечивает меньшее время обработки, чем дихотомия и СПО в
широком диапазоне значений a . Так, в диапазоне 612 22 −− ÷=a отношение 21 ττ составляет
величины порядка 0,9–0,65, т.е. ППО «работает» в 1,1–1,5 раз быстрее дихотомии. В таблице
62−>a СПО эффективнее ППО (и, тем более, дихотомического поиска).
2. Значения ( )1
0m и )2(
0m дают примерно одинаковый результат, что свидетельствует, с
одной стороны, о недостаточной корректности приложения (2) к однородной памяти, а с другой
стороны, о пологости гипотетической функции ( )mf в области минимума. Произвольно взятое
значение ( )3m дает явно худшие результаты, что косвенно подтверждает адекватность выбора
оптимальных значений m .
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 143
4. Заключение
Результаты моделирования могут быть использованы для оценки и выбора метода поиска-выборки
и обработки элементов последовательного файла (таблицы) по задаваемым ключам поиска в
зависимости от конкретных условий: диапазона коэффициентов активности ОФ, упорядоченности
ОФ и КФ, значимости возможности сокращения времени обработки.
Поскольку общий механизм сужения области поиска в В-деревьях, организующих индексы
баз данных [3], подобен механизму дихотомии ( m -томии), представляется возможным приложение
схемы «групповой» произвольно-последовательной обработки к страницам В-деревьев для поиска
К ключей-запросов.
СПИСОК ЛИТЕРАТУРЫ
1. Литвинов В.А. Алгоритм произвольно-последовательной обработки файлов // Кибернетика. – 1975. – № 5. –
С. 56 – 58.
2. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, 1978. – Т. 3: Сортировка и поиск. – 845 с.
3. Кузнецов С.Д. http://www.citform.ru/programming/theory/sorting/sorting 2.shtml.
Стаття надійшла до редакції 11.12.2008
|