C++ STL Map与Vector的速度比较

Question

在我的实验性编程语言解释器中，我有一个符号表。每个符号由名称和值组成（值可以是字符串、整数、函数等类型）。

起初，我用向量表示表格，并通过迭代符号来检查给定的符号名称是否匹配。

然后我想使用映射，在我的情况下是`map`，比一直迭代向量更好，但是：

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

如果在程序中第一次检索变量，当然必须找到其在符号表中的位置（现在使用向量）。如果每次执行该行时都要遍历向量，那么速度会非常慢(目前几乎和Microsoft的批处理一样缓慢)。

所以我可以使用映射来获取变量：`SymbolTable[ myVar.Name ]`

但请考虑以下内容：如果使用向量，第一次找到变量时，我可以将其精确的整数位置存储在向量中。这意味着：下次需要它时，我的解释器知道它已被“缓存”，不会搜索符号表，而是做类似于这样的操作：`SymbolTable.at( myVar.CachedPosition )`。

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

• 我应该使用带有在向量中缓存变量位置的向量作为符号表吗？

• 还是应该使用映射？为什么？[]运算符有多快？

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

- sub

---

只是一些值得思考的事情，如果您存储了变量所在的整数位置以及之前某个被垃圾回收或删除的变量，那么您对于该整数位置缓存有什么计划？ - Blindy

Answer 1

使用映射表作为符号表是一个好主意，但是对于映射表来说，operator[]并不是一个好的选择。通常情况下，除非你正在编写一些简单的代码，否则你应该使用映射表的成员函数insert()和find()，而不是operator[]。 operator[]的语义有些复杂，如果你要查找的符号不在映射表中，它几乎肯定不会做你想要的事情。

至于选择map和unordered_map之间的区别，在实现简单的解释性语言时，性能差异极不可能显著。如果你使用map，你可以确保它将被所有当前的标准C++实现支持。

- anon

---

要将符号“缓存”，只需存储std::map :: find（）返回的迭代器，而不是从std::vector中存储该符号的位置。 - moatPylon

Answer 2

您有多种选择。

存在以下库：

• Loki :: AssocVector：在一组成对的vector上实现映射的接口，因缓存局部性而对于小型或冻结集比映射更快。
• Boost.MultiIndex：提供了带有快速查找的列表和实现MRU列表（最近最少使用）的示例，可缓存最后访问的元素。

评论家

• 查找和检索地图需要O(log N)，但是项目可能分散在内存中，因此无法很好地与缓存策略配合。
• 向量更有利于缓存，但是除非您对其进行排序，否则在find上将具有O(N)的性能，这可以接受吗？
• 为什么不使用unordered_map？它们提供O(1)的查找和检索（尽管常数可能很高），并且肯定适合此任务。如果您查看维基百科关于哈希表的文章，您将意识到有许多可用的策略，并且肯定可以选择适合您特定使用模式的策略。

- Matthieu M.

---

如果你保持向量排序（插入时有惩罚），那么查找操作的性能将为O(log N)。 - Randy the Dev

我的向量已经排序，如何实现 O(log N) 的性能？ - John

@John：你需要使用二分查找算法。在C++中，可以使用std::lower_bound和std::upper_bound算法来实现（两者都可以）。 - Matthieu M.

@Matthieu M. 似乎std::vector ::lower_bound比std::map::find慢，即使数据集很小（300~5000）。这真的是非常意外。我在两小时前在Ubuntu上进行了这些测试。你对此有何看法？ - John

@John：我认为你需要提出一个明确的问题，并展示你的代码、编译器和编译器设置等等……这确实是令人意外的。 - Matthieu M.

Answer 3

通常情况下，你会使用符号表来查找变量，根据其在源代码中出现的名称进行查找。但是在这种情况下，你只有名称可用，因此没有地方存储变量在符号表中的缓存位置。因此，我认为使用 map 是一个不错的选择。 [] 运算符的时间复杂度与 map 中元素数量的对数成比例 - 如果速度变慢，你可以使用哈希映射，如 std::tr1::unordered_map。

- Mike Dinsdale

---

你不了解我的代码，我有一个非常好的选项来存储位置，请相信我。 - sub

然后存储一个指针（例如 symbol*），并完全绕过容器查找。 - Ben Voigt

你可以将位置存储在解析树或其他中间表示中，但如果你像Tronic在他/她的答案中所说的那样使用map，也可以做到同样的事情。最大的区别就是查找变量名所需的时间。（实际上，如果您想序列化数据结构，还会出现其他问题，但我将在此停止猜测您的代码；） - Mike Dinsdale

Answer 4

std::map的operator[]需要O（log（n））时间。这意味着它相当高效，但仍然应该避免反复查找。您可以存储值的引用或容器的迭代器，而不是存储索引吗？这样可以完全避免查找。

- Tronic

Answer 5

当大多数解释器解释代码时，它们首先将其编译成中间语言。这些中间语言通常通过索引或指针引用变量，而不是通过名称。

例如，Python（C实现）将本地变量更改为通过索引引用，但全局变量和类变量使用哈希表按名称引用。

我建议查看一些编译器的入门文本。

- Dietrich Epp

Answer 6

使用std::map（O(log(n)）或哈希表（“摊销”O(1)）将是首选 - 如果您确定它是瓶颈，则使用自定义机制。通常，使用哈希或对输入进行标记是第一个优化。

在对其进行性能分析之前，最重要的是隔离查找，以便您可以轻松地替换和分析它。

---

std::map 对于少量元素可能会稍微慢一些（但是，这并不重要）。

- peterchen

Answer 7

Map的时间复杂度为O(log N)，因此不如在数组中进行位置查找快速。但是确切的结果将取决于很多因素，因此最好的方法是以一种允许您稍后在实现之间进行切换的方式与容器进行接口交互。也就是说，编写一个“lookup”函数，可以通过任何合适的容器高效实现，以便允许您切换并比较不同实现的速度。

- Daniel Earwicker

Answer 8

Map的操作符[]的时间复杂度为O(log(n))，参见维基百科：http://en.wikipedia.org/wiki/Map_(C%2B%2B)。

我认为，如果你经常需要查找符号，使用map肯定是正确的选择。也许哈希映射（std::unordered_map）可以提高性能。

- Klaim

Answer 9

如果你要使用一个vector并且费心地缓存最近的符号查找结果，那么如果你的符号表是用map实现的，你也可以做同样的事情（缓存最近的查找结果），但在使用map的情况下，缓存可能不会有太多好处。使用map的另一个优点是，任何未缓存的符号查找都比在vector中搜索要快得多（假设vector没有排序——如果你不得不多次进行排序，保持向量排序可能很昂贵）。

采纳Neil的建议；map通常是符号表的一个很好的数据结构，但你需要确保正确使用它（不要意外添加符号）。

- Michael Burr

Answer 10

你说：“如果变量仍然使用向量，并且第一次找到它，我可以将其精确整数位置与向量存储在一起。”

你也可以用map来做同样的事情：使用 find 搜索变量并存储指向它的迭代器，而不是位置。

- baol