- PVSM.RU - https://www.pvsm.ru -

QMap vs. QHash: небольшой бенчмарк

Во время работы над своей презентацией для Qt developer days 2012 (QtCore in depth [1]), я произвёл сравнение производительности QMap и QHash и подумал, что неплохо было бы поделиться результатами в этой короткой статье.

Под капотом

Контейнеры Qt 4 были хорошо разобраны в этой старой статье [2] (или в этой [3] — на хабрахабре).
В Qt 4 QHash реализован с использованием Хеш-таблицы [4], а QMap — с использованием Списка с пропусками [5]. В Qt 5 реализация контейнеров немного изменилась, но принципы остались теми же.
Главные отличия:

  • QVector, QString и QByteArray теперь реализованы одинаково (QArrayData [6]). Здесь основным отличием стало смещение (offset), которое может позволить в будущем ссылаться на внешние данные.
  • Устройство QMap изменилось полностью: теперь это не Список с пропусками, а Красно-чёрное дерево [7].

Бенчмарк

Тест довольно простой: в цикле много раз выполняется поиск по контейнеру и считается количество совершённых итераций за одну секунду. Это не совсем научно. Цель состоит только в том, чтобы показать форму кривых.
Исходный код: pastebin.com/Ya6D4QUm [8]

Результат

Тестирование проводилось на моём компьтере, GCC 4.7. Чем значение итераций выше, тем лучше. Шкала количества элементов — логарифмическая [9]. Следует ожидать, что для QHash величина не будет изменяться с ростом числа элементов, а для QMap она должна быть равной O(log N), что соответствует прямой линии на логарифмической шкале.

Qt 4.8

QMap vs. QHash: небольшой бенчмарк

QMap работает немного медленее, чем std::map. Поиск по QMap выполняется быстрее, чем по QHash при количестве элементов меньше 10.

Qt 5

QMap vs. QHash: небольшой бенчмарк

Это была хорошая идея — заменить список с пропусками красно-чёрными деревьями. Производительность контейнеров Qt теперь почти такая же, как у контейнеров STL. Поиск по QMap выполняется быстрее, чем по QHash при количестве элементов меньше 20.
Если вы сравните показатели Qt 4 и Qt 5 то увидите, что производительность Qt 5 выше. Это может быть связано с изменениями в QString.

Заключение

Используйте QMap только в случае, если вам нужно отсортированное содержимое или вы знаете, что в вашем словаре всегда содержится небольшое количество элементов.

Автор: epicfailguy93

Источник [10]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/qt-2/27584

Ссылки в тексте:

[1] QtCore in depth: http://www.youtube.com/watch?v=vixQxXCVR10

[2] этой старой статье: http://doc.qt.digia.com/qq/qq19-containers.html

[3] этой: http://habrahabr.ru/post/127870/

[4] Хеш-таблицы: http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0

[5] Списка с пропусками: http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81_%D0%BF%D1%80%D0%BE%D0%BF%D1%83%D1%81%D0%BA%D0%B0%D0%BC%D0%B8

[6] QArrayData: http://code.woboq.org/qt5/qtbase/src/corelib/tools/qarraydata.h.html#QArrayData

[7] Красно-чёрное дерево: http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

[8] pastebin.com/Ya6D4QUm: http://pastebin.com/Ya6D4QUm

[9] логарифмическая: http://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%88%D0%BA%D0%B0%D0%BB%D0%B0

[10] Источник: http://habrahabr.ru/post/170017/