c++ - 指针太昂贵了？

Question

我知道这不合适，但我想听听 SO 的意见。

我正在构建一个对象必须相互交互的模拟。因此，为了也跟踪对象与之交互的其他对象，我保留了指向它们的指针。但在我的例子中，一个对象可能必须与大约 15,000 个其他对象交互，因此我最终不得不在每个对象的 vector 中保留 15,000 个指针。我想要至少 10 亿个，希望有更多这样的对象来正确模拟我的问题。

我正在考虑将对象存储在 vector 中，然后仅使用索引来引用该对象。这样我就可以只需要保留 15,000 个 32 位整数的 vector ，而不是存储 15,000 个 64 位指针。

这样做的一个缺点可能是性能会下降，但我愿意为了更大的规模而放弃一些性能？

15 000 是最大值，有时我只需要指向 1000 个对象。

这个问题有更好的解决方案吗？有没有其他人在模拟等方面遇到过类似的问题，你做了什么？

有没有关于在 cpp 中进行大规模模拟的好书/文章等？我还担心缓存、锁定和内存对齐等问题会如何影响我的性能。

感谢您在评论中提出的建议。我想提供有关问题内局部性的更多信息。

一个物体只与它附近的其他物体相互作用，而这个附近是不同的部分。意思是，在更大的空间内有部分。如果一个对象在一个部分中，它只需要与该部分中的其他对象交互。有一些对象跨部分交互，但我忽略了它们。

这似乎是我能给你的唯一相关信息。

Answer 1

An object only interacts with other objects in its vicinity , and this vicinity are different sections . [...] And if an object is within a section , it only has to interact with other objects within that section.

如果一个部分中的每个对象都与同一部分中的所有其他对象交互，您可以只跟踪对象所在的部分。考虑到您没有太多的部分，您可能可以用一个int 每个对象。当您想知道两个对象是否必须相互作用时，比较它们的部分编号。

另一种希望更好的方法可能需要您重新设计模拟。如果对象仅存在于部分中，则让这些部分拥有您的对象。这样，您就不需要为每个对象添加额外的“节号”。考虑交互时，只需一次在一个部分内操作。

此外，as vu1p3n0x said in the comments ，您可能需要考虑使用 quadtrees (或类似的高维树)。这实际上取决于您构建的模拟类型。

There are some object which interact across sections , but I am ignoring them.

有几种方法可以表示跨部分的交互。

一种方法是使它们成为完全不同类型的数据。交互将由两个部分表示，在这些部分中，可以是“边缘”对象列表并且可以跨部分交互，或者是对象对之间的实际交互列表，具体取决于您的模拟。

另一种方法是，在每个部分中，存储可以跨部分交互的不同对象，我们称它们为边界对象。假设每个部分都可以与其他四个部分交互(其中的对象可以交互)。然后，您将对象存储在五个不同的容器中:一个对象不能跨部分交互，我们称它们为中心对象，另一个部分用于边界对象。后四个容器代表该部分的边界。当遍历一个部分的对象时，您首先会像以前一样考虑中心对象。然后，对于每个边框，您考虑其边框对象以及相应部分的边框对象。这假设给定部分中的任何对象都可以与同一部分中的对象或仅与另一个部分中的对象交互。