|
3070
|
3019
|
27380
|
50665
|
26954
|
|
6000
|
3528
|
3618
|
39294
|
72996
|
39227
|
|
7000
|
4322
|
4542
|
53255
|
99402
|
53309
|
|
8000
|
5299
|
5531
|
71406
|
129964
|
70766
|
|
9000
|
6180
|
6553
|
89583
|
164943
|
89935
|
|
10000
|
7527
|
7797
|
112190
|
202993
|
111439
|
Таблица 6. Удаление элемента по ключу (случайные
ключи)
Постоянно сортированный массив – это массив, в который
элементы вставляются так, что бы он сохранял свойство упорядоченности. Массив с
постсортировкой – это массив, в который сначала вставляются все элементы, а
потом он сортируется алгоритмом быстрой сортировки. Данные таблицы, безусловно, не являются истиной в последней инстанции, но позволят вам прикинуть, какая из
структур данных будет наиболее производительна в вашей программе, учитывая
предполагаемую вероятность операций вставки, удаления и поиска. Так, например, массив с постсортировкой является весьма привлекательным по производительности, но совершенно не подходит для комплексных работ, так как предполагает
фиксированный порядок действий – сначала только добавление элементов, а после
использование полученной информации. Другие структуры данных лишены этого
недостатка. Для большого числа (порядка 10 000) случайных элементов время
поиска в ДДП и КЧД становится практически одинаковым. Как следствие, можно
реализовать более простые алгоритмы, исходя из некоторых свойств входных
данных. С другой стороны, в крайнем случае (возрастающие элементы) ДДП отстают
от КЧД на несколько порядков. Постоянно сортированный массив является абсолютным
победителем по скорости, но не имеет естественной поддержки отношений
родитель-ребёнок. Если они вам нужны, придётся реализовывать их поддержку
самостоятельно. Также надо всегда помнить, что при количестве элементов порядка
тысячи, асимптотические показатели скорости ещё не вполне вступили в силу и
теоретически более быстрые структуры данных на практике могут оказаться более
медленными. Так, например, скорость поиска в КЧД и массиве с пресортировкой до
5000-7000 практически одинакова. Так же надо заметить, что тестирование
производилось на объектах относительно малого размера (8 байт), сравнимого с
размером указателя (4 байта). Все виды массивов сортированных подразумевают
весьма интенсивное копирование элементов, в то время как деревья работают с
указателями. При размере элемента, на порядки превышающем размеры указателя, акценты сместятся весьма значительно. Например, ниже приведены результаты
испытания с ключом типа int (32-x битное целое) и битовыми данными размером в
256 байт.
Главная