Исследование производительности процессора обработки структур в системе…
9
полностью совпадающего ключа. Ускорение относительно про-
граммной реализации на микропроцессоре достигается благодаря то-
му, что в СП заложен больший параллелизм при поиске, а также реа-
лизован механизм хранения трассы дерева. В программной же реали-
зации ускоренное обращение к ранее загруженной части дерева
возможно только в том случае, если эта информация осталась в кэш-
памяти. Операция
Поиск
в худшем случае требует
(log )
b
O n
тактов.
Экспериментальное исследование временной сложности ос-
новных операций.
Экспериментальные исследования временной
сложности операций
Добавление
,
Поиск
и
Удаление
проводились при
помощи измерения количества тактов, затраченных на выполнение
определенного количества итераций. В первом эксперименте был по-
лучен график зависимости количества тактов, необходимых для со-
здания различных структур при выполнении операции
Добавление
случайных ключей, от количества элементов в структуре (рис. 3). Во
втором и третьем экспериментах были получены графики зависимо-
стей количества тактов, необходимых для выполнения 10
3
операций
Удаления
(рис. 4) и
Поиска
(рис. 5) случайных ключей для структур с
различным количеством элементов. Замер количества тактов вместо
измерения времени проведения экспериментов дает более четкое
представление об эффективности аппаратного решения, так как
уменьшает влияние технологической разницы в реализации тестовых
платформ.
Рис. 3.
Экспериментальное исследование временной сложности операции
Добавление
В экспериментах использовалась реализация СП со следующими
параметрами: разрядность ключей и данных — 32 бит; максимальное
количество ключей в структуре — 2·10
6
; количество уровней
B
+ де-
