- PVSM.RU - https://www.pvsm.ru -
Во время работы над своей презентацией для Qt developer days 2012 (QtCore in depth [1]), я произвёл сравнение производительности QMap и QHash и подумал, что неплохо было бы поделиться результатами в этой короткой статье.
Контейнеры Qt 4 были хорошо разобраны в этой старой статье [2] (или в этой [3] — на хабрахабре).
В Qt 4 QHash реализован с использованием Хеш-таблицы [4], а QMap — с использованием Списка с пропусками [5]. В Qt 5 реализация контейнеров немного изменилась, но принципы остались теми же.
Главные отличия:
offset
), которое может позволить в будущем ссылаться на внешние данные.
Тест довольно простой: в цикле много раз выполняется поиск по контейнеру и считается количество совершённых итераций за одну секунду. Это не совсем научно. Цель состоит только в том, чтобы показать форму кривых.
Исходный код: pastebin.com/Ya6D4QUm [8]
Тестирование проводилось на моём компьтере, GCC 4.7. Чем значение итераций выше, тем лучше. Шкала количества элементов — логарифмическая [9]. Следует ожидать, что для QHash величина не будет изменяться с ростом числа элементов, а для QMap она должна быть равной O(log N), что соответствует прямой линии на логарифмической шкале.
QMap работает немного медленее, чем std::map. Поиск по QMap выполняется быстрее, чем по QHash при количестве элементов меньше 10.
Это была хорошая идея — заменить список с пропусками красно-чёрными деревьями. Производительность контейнеров 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/
Нажмите здесь для печати.