替代stdext ::由于性能原因的hash_map [英] Alternative to stdext::hash_map for performance reasons

问题描述

我工作的一个高性能的应用程序，其中的所有调用必须说明理由。我有一个使用一次在每个事务开始这样做，我想加以改进查找地图。地图被加载在启动后不改变。

I'm working on a high performance application where all calls must be justified. I have a map that is used once in the beginning of each transaction to do a lookup that I would like to improve upon. The map is loaded at startup and does not change after that.

在地图下方的关键是一个std :: string的，但它可以根据需要将其更改为一个字符数组。 C或C ++作为一个解决方案是好的。

The key in the map below is an std::string but it can it changed to a char array if needed. C or C++ as a solution is fine.

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

有谁知道这将消除查找或更快的任何其他解决方案？

Does anyone know of any other solutions that would eliminate the lookup or be faster?

由于提前对您有所帮助。

Thanks ahead of time for your help.

从编辑附加信息：结果
1.目前的hash_map有350000元。结果
2.每个键值长度通常为4个字符和10之间。结果
3.信息收到回调从第三方API。回调给做一个地图上查找时所使用的密钥值的符号。该软件的其余部分被驱除从地图查找返回的是int。

Additional info from edits:
1. The hash_map currently has 350,000 elements.
2. Each key value is typically between 4 and 10 characters in length.
3. Information is received on a callback from a third party API. The callback is given a symbol that is used as the key value when doing a the map lookup. The rest of the software is driven off of the int returned from the map lookup.

感谢：感谢所有为您的输入。你给了我几个途径进行探索。我一定会尝试这些了。我AP preciate的帮助。

THANKS: Thanks all for your input. You've given me a few avenues to explore. I will definitely try these out. I appreciate the help.

推荐答案

一个哈希表通常是足够快的O（1），我们不能告诉你，如果你可以不知道你的应用程序的整体结构摆脱了哈希表。它可能是不可能的。

A hash table is usually fast enough O(1) and we cannot tell you if you can get rid of the hash table without knowing the whole structure of your application. It may not be possible.

我不知道如何实施 stdext ::的hash_map＆LT;的std ::字符串，T＆GT; ，而是一个的 preFIX树是一个可能的更好解决方案。它相当于一个哈希表具有完美哈希函数。

I don't know how is implemented stdext::hash_map<std::string,T> , but a prefix tree is a possibly better solution. It is equivalent to a hash table with a perfect hash function.

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

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

It will give you the value corresponding to your string in O(1) maximum 10 iterations (max length of the string) and will minimize the space cost of storing keys.

这篇关于替代stdext ::由于性能原因的hash_map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！