30
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
В табл. 4 приведены значения времени выполнения вставки одно-
го элемента в середину структуры.
Таблица 4
Значения времени выполнения вставки одного элемента
в середину структуры, мс
Количество элементов
IgushArray
std::vector
Результат
1 000
10
10
Одинаково
10 000
10
30
Более 3
100 000
60
360
6
1 000 000
80
3 580
45
10 000 000
550
36 940
67
Из результатов видно, что время операции вставки std::vector
возрастает линейно вместе с количеством элементов, а время опера-
ции вставки IgushArray — как
N
1/2
.
В табл. 5 даны значения времени удаления одного элемента из
середины структуры.
Таблица 5
Значения времени удаления элемента из середины структуры, мс
Количество элементов
IgushArray
std::vector
Результат
1 000
10
10
Одинаково
10 000
40
10
Ниже 4
100 000
60
300
Более 5
1 000 000
200
3 270
16
10 000 000
590
31 310
53
Из результатов ясно, что время удаления std::vector увеличивает-
ся линейно вместе с количеством элементов, а время операции уда-
ления IgushArray — как
N
1/2
.
Заключение.
В статье описана структура с произвольным досту-
пом, которая как массив имеет быструю константную операцию до-
ступа, сложность операции вставки или удаления составляет всего
O
(
N
1/2
).
Структура может рассматриваться как «быстрый массив»
или «массив с быстрой операцией вставки». Структура была реализо-
вана и протестирована.
СПИСОК ЛИТЕРАТУРЫ
1.
Cormen T.H. , Le iser son C.E., Rives t R.L., St e in Cl. Introductin to
Algorithms. Third Edition. Cambridge: The MIT Press, 2009.
2.
Макконнелл Дж. Основы совеременных алгоритмов. М.: Техносфера,
2006.
3.
Strous trup B. The C++ Programming Language. Special Edition. Boston:
Addison-Wesley, 2000.
4.
http://caladan.nanosoft.ca/fastarray.php.
FastArray.
Статья поступила в редакцию 4.07.2012