由于性能原因，替代stdext :: hash_map

我正在开发一个高性能应用程序，其中所有调用都必须是合理的。我有一张在每次交易开始时使用过一次的地图，用于查找我想改进的地方。地图在启动时加载，之后不会更改。由于性能原因，替代stdext :: hash_map

下图中的关键字是一个std :: string，但如果需要它可以将其更改为一个char数组。 C或C++作为解决方案很好。

typedef stdext::hash_map<std:string, int> symbols_t;

有谁知道任何其他解决方案，可以消除查找或更快？

非常感谢您的帮助。

编辑的其他信息：
1. hash_map当前有350,000个元素。
2.每个键值通常在4到10个字符之间。
3.信息从第三方API的回调中收到。在进行地图查找时，回调被赋予一个用作键值的符号。该软件的其余部分是从映射查找返回的int驱动的。

感谢：谢谢大家的意见。你给了我一些探索的途径。我一定会尝试一下。我很感激帮助。

来源

2010-09-22 skimobear

我非常怀疑，如果你用'char *'替换'std :: string'，整体性能会大大不同。但是，这肯定会使代码更不易维护。 – ereOn 2010-09-22 11:59:02

哈希映射是O（1），因此查找时间仅取决于计算哈希所需的时间。你看过吗？ – sbi 2010-09-22 12:19:35

我在想，这是你代码中最大的瓶颈吗？闻起来不成熟的优化。 – ybungalobill 2010-09-22 12:29:35

我想说我们缺乏这方面的信息来可靠地告诉你该怎么做。

您可能希望更具体地了解查找内容以及函数的总体算法成本。

如果你用丑陋的黑客弄乱了代码，在算法成本为O(n²)的函数中赢得1个恒定的微秒，那么你在错误的问题上浪费你的时间。

没有额外的细节，我们无法确定。

来源

2010-09-22 12:03:56 ereOn

我添加了一些额外的信息。希望它有帮助，这是足够的:) – skimobear 2010-09-22 12:20:47

手动编码更适合您的数据的哈希映射。

简单的哈希函数是不够好
使用稀疏C-数组，它是足够大的没有冲突的数据
确保所有来电都被内联
确保你永远不会复制或转换字符串
编写代码以生成此C数组的C源代码。这是怎么回事的样子（用0表示无输入）：
```
int symbols[] = { 0,0,0,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,0,2 /* etc */ }; 
```
你写的代码可以搜索那里有你的数据没有冲突的哈希函数。也许它是像符号的前两个字符（或前4个）那样简单的int。如果你不关心空间，你不需要为所有可能的数据做一个完美的哈希，而只需要一个对所有数据来说都很完美的快速哈希。

的数组索引是simple_hash(string& s)

请记住，如果你改变了符号，您可能需要重写哈希，当然需要重新生成表。

编辑：根据@火焰的答案 - 在＃5的代码是为你写的，被称为gperf

来源

2010-09-22 12:09:06

如果你真的需要键入上串一的hash_map，那么你可以尝试定制散列函数。如果你的字符串在前四个字符中都是唯一的，那就编写一个自定义的散列函数，它只能查看字符串中前四个字符，然后使用hash_map。这里有一个例子：

struct CustomStringHash: std::unary_function<std::string, size_t> 
{ 
    size_t operator()(const std::string & s) const 
    { 
     switch (s.size()) 
     { 
       case 0: 
        return 0; 
       case 1: 
        return s[0] + 1; 
       case 2: 
        return (s[0] << 8) + s[1]; 
       default: //3 or more chars long, plus a terminating null 
        return *reinterpret_cast<const uint32_t *>(s.c_str()); 
     } 
    }

如果你的字符串的字符8-12平均，和前四个字符大多是唯一的，那么自定义哈希函数可以很显著加快查找。

来源

2010-09-22 12:19:57 Doug

我们如何建议您如何消除您的查找，因为您不告诉我们您查找什么或为什么？我们需要更多的算法细节。

至于性能，是否使用hash_map取决于一些复杂性。 HashMap有（如果你有一个很好的实现，现实）O（1）查找，插入。但是不断的开销可能会很高。如果你有很少的条目，你可能会在这里受到影响，并可能从std :: map中受益。如果频繁访问映射的许多不同元素并且可能会考虑某种排序数组，则可能还会遇到缓存一致性问题。

来源

2010-09-22 12:23:23 Puppy

上面添加了一些额外的信息。请让我知道，如果它不够。 thx – skimobear 2010-09-22 12:30:09

这个映射是完全不变的，还是程序调用之间的变化？对于常量散列（编译时已知），有gperf程序，它可以生成快速且有保证的O（1）查找表。

此外，如果您告诉我们为什么以及如何确切地图查找会减慢代码，它可能有助于理解您的问题。

来源

2010-09-22 12:55:14 blaze

hash_map的内容每天都在变化。它每天早上从数据库中取出。这听起来很有趣，我会看看:) – skimobear 2010-09-22 13:06:10

gperf生成与您的数据硬编码的C++源文件。使用gperf从数据库创建一个动态库，每天早上卸载和加载。 – 2010-09-22 14:51:34

散列表通常足够快O（1），我们不能告诉你是否可以在不知道应用程序的整体结构的情况下摆脱散列表。这可能是不可能的。

我不知道如何实施stdext::hash_map<std::string,T>，但prefix tree是可能的更好的解决方案。它相当于一个具有完美散列函数的散列表。

 s 
     | 
     t 
    / \ 
    o  a 
    |  | 
(p,42) r 
     | 
     (t,69)

它会给你相应的你在O（1）最大10次迭代（字符串的最大长度）的字符串值，将最大限度地减少存储密钥的空间成本。

来源

2010-09-22 13:18:34 log0

以下是有关的hash_map，其中一个简易替换提出的表现的文章，应该执行好得多：

http://www.codeproject.com/KB/cross-platform/BenchmarkCppVsDotNet.aspx

经历了std_ext :: PERFO的hash_map当超过25000个元素时，这些元素的表现并不理想，随着元素数量的增加查找速度变慢。更改为boost :: unordered_map解决了问题。

来源

2011-07-05 11:28:57

感谢您的信息！ – skimobear 2011-07-09 13:10:03

由于性能原因，替代stdext :: hash_map

回答

相关问题