воскресенье, 1 февраля 2009 г.

Что выбрать: std::map, std::vector или boost::unordered_map?

На практике столкнулся со следующей задачей. Имеется последовательность токенов (числовых или строковых). Необходимо подсчитать количество вхождения каждого токена в последовательность. Какие именно токены входят в последовательность - заранее не известно, однако известно, что общее количество разных токенов не превосходит заданной величины и что длина последовательности гораздо больше количества разных токенов.

Как решать? Возможный алгоритм: создать ассоциативный контейнер, в котором будем хранить пару "токен - количество вхождений", перебрать всю последовательность и подсчитать количество вхождений каждого токена. Нам придется многократно пополнять ассоциативный контейнер в процессе перебора последовательности и на каждом шаге проводить в нем поиск очередного токена.

"Стандартных" контейнера, которые подойдут в данном случае, как минимум три: std::map, сортированный std::vector и boost::unordered_map, который уже вошел в TR1. Вопрос, какой из них лучше подойдет для данной задачи?

Чтобы определить, какой вариант лучше, написал небольшое тестовое приложение. В нем содержатся три класса, реализующие варианты подсчета токенов с помощью разных ассоциативных контейнеров, два класса для генерации случайной последовательности токенов (int и string) и тестовая функций, выполняющая тестовый перебор последовательности несколько раз и определяющая среднее время, затрачиваемое на его выполнение. У программы два параметра: максимальное количество токенов и длина последовательности. Программа тестировалась на VS2005 с родной реализацией STL.


Результаты тестирования для последовательности из 1e5 целочисленных токенов


Кол-во токенов:101e21e31e41e5
std::map, int373531464716
std::vector, int403731511446
boost::unordered_map, int35312340427


Результаты тестирования для последовательности из 1e5 строковых токенов


Кол-во токенов:101e21e31e41e5
std::map, string556270493391
std::vector, string7174871071-
boost::unordered_map, string47463893437


Вектор работает плохо, но это и следовало ожидать. boost::unorderd_map демонстрирует лучшую производительность, чем std::map, однако если по началу их результаты примерно одинаковы, то потом следует резкий перекос (производительность boost::unorderd_map в 5-10 раз лучше), а затем маятник качается в обратную сторону, так что производительность std::map становится даже лучше. Посмотрим, как ведет себя производительность при других соотношениях длины последовательноси и количества токенов.

Кол-во токенов/длина последовательности:1e5/1e61e5/1e71e6/1e7
std::map, int625503113875
boost::unorderd_map, int98425786062
std::map, string17961534328875
boost::unorderd_map, string132863751125


Выводы


Сортированный вектор в данной задаче показывает худшие результаты - при большом количестве токенов ему становится совсем плохо, что вообщем-то не удивительно - ведь производится много операций вставок в произвольное место вектора, а такие операции для вектора очень дорогие.

boost::unordered_map работает быстрее std::map при условии, что длина последовательности гораздо больше количества токенов, т.е. каждый токен в среднем входит в последовательность множество раз.

Если же длина последовательности и количество токенов примерно совпадают (т.е. все токены входят в последовательность один-несколько раз ), то std::map может оказаться быстрее, но в редких случаях..

Итог - для моей задачи boost::unordered_map предпочтителен. И как хорошо, что это теперь стандартный контейнер :)

Исходные коды тестового проекта можно взять здесь.

1 комментарий: