Инженер Гудков К.С.
Государственный научно-исследовательский институт
авиационных систем, Россия
Оценка времени работы одного алгоритма, находящего разность в версиях
открытых внешних справочников
В корпоративных информационных системах часто используются таблицы
нормативно-справочной информации, полученные на основе внешних справочников
открытых баз данных. При этом часто составители внешних справочников предоставляют
для скачивания только их финальную версию, не предоставляя информацию о
внесённых изменениях. Поэтому актуальной задачей является самостоятельное
нахождение различий между сохранённой предыдущей версией справочника и
скачанной текущей версией справочника. Формализуем эту задачу. Пусть и
предыдущая, и текущая версии открытой базы данных представлены в CSV-формате. Если это не
так, то можно осуществить предварительное преобразование исходного формата к CSV-формату.
Математическая модель управления обработкой нормативно-справочной информации, в
рамках которой используется подобный подход, описана в [1]. Необходимо сравнить
текущую и предыдущую версии справочника, получив файл с добавленными кортежами
и файл с удалёнными кортежами. Оба выходных файла также должны быть
представлены в CSV-формате. Для решения этой задачи в работе [2] был предложен следующий алгоритм:
· Данные предыдущей версии справочника заносятся в красно-чёрное дерево [3].
Узел дерева – это CSV-строка, соответствующая кортежу справочника.
· Осуществляется линейный проход по CSV-файлу с текущей
версией справочника. Для каждой строки проверяется её наличие в красно-чёрном
дереве. Если она там есть, то никакие действия не предпринимаются. Если её там
нет, то строка добавляется к CSV-файлу, содержащему добавленные в текущей версии
справочника по сравнению с предыдущей версией справочника строки.
· Данные текущей версии справочника заносятся в красно-чёрное дерево. Узел
дерева – это CSV-строка, соответствующая кортежу справочника.
· Осуществляется линейный проход по CSV-файлу с предыдущей
версией справочника. Для каждой строки проверяется её наличие в красно-чёрном
дереве. Если она там есть, то никакие действия не предпринимаются. Если её там
нет, то строка добавляется к CSV-файлу, содержащему удалённые в текущей версии
справочника по сравнению с предыдущей версией справочника строки.
В работе [2] было проведено сравнение с точки зрения скорости работы
следующих структур данных: красно-чёрного дерева, AVL-дерева [4],
хэш-таблицы, бинарного дерева поиска и линейного списка. Сравнение проводилось
с использованием теории сложности и прикладной математической статистики. При
этом наихудшие результаты были показаны с использованием бинарного дерева
поиска и линейного списка. В данной работе будет проведено независимое
сравнение скорости работы алгоритма методом наименьших квадратов для следующих
структур данных: красно-чёрного дерева, AVL-дерева, хэш-таблицы.
Кроме того, будут получены формулы, позволяющие оценить скорость работы
алгоритма для конкретного компьютера, на котором будет использоваться алгоритм.
Гипотеза: при использовании всех трёх структур данных формула
зависимости времени работы алгоритма в миллисекундах от числа записей имеет вид
, где 
– суммарное число записи в CSV-файлах, 
– вычисляемый методом
наименьших квадратов коэффициент, зависящий от используемой структуры данных и
используемого компьютера. Так как при отсутствии записей алгоритм сразу же
заканчивает работу, то использование дополнительного коэффициента 
не требуется. Результаты
эксперимента, проведённого средствами компьютерного моделирования, – это
времена работы 
и соответствующие им 
. Неизвестный коэффициент 
необходимо оценить
при помощи метода наименьших квадратов. При помощи 
обозначено число
экспериментов.
В результате, были получены следующие результаты:
· 
· 
· 
Во всех формулах последняя цифра значащая. То есть наименьшее время
работы достигается при использовании красно-чёрного дерева, чуть большее время
работы – при использовании AVL-дерева. Худшие результаты показаны при
использовании хэш-таблицы. Полученные результаты согласованы с результатами,
полученными в [2] методами прикладной математической статистики.
Можно заметить, что в приведённых формулах появилось дополнительное
частное 
. Его появление вызвано тем обстоятельством, что эксперименты
проводились на конкретном компьютере со своей производительностью. Числитель 
– это коэффициент,
характеризующий производительность компьютера, на котором были проведены
эксперименты. Знаменатель 
– это коэффициент,
характеризующий производительность компьютера, на котором будет использоваться
алгоритм. И 
, и 
обратно
пропорциональны временам работы алгоритма 
и 
. Легко заметить, что частное 
равно единице для
компьютера, на котором были проведены эксперименты. В качестве примера теста
производительности можно привести инкрементирование переменной от 1 до
миллиарда. На компьютере, на котором производился эксперимент, с округлением до
сотен миллисекунд оно заняло 700 миллисекунд. Если на компьютере, на котором
необходимо узнать время работы исходного алгоритма оно займёт 600 миллисекунд,
то 
, так как 
.
Следует отметить, что для оценки частного 
нельзя использовать
данные о тактовой частоте процессора. Как показано в [5] различные процессоры
могут сильно различаться в производительности при одинаковой тактовой частоте.
Следовательно, при оценке производительности компьютера нельзя опираться на
этот параметр. В данной работе предложен наиболее простой тест сравнения
производительности. Если требуется большая точность, то необходимо использовать
один из тестов, рекомендованных в [5].
В работе был представлен алгоритм выделения изменений в версиях открытых
баз данных. Предложенный алгоритм базируется на использовании красно-чёрного
дерева, предложенного Байером в 1972 году. При помощи метода наименьших
квадратов было показано, что для поставленной задачи использование
красно-чёрных деревьев более предпочтительно, чем использование AVL-деревьев или
хэш-таблиц. При помощи метода наименьших квадратов получены оценки времени
работы алгоритма при использовании красно-чёрных деревьев, AVL-деревьев и
хэш-таблиц.
Литература:
1. Гудков К.С. Математическая модель управления справочниками административно-территориального
деления стран СНГ в корпоративных информационных системах // Прикладная
информатика – 2010. – №5(29). – С.117-124.
2. Гудков К.С. Выделение изменений в версиях открытых баз данных при
построении автоматизированной системы импорта внешних справочников. // Основни
проблеми на съвременната наука – 2010. Том 22 Съвременни технологии на
информации Математика Здание и архитектура. – 2010. – С.16-19.
3.
Bayer R.
Symmetric binary B-trees: Data Structure and maintenance algorithms. // Acta
Informatica. – 1972. – P.290-306.
4. Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации
информации. // Доклады АН СССР. – 1962. – №2(146). – С.263-266.
5. Мюллер С. Модернизация и ремонт ПК. Полный курс. – Москва: Вильямс, 2004.
– 1344 с.