翻译-QMap与QHash小基准测试

本文翻译自: https://woboq.com/blog/qmap_q…
作者: 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 <ogoffart@woboq.com>
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;}