2

语境

我有这样的代码：

..
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;)，但为简单起见，我在上面使用了向量。

我在装满之前知道每个桶的大小。

向量的大小约为 2,000,000,000。

问题

如您所见，上面的代码以随机方式访问“buckets”数组。因此，它有不断的缓存未命中，从而大大减慢了执行时间。是的，我在个人资料报告中看到了这样的失误。

问题

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

我试图创建一个辅助向量并将第一次出现的值放在那里，因此我可以将两个索引放在相应的存储桶中，因为我找到了第二个。这种方法没有任何加速。

谢谢！

4

2 回答 2

0

您为什么假设缓存未命中会使您的代码变慢？你有没有介绍过，或者这就是你想到的？

从性能的角度来看，您的代码有很多问题。第一个也是最明显的一点是你从不保留向量大小。发生的事情是您的向量开始时​​非常小（例如，2 个元素），然后每次添加超过大小时，它都会再次调整大小并将内容复制到新的内存位置。如果您说有 20亿个条目，那么您可能会调整大小 30 次！

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

编辑

严重地？你提到你甚至没有在你的 PS 中使用矢量？我们应该如何猜测您的实际代码是什么样的以及它将如何执行？

于 2012-05-13T08:56:10.723 回答
0

对于给定的间隔foo，至少是可逆的和满射的吗？然后，您可以运行该区间并buckets[j]完全填充bar(j,k)（如果bar是 的倒数foo），对于kin [0,...,MAX_BAR_J)，然后继续，j+1依此类推。

但是，如果foo具有散列属性，那么您的机会就很小，因为您无法预测下一个i将获得哪个索引。所以我现在看不到机会。

于 2012-05-13T09:09:00.400 回答