Время работы программы генерации случайной выборки
для некоторых структур данных
Структура m = 1 ООО ООО m = 5 ООО ООО m = 10 ООО ООО
* сек Мбайт сек Мбайт сек Мбайт
STL 9,38 72
BST 7,30 56
BST* 3,71 16 25,26 79
Корзины 2,36 60
1 В мою первую версию этой программы вкралась хитрая ошибка. Компилятор сообщал о наличии внутреннего несоответствия и завершал работу. Я отключил оптимизацию, ошибки исчезли, и я мысленно обругал авторов компилятора Позже я понял, что при написании кода функции обхода я забыл включить проверку на нулевое значение р. Оптимизатор пытался преобразовать концевую рекурсию в цикл и завершал работу, поскольку не мог найти условия для выхода из цикла.
Структура m = 1 ООО ООО m = 5 ООО ООО m = 10 ООО ООО
сек Мбайт сек Мбайт сек Мбайт
Корзины* 1,02 16 5,55 80 *
Битовый вектор 3,72 16 5,70 32 8,36 52
Приведенные в таблице данные не включают затраты на вывод результатов (требующий приблизительно столько же времени, сколько работает библиотека STL). В простой реализации двоичных деревьев поиска исключена сложная схема балансировки, используемая STL (спецификация STL гарантирует хорошую производительность даже в худшем случае), и поэтому она работает несколько быстрее и использует меньший объем памяти. Для реализации STL обращения к диску начинались при m = 1 600 ООО, тогда как первый вариант BST доходил до m - 1 900 ООО. Сокращение BST* обозначает двоичное дерево поиска с некоторыми оптимизациями. Главная из них состоит в одновременном выделении памяти иод все узлы единым блоком (как в задаче 5). Это значительно уменьшает затраты памяти и сокращает время выполнения примерно на одну треть. Помимо этого, рекурсия в этой программе заменяется итерацией (как в задаче 4) и используется узел-маркер, описанный в задаче 7, что приводит к дополнительному увеличению скорости на 25%.
Опубликовал vovan666
April 17 2013 00:03:33 ·
0 Комментариев ·
4510 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
