原文

说明: 因为图片无法下载，我们就看看结论吧。

介绍

在相当多的应用程序中，我们必须处理稀疏数组或具有整型键的映射。当元素的数量相当少 (比如不超过1000个) 时，使用标准的std::map或std::unordered_map就足够了。当键的数量增加时，这些映射的表现就不那么好了: 我们想要考虑更快的容器。在本文中，我将尝试研究使用整数键实现映射并度量其性能的各种方法。

该代码在 Microsoft Visual C++ 14 CTP和GNU C++ 4.9 中进行了测试。

现有的map容器有问题吗?

现有的std::map和std::unordered_map将元素分散到整个堆中，这将导致对元素的访问非常低效 (由于缓存丢失)，特别是当它们的数量接近100,000时。这显然取决于元素的大小。衡量效率的两个主要标准可以是:

• 随机存取的速度
• 浏览整个列表的速度

另一个标准可能是元素创建和删除的速度。如果我们真的想实现高效的随机访问，我们可以用一个值数组替换map，并使用它的索引作为键。只要满足以下两个条件，就可以正常工作:

• 对于给定的键值范围，有足够的内存空间容纳整个数组。
• 我们要么不需要扫描所有的元素，要么对扫描的速度感到满意，如果值之间有很大的差距，可能就不会很快。

另一种选择是使用平面映射 (flat map)，它不在C++ STL中，但在Boost中可用。平面映射是一个“键-值”对的排序数组，按键排序。平面映射的优点是它提供了按键顺序扫描元素的最快方式。它也是所有map中最紧凑的。但它存在以下问题:

• 随机存取不是那么快。
• 当元素的数量超过100,000时，添加和删除会非常缓慢。

我将尝试考虑一些其他方法，并根据已知的映射容器度量它们的性能。

提议的map容器

Flat Index Map

这个容器试图处理平面映射 (flat map) 的一些缺陷，方法是使用一个额外的std::vector<bool>类型的变量，该变量告诉我们平面映射中是否存在具有给定索引的元素。这种方法提高了随机访问的速度，因为当检查元素是否存在时，算法首先查看这个 vector，如果元素不存在，则无需进一步查看。当映射中有许多缺口 (gap) 时，这可以节省大量的时间。你必须付出的代价是std::vector<bool>的大小，它应该能够包含map中使用的所有可能的索引。

Unordered Index Map

这种映射类似于[2,3,4]中讨论的无序稀疏集。这个映射是用两个数组 (array) 实现的。一种称为密集 (dense) (无间隙)，它包含“索引-值”对。另一个叫稀疏 (sparse)，存在的元素的索引被包含在第二个数组中。规则是:

dense[sparse[i]].first = i

这个map提供了非常快速的扫描设施，因为密集数组 (dense array) 的性质——没有间隙。随机访问也相当快: dense[sparse[i]] 为你提供所需的键值对。这里的缺点是，密集数组的值不是有序的，映射需要大量的内存空间，这大致与映射中使用的索引范围成比例。

Sparse Map

这是一个有序映射，有点类似于无序索引映射 (unordered index map): 它由一个稀疏数组 (sparse array) 和一个密集列表 (dense list) (有序对) 组成。稀疏数组包含指向密集列表的指针 (实现为迭代器)。每次算法试图添加新元素时，都会将其放入密集列表中正确的位置，并在稀疏数组中设置相关的指针: 稀疏数组有助于提高效率。与无序索引映射相比，其优点是它是有序的。

Two-Level Map

两级映射试图通过使用 map-of-maps 方法来解决平面映射 (flat map) 生成的速度问题。在这个实现中，我使用了两个 flat map: 它们是最紧凑的。第一级 map 是第二级 map 的映射 (The first-level map is a map of second-level maps.)。每个二级 map 可以索引范围 [0-4095] 。与 flat map 相比，该 map 提供了更快的映射生成算法。

基准

一般评论

在这些基准测试中，我使用了各种映射 (map)，其中索引的范围是固定的 [0;9999999]。元素的数量在20到10,000,000之间。每个元素由一个无符号键和一个双浮点值组成。

索引的范围影响了一些映射所需的内存大小。std::map、std::unordered_map和平面映射 (flat map) 所使用的内存依赖于索引的可能范围: 它只依赖于映射中实际存在的元素。在某种程度上，这对两级映射 (two-level map) 来说也是如此: 但它增长的速度取决于范围。其他映射的内存使用在很大程度上取决于可能的索引范围。

map 生成

结果如图1所示。你可能会看到，平面映射 (flat map) 和平面索引映射 (flat index map) 的生成速度特别慢。两层映射 (two-level map) 不是最快的，但它设法让它“处于控制之下”。当元素数小于10000时，稀疏映射 (sparse map) 速度较慢，但当元素数增加时，稀疏映射开始超越其他映射。

随机存取

结果如图2所示。这里的“赢家”是: 稀疏映射 (sparse map)、无序索引映射 (unordered index map) 和std::unordered_map。平面索引映射在有很多缺失的时候表现得很好，但是当大部分缺失被填补时就开始变慢。你可能根据印象认为平面索引映射相当快: 当只处理成功命中时，它会很慢。

扫描整个范围的元素

结果的比较如图3所示。每次扫描所花费的时间除以元素的数量: 我们得到每个元素所花费的时间，单位是纳秒。这里的胜出者显然是:平面映射、平面索引映射和无序索引映射，因为它们使用成对的密集数组进行扫描。两层映射也很接近。当元素数量小于10,000时，稀疏映射和无序映射工作得相当好。

删除的元素

在某种程度上，删除映射的速度与生成映射的速度相似。例外是稀疏映射。结果如图4所示。这里最大的“输家”是平面映射和平面索引映射，以及生成速度的情况。

内存使用情况

图5显示了 [0;9999999] 范围内的内存使用情况。这里的“松散者”是稀疏映射、无序索引映射和平面索引映射。

结论

问题是:哪种映射是最好的? 答案并没有那么简单。如果你处理少于1000个元素，我也不会太在意。在这种情况下，平面映射可能是最有效的，而且非常紧凑，此外，它将提供最快的扫描算法。如果范围更大，问题是什么更重要:

• 如果它是随机访问，那么你可以使用 std::unordered_map，稀疏映射或无序索引映射 (三个中只有稀疏映射是有序的);
• 如果扫描更重要，那肯定是两级映射(平面映射的生成速度要慢得多)。