翻譯 | QMap與QHash小基準
- 2019 年 10 月 5 日
- 筆記
本文翻譯自: https://woboq.com/blog/qmap_qhash_benchmark.html 作者: Olivier Goffart
在我的Qt開發者日2012演示文稿(深入探討QtCore)時，我做了一個比較QMap和QHash的基準。我認為在這篇簡短的部落格文章中分享結果會很不錯。
在底層實現上
在Qt 4中QHash使用哈希表實現，而QMap使用跳躍表實現。
在Qt 5中，雖然容器的實現有所改變，但概念仍然相同。主要有以下區別：
- QVector、QString和QByteArray現在共享相同的實現(QArrayData)。主要的區別是現在有一個偏移量，將來可能允許引用外部數據。
- QMap的實現已經完全改變了。它不再是跳躍表，而是一個紅黑樹。
基準
基準測試很簡單，並且在一秒鐘內在循環中進行大量查找並計算迭代次數。 這不是真正科學嚴謹的。我們的目標只是展示曲線的形狀。
結果
在我的電腦上運行，gcc 4.7。越高越好。元素的數量是對數標度。對於QHash，人們應該期望它不隨元素數量而變化，對於QMap，它應該是O(log N): 對數刻度上的直線。
Qt 4.8
QMap的執行稍微慢於std::map。對於少於10個元素，QMap查找比QHash更快。
Qt 5
將跳躍表更改為紅黑樹是一個好主意。與STL相比，Qt容器的性能基本相同。如果少於20個元素，QMap比QHash更快。
如果比較Qt5和Qt4之間的數量，您會發現Qt5的性能更好。這可能與QString中的更改有關。
結論
典型的規則是：僅當您需要對項進行排序，或者您知道您的映射中始終只有很少的項時，才使用QMap。
相關知識
- 跳躍表：通過增加多級索引(會增加額外的空間)來提升插入與刪除操作。
- 紅黑樹：是一種特定類型的二叉樹，進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡。
附: 基準測試程式
/* Copyright 2013 Olivier Goffart <[email protected]> http://woboq.com/blog/qmap_qhash_benchmark.html */ #include <QtCore/QtCore> #include <unordered_map> #ifndef CONTAINER #error CONTAINER must be defined to QMap, QHash, std::map or std::unordered_map #endif namespace std{ /* std::hash specialization for QString so it can be used * as a key in std::unordered_map */ template<class Key> struct hash; template<> struct hash<QString> { typedef QString Key; typedef uint result_type; inline uint operator()(const QString &s) const { return qHash(s); } }; } int main(int argc, char **argv) { if (argc < 2) qFatal("Missing number of element to add"); QByteArray a = argv[1]; uint num = a.toUInt(); // creates an array of random keys QVector<QString> strs(num); for (int i=0; i < num; ++i) strs[i] = qvariant_cast<QString>(qrand()); CONTAINER<QString, QString> c; for (uint i = 0; i < num; ++i) { QString &k = strs[i]; c[k] = QString::number(i); } quint64 it = 0; const QString *arr = strs.constData(); QElapsedTimer t; t.start(); while (t.elapsed() < 1000) { const QString &k = arr[(++it)*797%num]; c[k]; // perform a lookup } qDebug() << it/1000; }
