«Даже если гарантированное время логарифмического поиска вас устраивает, стандартные ассоциативные контейнеры не всегда являются лучшим выбором.
Как ни странно, стандартные ассоциативные контейнеры часто уступают по производительности банальному векторному контейнеру» — К.
Мейерс «Эффективное использование STL».
Многих может заинтересовать практическая сторона этого совета: насколько на самом деле может быть быстрее отсортированный вектор, чем ассоциативные контейнеры.
Меня тоже заинтересовал этот вопрос и я решил провести небольшой тест и нарисовать пару графиков, чтобы все встало на свои места.
Для начала немного теории (тем, кто знает, что такое вектор и карта, читать не нужно).
Карта в STL — это ассоциативный контейнер для хранения пар ключ-значение.
Данные в нем хранятся в отсортированном виде, хотя стандарт C++ не определяет реализацию; чаще всего карта реализуется в виде красно-черного дерева, в котором каждый элемент хранит указатели на двух дочерних элементов.
Вектор в STL — это просто контейнер элементов, который гарантирует, что хранящиеся в нем данные не будут фрагментированы.
Эффективный поиск в нем можно организовать посредством сортировки и дальнейшего бинарного поиска.
Как и в первом случае, сложность поиска равна O(ln(n)).
Разница в скорости будет варьироваться за счет лучшего кэширования во втором случае (данные располагаются локально и для хранения требуется меньше памяти).
Для сравнения скорости вставки и поиска я написал тестовая программа , который производит два типа измерений — запись случайных значений (random(3)) в контейнеры при измерении времени (с помощью gettimeofday) и поиск случайных значений в контейнере за определенное время (10 с).
Таким образом измеряется время вставки данных в контейнер и количество поисков в контейнере за интервал времени.
Инструменты: Аппаратное обеспечение: Двухпроцессорный (Intel Xeon E5420) сервер без файла подкачки.
Программное обеспечение: сервер Ubuntu с ядром 2.6.28, gcc 4.3.3. Компилируем проект с ключами: -O3 -felide-constructors -fno-Exceptions -fno-rtti -funroll-loops -ffast-math -fomit-frame-pointer -march=core2 Каждый тест запускался несколько раз (N=10) и фиксировались минимальное, максимальное и среднее значения какого-либо параметра.
При проведении тестов разница полученных значений была минимизирована (снижение нагрузки на сервер, установка cpu affinity).
Данные, полученные при вставке элементов в контейнеры 
На первом графике показана зависимость времени вставки и сортировки контейнеров в зависимости от количества элементов.
Обе шкалы логарифмические, поэтому для наглядности построена еще одна кривая, показывающая сумму времени вставки и сортировки для вектора — она показана пунктиром.
Горизонтальные черные линии показывают ошибку для каждого эксперимента – максимальное и минимальное значения.
Как видите, для 1 миллиона записей время вставки и сортировки вектора примерно в 10 раз меньше (0,11 с), чем для карты (1,1 с).
Данные, полученные при поиске элементов в контейнерах 
На втором графике показана зависимость количества поисков, выполняемых за единицу времени (10 секунд), от количества элементов в контейнере.
Вы можете видеть, что скорость поиска в векторе выше, как и ожидалось выше, и на 1 миллион записей количество поисков в векторе примерно в 3,9 раза больше, чем в карте.
Из этих тестов видно, что производительность вектора может быть значительно (в 3,9 раза) выше, чем у карты, при этом заполнение вектора один раз и его сортировка также происходит быстрее (в 10 раз), чем у карты.
Таким образом, отсортированные векторы следует использовать в ситуациях редкого изменения данных и частого поиска, например, для данных, которые загружаются при запуске программы и редко изменяются в дальнейшем.
И как всегда нельзя забывать, что преждевременная оптимизация – это зло.
Теги: #C++ #STL #map #vector # Performance #C++
-
Дизайн Внешнего Интерфейса
19 Oct, 24 -
Tizen Получит Поддержку Android-Приложений
19 Oct, 24 -
Anonymous Начали Мстить Megaupload
19 Oct, 24 -
На Вкус И Цвет Или Раскраска Для Android
19 Oct, 24
