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

问题描述

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

一个向量，并通过符号检查给定的符号名称是否匹配。

然后我通过使用地图，在我的情况下 map< string，symbol> 通过向量但：

这个部分有点难以解释，但我会尝试。

如果一个变量是第一次在我的语言的程序中检索，当然，它在符号表中的位置必须找到（现在使用向量）。如果我每次在执行该行时都会迭代遍历该向量（想想一个循环），这将是非常慢的（因为它目前是，几乎和微软的批处理一样慢）。

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

但是想到以下情况：如果变量，仍然使用向量，是第一次找到，我可以存储它的精确的整数位置在向量与它。这意味着：下次需要它时，我的解释器知道它已经缓存，并且不搜索符号表，但是执行类似 SymbolTable.at（myVar.CachedPosition）。

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

• 我应该为符号表使用向量，同时缓存向量中变量的位置吗？




• ？为什么？ []运算符有多快？




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

$ b

解决方案

您实际上有多种选择。

存在库：

• Loki::AssocVector ：在向量上实现的映射的接口，比用于小型或冻结集合的映射快，因为的缓存位置。


• Boost.MultiIndex ：同时提供使用快速查找列表以及实施 MRU列表（最近的
  
  $ b $ b
  
  
  • 地图查找和检索需要 O（log N），但是项目可能分散在整个内存中，
  
  
  • 向量是更容易缓存的，但是除非你排序，你会有 O（N） 找到，是否可以接受？
  
  
  • 为什么不使用 unordered_map ？它们提供 O（1）查找和检索（尽管常数可能很高），并且肯定适合于此任务。如果您查看维基百科的哈希表文章，您会发现有很多策略可供选择，您可以选择
  
  
  
  

  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.

  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.

  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).

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

  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.

  Libraries exist:

  • 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.

  Critics

  • 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地图vs矢量速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！