2

我编写了一个基本程序，该程序接受字符串并通过将它们插入字符串->整数哈希映射来计算唯一字符串的发生率。

我使用 std::tr1::unordered_map 进行存储，为自定义哈希函数和自定义相等函数模板化。关键类型实际上是char*而不是 too-slow std::string。

然后，我更改了相同的代码以使用一个非常非常简单的哈希表（实际上是一个由哈希索引的 {key, value} 结构的数组），其大小为 2 的幂，并且对冲突进行线性探测。该程序的速度提高了 33%。

考虑到当我使用 tr1::unordered_map 时，我预先设置了哈希表的大小，因此它永远不必增长，并且我使用完全相同的哈希和比较例程，所以 tr1::unordered_map 这样做会使其速度减慢 50%与可以想象的最基本的哈希图相比？

我在这里所说的“简单”哈希映射类型的代码：

typedef struct dataitem {
    char* item;
    size_t count;
} dataitem_t;

dataitem_t hashtable[HASHTABLE_SIZE] = {{NULL,0}}; // Start off with empty table

void insert(char* item) {
    size_t hash = generate_hash(item);
    size_t firsthash = hash;
    while (true) {
        hash &= HASHTABLE_SIZE_MASK; // Bitmasking effect is hash %= HASHTABLE_SIZE
        if (hashtable[hash].item == NULL) { // Free bucket
            hashtable[hash].item = item;
            hashtable[hash].count = 1;
            break;
        }
        if (strcmp(hashtable[hash].item, item) == 0) { // Not hash collision; same item
            hashtable[hash].count += 1;
            break;
        }
        hash++; // Hash collision.  Move to next bucket (linear probing)
        if (hash == firsthash) {
            // Table is full.  This does not happen because the presizing is correct.
            exit(1);
        }
    }
}
4

4 回答 4

12

我希望扩展@AProgrammer 的答案。

您的哈希图很简单，因为它是根据您的需要定制的。另一方面std::tr1::unordered_map必须完成许多不同的任务，并且在所有情况下都做得很好。这需要在所有情况下都采用平均性能方法，因此它在任何特定领域都不会出色。

哈希容器非常特殊，因为有很多方法可以实现它们，您选择了 Open-Addressing，而标准强制实现者采用桶方法。两者都有不同的权衡取舍，这也是该标准这次实际上强制执行特定实现的原因之一：以便从一个库切换到另一个库时性能不会发生显着变化。在这里简单地指定 Big-O 复杂性/摊销复杂性是不够的。

您说您指示了unordered_map决赛元素的数量，但是您是否更改了负载因子？在发生冲突的情况下，链接是出了名的“糟糕”（因为缺乏内存局部性），并且使用较小的负载因子有利于分散您的元素。

最后，指出一个区别：当您调整哈希图大小时会发生什么？通过使用链接，unordered_map不会移动内存中的元素：

  • 对它们的引用仍然有效（即使迭代器可能无效）
  • 在大或复杂对象的情况下，不调用复制构造函数

这与您的简单实现形成对比，后者会产生O(N)副本（除非您使用线性重新散列来分散工作，但这绝对不简单）。

因此，似乎选择unordered_map是平滑尖峰，代价是平均插入速度较慢。

不过，您可以做一些事情：提供自定义分配器。通过为您的用例编写一个特定的分配器，并一次性分配其所有内存（因为您知道将插入多少对象，并且可以让分配器报告一个节点有多少内存）。然后以类似堆栈的方式分配节点（简单的指针增加）。它应该（某种程度上）提高性能。

于 2011-04-16T13:14:19.160 回答
6

您的“本地哈希图”根本不是哈希图，而是侵入式哈希集。这就是它更快的原因。就那么简单。

好吧，实际上侵入式哈希集也不精确，但它是最接近的匹配。

于 2011-04-16T06:19:25.760 回答
4

一般来说，比较未按照相同规格构建的组件的速度是不公平的。

在不确切知道您测量的内容的情况下 - 哪个负载因子的操作组合与当前/不存在数据的组合 - 很难解释差异来自哪里。

g++的TR1通过链式解决碰撞。这意味着动态分配。但这也可以在高负载水平下提供更好的性能。

于 2011-04-16T06:16:48.253 回答
1

您的“本土”哈希图比1更快，std::tr1::unordered_map因为正如您自己所说，您的本土哈希图是“简单的”并且它不处理检查哈希表是否已满。可能还有很多你在操作之前没有检查的东西。这可能是您的哈希映射比std::tr1::unordered_map.

此外， 的性能std::tr1::unordered_map是由实现定义的，因此不同的实现在速度方面会有所不同。您可以查看它的实现并将其与您的进行比较，因为这是您可以做的第一件事，我相信这也将在一定程度上回答您的问题。

1.我只是假设你的说法是正确的，并据此说了以上的话。

于 2011-04-16T05:49:44.453 回答