Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска Двоичные деревья поиска Категория реферата: Рефераты по информатике, программированию Теги реферата: отчет о прохождении практики, шпоры на экзамен Добавил(а) на сайт: Dvoreckov. Предыдущая страница реферата | 23  24  25  26  27  28  29  30  31  32  33 | Следующая страница реферата	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 байт.

Главная | Партнеры | Лучшие рефераты

Обратная связь

Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска | страница реферата 28 | Большая Энциклопедия Рефератов от А до Я    Все рефераты, курсовые, дипломы, шпаргалки, сочинения, изложения, решебники, конспекты являются общедоступными    Копирование и размещение в интернете разрешается только при наличии активной индексируемой ссылки на Ahaha.ru

© 2006-2020 «Ahaha.ru»