c++ - 选择性能最高的容器(阵列)

Question

这是我关于容器的小大问题，尤其是数组。

我正在编写一个物理代码，主要操纵一大组(> 1 000 000)“粒子”(每个粒子有 6 个 double 坐标)。我正在寻找最佳方式(在性能方面)来实现一个类，该类将包含这些数据的容器并为这些数据提供操作原语(例如实例化、operator[] 等)。

这个集合的使用有一些限制:

• 它的大小是从配置文件中读取的，在执行过程中不会改变
• 可以看做是一个N(比如1000000)行6列(每列存储一维坐标)的二维大数组
• 数组在一个大循环中进行操作，访问每个“粒子/线”并使用其坐标进行计算，并为该粒子存储结果，以此类推每个粒子，以此类推大循环的迭代。
• 执行过程中没有添加或删除新元素

第一个结论，因为对元素的访问基本上是通过使用 [] 一个一个地访问每个元素来完成的。 ，我认为我应该使用普通的动态数组。

我已经探索了一些东西，我想听听你对哪一个能给我最好的表现的意见。

据我所知，使用动态分配的数组而不是 std::vector 没有任何优势。 , 所以像 double** array2d = new ..., loop of new, etc 这样的东西被排除。

那么使用 std::vector<double> 是个好主意吗？ ？

如果我使用 std::vector , 我应该创建一个像 std::vector<std::vector<double> > my_array 这样的二维数组吗？可以像my_array[i][j]一样被索引, 或者这是一个坏主意，最好使用 std::vector<double> other_array并使用 other_array[6*i+j] 访问它.

也许这可以提供更好的性能，尤其是因为列数是固定的并且从一开始就已知。

如果您认为这是最佳选择，是否可以将此 vector 包装成可以使用定义为 other_array[i,j] // same as other_array[6*i+j] 的索引运算符访问的方式？没有开销(比如每次访问时的函数调用)？

另一个选项，我目前使用的选项是使用 Blitz，特别是 blitz::Array :

typedef blitz::Array<double,TWO_DIMENSIONS> store_t;
store_t my_store;

像这样访问我的元素的地方:my_store(line, column); .

我认为在我的案例中使用 Blitz 没有太多优势，因为我正在一个接一个地访问每个元素，如果我直接在数组上使用操作(如矩阵乘法)，Blitz 会很有趣，而我不是。

您认为 Blitz 还可以，还是对我没用？

这些是到目前为止我考虑过的可能性，但也许我还有一个是最好的，所以请不要犹豫向我建议其他事情。

非常感谢您对这个问题的帮助!

编辑:

从下面非常有趣的答案和评论来看，一个好的解决方案似乎如下:

• 使用结构particle (包含 6 个 double )或 6 个 double 的静态数组(这避免使用二维动态数组)
• 使用 vector或 deque这个 particle结构或数组。然后最好用迭代器遍历它们，这将允许以后从一个更改为另一个。

此外我还可以使用 Blitz::TinyVector<double,6>而不是结构。

Answer 1

So is it a good idea to use std::vector<double> ?

通常，一个 std::vector应该是容器的首选。您可以使用 std::vector<>::reserve()或 std::vector<>::resize()以避免在填充 vector 时重新分配。是否有其他容器更好，可以通过测量来发现。而且只能通过测量。但首先要衡量容器涉及的任何事情(填充、访问元素)是否值得优化。

If I use a std::vector, should I create a two dimensional array like std::vector<std::vector<double> > [...]?

没有。 IIUC，您正在访问每个粒子的数据，而不是每行。如果是这样，为什么不使用 std::vector<particle> , 其中particle是一个包含六个值的结构吗？即使我理解不正确，您也应该在一维容器周围编写一个二维包装器。然后将您的数据按行或按列对齐 - 使用您的访问模式可以更快。

Do you think that Blitz is OK, or is it useless in my case?

我对 blitz++ 及其使用领域一无所知。但是 blitz++ 不就是关于表达式模板以展开循环操作并在进行矩阵操作时优化掉临时变量吗？ ICBWT。