ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
29
Отметим, что в массиве, используемом для реализации очереди с
двумя концами, можно применить структуру IgushArray и т. д. Тогда
сложность операции доступа будет
O
(
k
),
где
k
—
степень; сложность
операции вставки или удаления составит
О
(
N
1/
k
).
В простом случае,
описанном в статье,
k
= 2.
Тесты производительности.
Структура данных была реализова-
на. Тесты были проведены с помощью компьютера со следующей
конфигурацией: Inter Core 2 Duo 1,83 МГц, 2 Гбайт, Ubuntu,
GCC версии 4.5.2. Каждая операция повторялась 1 000 раз. Сравни-
валась стандартная реализация массива из математической библиоте-
ки std::vector [3].
В табл. 2 приведены значения времени суммирования элементов
структур при произвольном доступе к элементу по индексу.
Таблица 2
Значения времени суммирования элементов структур
при произвольном доступе к элементу по индексу, мс
Количество элементов
IgushArray
std::vector
Результат
1 000
80
10
Ниже 8, 0
10 000
840
110
7,6
100 000
8 220
1 130
7,3
1 000 000
89 340
15 720
5,7
10 000 000
903 520
130 200
6,9
Из результатов ясно, что время суммирования возрастает линей-
но вместе с количеством элементов. Следовательно, обе структуры
имеют константное время доступа к элементу.
В табл. 3 даны значения времени суммирования элементов струк-
туры при доступе по итератору.
Таблица 3
Значения времени суммирования элементов структур
при доступе по итератору, мс
Количество элементов
IgushArray
std::vector
Результат
1 000
170
40
Ниже 4,2
10 000
1 700
340
5,0
100 000
16 910
3 420
4,9
1 000 000
167 600
34 310
4,9
10 000 000
1 686 220
343 090
4,9
Согласно результатам, время суммирования увеличивается ли-
нейно вместе с количеством элементов.
Худшее время доступа в структуре IgushArray обусловлено тем,
что она является более сложной структурой, чем массив.