C ++ STL Map与矢量速度 [英] C++ STL Map vs Vector speed

问题描述

在我的实验编程语言的解释器中，我有一个符号表。每个符号由一个名称和一个值组成（该值可以是例如：string，int，function等）。

In the interpreter for my experimental programming language I have a symbol table. Each symbol consists of a name and a value (the value can be e.g.: of type string, int, function, etc.).

一个向量并迭代通过符号检查给定的符号名称是否合适。

At first I represented the table with a vector and iterated through the symbols checking if the given symbol name fitted.

然后我使用地图，在我的情况下， map< string，symbol> 将比迭代更好通过向量，所有的时间但：

Then I though using a map, in my case map<string,symbol>, would be better than iterating through the vector all the time but:

这很难解释这部分，但我会尝试。

It's a bit hard to explain this part but I'll try.

如果在我的语言程序中首次检索到变量，那么必须找到符号表中的位置（现在使用向量）。如果我每次执行线程时都会遍历向量（想到一个循环），那将是非常慢的（因为它现在几乎和microsoft的批处理相同）。

If a variable is retrieved the first time in a program in my language, of course its position in the symbol table has to be found (using vector now). If I would iterate through the vector every time the line gets executed (think of a loop), it would be terribly slow (as it currently is, nearly as slow as microsoft's batch).

所以我可以使用地图来检索变量： SymbolTable [myVar.Name]

So I could use a map to retrieve the variable: SymbolTable[ myVar.Name ]

但是想到如下：如果变量，仍然使用向量，是第一次找到，我可以存储它的确切的整数位置在它的向量中。这意味着：下次需要时，我的口译员知道它已经被缓存，并且不搜索符号表，但是像 SymbolTable.at（myVar.CachedPosition）。

But think of the following: If the variable, still using vector, is found the first time, I can store its exact integer position in the vector with it. That means: The next time it is needed, my interpreter knows that it has been "cached" and doesn't search the symbol table for it but does something like SymbolTable.at( myVar.CachedPosition ).

现在我的（相当困难的）问题：

Now my (rather hard?) question:

• 我应该使用向量作为符号表，还可以缓存向量中变量的位置吗？

• Should I use a vector for the symbol table together with caching the position of the variable in the vector?

我应该使用地图？为什么？

Should I rather use a map? Why? How fast is the [] operator?

我应该使用完全不同的东西吗？

Should I use something completely different?

推荐答案

您有效地选择了多种替代方案。

You effectively have a number of alternatives.

库存在：

• Loki :: AssocVector ：通过向量实现的地图的接口，比地图快由于缓存区域而导致小型或冻结集。


• Boost.MultiIndex ：同时提供快速查找列表以及实现 MRU List （M最近被使用的）最近访问的元素。

• Loki::AssocVector: the interface of a map implemented over a vector of pairs, faster than a map for small or frozen sets because of cache locality.
• Boost.MultiIndex: provides both List with fast lookup and an example of implementing a MRU List (Most Recently Used) which caches the last accessed elements.

评论

• 地图查找和检索采取 O（log N），但是项目可能会分散在整个内存中，因此无法使用缓存策略。


• 矢量更加缓存友好，不过除非你排序，否则你会有 O（N） O（1）查找和检索（尽管常数可能很高），并且肯定适合于此任务。如果您有关于维基百科的哈希表的文章，您会发现有很多策略可用您可以选择一个适合您特定使用模式的选项。

• Map look up and retrieval take O(log N), but the items may be scattered throughout the memory, thus not playing well with caching strategies.
• Vector are more cache friendly, however unless you sort it you'll have O(N) performance on find, is it acceptable ?
• Why not using a unordered_map ? They provide O(1) lookup and retrieval (though the constant may be high) and are certainly suited to this task. If you have a look at Wikipedia's article on Hash Tables you'll realize that there are many strategies available and you can certainly pick one that will suit your particular usage pattern.

这篇关于C ++ STL Map与矢量速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！