如何加速非顺序数组的填充？

Question

上下文

我有这样的密码：

..
vector<int> values = ..., vector<vector<int>> buckets;
//reserve space for values and each buckets sub-vector
for (int i = 0; i < values.size(); i++) {
  buckets[values[i]].push_back(i);
}
...

因此，我得到了一个具有相同值的条目索引的“桶”。然后在进一步的处理中使用这些桶。

实际上，我正在使用本机动态数组(int ** buckets;)，但为了简单起见，我使用了上面的向量。

我知道每个水桶的大小，然后再填。

向量的大小约为20亿。

问题

正如您所看到的，上面的代码以一种随机的方式访问“桶”数组。因此，它有常量的缓存丢失，大大降低了执行时间。是的，我在侧写报告中看到了这样的失误。

问题

有没有办法提高这类代码的速度？

我尝试创建一个辅助向量，并将值的第一个出现在那里，这样我就可以在相应的桶中放入两个索引，就像我发现的第二个索引一样。这种方法并没有加快速度。

谢谢！

Answer 1

为什么假设是缓存丢失导致代码变慢？你有没有描述过，或者这就是你想要的？

从性能的角度来看，您的代码有许多非常错误的地方。第一个也是最明显的是，你从来没有保留一个向量大小。正在发生的情况是，您的向量开始非常小(例如，2个元素)，然后每次添加超过大小时，它都会重新调整大小，并将内容复制到新的内存位置。如果你说有20亿个条目，你可能会调整30倍！

在查看其他改进之前，您需要调用函数vector.reserve() (或vector.resize()，取决于哪些行为对您最适合)。

编辑

我是认真的?你说你甚至没有在你的PS中使用向量？我们应该如何猜测您的实际代码是什么样的，以及它将如何执行？

Answer 2

在给定的区间内，foo至少是可逆的和满射的吗？然后，您可以运行该间隔，并将buckets[j]完全填充为bar(j,k) (如果bar与foo相反)，对于[0,...,MAX_BAR_J)中的k，然后继续使用j+1等等。

但是，如果foo具有散列属性，则可能性很小，因为您无法预测下一个i将得到哪个索引。所以我现在没机会了。