翻译 | 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; }
