2

因此，我花了很多时间阅读各种问题、博客文章、文章等，了解不同 STL 容器在不同情况下的性能比较。

但是，我还没有为我的确切情况找到一个好的来源（3D 游戏）：

我正在收集大量（肯定超过 5k，可能低于 50k）指向某个类的指针（我认为它的确切性质不相关）并希望通过一个浮点值对它们进行排序，该浮点值确定它们到某个任意位置的距离（在帧期间不会改变）。

之后，我想遍历每个存储的指针。顺序在这里很重要，因此排序。

这是伪代码中的情况：

// A: Insertion
foreach (class instance that needs sorting):
    container.insert( pair(distanceOfInstance, instance) );

// B: Sorting - using the distanceOfInstance as the determining factor
container.sort();

// C: Iteration in sorted order
foreach (pair in container)
    doSomethingWith(pair.instance);

整个过程（可能）在游戏中的每一帧都重复，所以这里的最佳性能有点重要。每次都必须在A之前清空容器。在C之后，什么都没有做。

我不需要的（我重复一遍，NOT）需要：

  • 随机访问容器。
  • 容器排序后插入新元素的能力。

目前，我认为最快的是使用向量或集合。但我不知道 - 在我的情况下 - 将元素插入向量中，然后对其进行排序，然后对每个元素进行一次迭代会更快。或者如果将元素插入集合（因此在插入期间对它们进行排序）然后迭代每个元素一次会更快。

我们还在我们的项目中将 boost 用于其他一些任务，所以如果有人知道 boost 内部更好的解决方案（或完全其他的解决方案），我非常愿意提供建议。另外，很抱歉，如果这个问题已经得到回答，我只是没有找到它:)

4

5 回答 5

2

向量在实践中几乎总是更快；如果您不需要将更新与查找交错，那么没有理由1使用set.

也就是说，你也可以看看 Google 的B-tree implementation，它应该比 set 更快。

1 也就是说，除非您还要检查和删除重复项，否则会有很多重复项。
（这并不常见。）

于 2013-10-25T08:59:06.907 回答
1

如果您只需要对元素进行一次排序，我认为如果您使用矢量，您将获得更好的性能。您也可以考虑使用列表，尽管我认为它会比向量稍微慢一些。

于 2013-10-25T08:44:58.090 回答
1

性能总是很棘手：您应该以两种方式实现它并衡量哪一种能提供更好的输出。

也就是说，如果你在创建时保留足够的元素，我认为 vector 会是一个更好的选择：如果你使用 set，新插入的元素将在每次插入时排序到集合中。使用矢量，您只会一次性产生该成本。

于 2013-10-25T08:47:35.147 回答
1

如其他答案所述，应在您的情况下使用向量。关于时间复杂度，对向量进行排序需要时间O(n log n)，其中n是您插入的元素数。对于，已排序的序列以每次插入的O(log n)std::set为代价。插入n 个元素也会导致O(n log n)运行时间。但是由于更好的内存局部性，向量解会更快（简而言之，它存储在一个连续的内存范围内，可以快速读写）。

此外，std::vector只有恒定的空间开销，而std::set具有线性开销（通常实现为Rb-tree）。

如果您有多次迭代并且n很大，请避免在每次迭代中分配向量的内存。所以而不是

while (true) {
  vector<YourClass*> container;
  container.reserve(numInstancesInCurrentIteration);
  // your code, insertions with 'container.emplace_back(...)'
}

做类似的事情：

vector<pair<float, YourClass*> > container;
while (true) {
  if (container.size() < numInstancesInCurrentIteration)
    container.resize(numInstances, pair<float, YourClass*>(-1.f, NULL));

  // A: Insert using assignments
  size_t pos = 0;
  foreach (class instance that needs sorting):  // pseudo-code
    container[pos++] = make_pair(distanceOfInstance, &instance);

  // B: Sort only the used range
  std::sort(container.begin(), container.begin() + pos);

  // C: Iterate over pointers sorted by distance
  for (auto it = container.begin(); it != container.begin() + pos; ++it)
    doSomethingWith(it->second);
}

经过一些迭代后，调用container.resize()将变得非常罕见。的调用doSomethingWith(YourClass*)可能会成为程序中最昂贵的部分。

于 2013-10-28T18:45:59.033 回答
0

正如其他人回答的那样，我也会选择矢量。它更简单，并且可以更多地访问对象的内存布局。

于 2013-10-28T19:09:32.007 回答