5

我最近发现了面向数据设计的好处。它看起来非常令人印象深刻。要点之一是按类型和访问对数据进行分组，而不是全部放在对象中，而是放在数组中，以防止缓存未命中并进行更好的处理。

所以在游戏中我们仍然有实例并且用户可以销毁它们中的任何一个（不仅仅是最后一个数组）。我不知道如何有效地处理数组中间的对象删除。

我有一个想法：isAlive有价值，但这会对条件数量造成相当大的影响，因为每个对象在处理，绘图，...

另一个想法是移动整个数组以填充必须删除的空间，但这会在删除时消耗大量资源。

人如何在国防部处理这个问题？

所以提出要求：

  • 它必须是数组以减少 DOD 中的缓存未命中
  • 它必须有快速的随机位置对象删除，最大 o(log n)
  • 对象自创建以来就不能移动，因为它们可能在未知的地方被引用，因此会导致程序异常
4

2 回答 2

5

这实际上很容易，不要使用直接引用。使用一个间接层，例如 ID。例如：

假设您有一个 FooManager 来管理您的所有 Foo “对象”（不是 OOP 意义上的对象，每个 Foo 属性的数组集合）。据我了解，您现在所做的只是返回一个索引。假设 Foo #42 是 Foo ，其数据位于所有数组的索引 42 处。现在你想删除 Foo #42，这会在你的数组中炸出一个洞。您可以移动所有其他数组条目，但 Foo #43 不再指向实际索引 43。

因此，我们添加了一个 ID 表，而不是返回索引，而是返回一个 ID。当您创建一个新的 Foo 时，您将其数据添加到数组中的第一个空闲索引（比如说 42）。然后生成一个新的未使用 ID（比如 1337）。现在您可以更新 ID 表（（散列）映射非常适合此操作）以说 ID 1337 指向索引 42。现在您可以将 ID 1337 返回给调用函数。（注意调用函数永远不会找到数据的实际存储位置，这是不相关的信息）

下次需要从另一段代码更新 Foo 时，将使用 ID。因此 FooManager 的 setBar 函数以 ID 1337 和新的 Bar 值作为参数调用。FooManager 在其 ID 表中查找 1337，发现它仍然位于索引 42 并使用新的 Bar 值更新 Bar 数组索引 42。

现在这是这个系统获得它的价值的地方，让我们删除 Foo 1337。FooManager 的 removeFoo 以 ID 1337 作为参数调用。它查找 1337，它位于索引 42。但是，与此同时，添加了 10 个新的 Foo。所以我们现在可以做的就是将索引 42 的值替换为 52 的值，有效地将 52 移动到 42。这在旧系统中会造成很大的问题，但是现在，我们只需要更新索引表即可。所以我们查找哪个 ID 指向 52（假设它是 1401）并将其更新为 42。下次有人尝试更新 ID 为 1401 的 Foo 时，它会在索引表中查找它并发现它位于索引 42 处。

所以我们将数据保存在连续内存中，删除只需要非常少的数据复制操作（Foo 的每个属性一个副本），而 FooManager 的“外部”代码甚至从未意识到发生了什么事。它甚至可以解决死引用问题。假设某些代码仍然具有已删除的 1337 ID（悬空引用，这很糟糕！），当它尝试访问/更改它时，FooManager 查找它，看到 1337 不存在（不再存在）并且可以生成一个很好的干净警告/error 和 callstack，它允许您直接识别哪些代码仍然有悬空引用！

只有一个缺点，那就是在 ID 表中的额外查找。现在哈希表可以非常快，但是每次修改 Foo 对象时它仍然是一个额外的操作。但是，在大多数情况下，来自管理器外部的访问远远少于管理器内部的访问。当你有一个 BulletManager 时，它会在每一帧更新每个项目符号，但访问项目符号以更改/请求某些内容以及创建/删除项目符号的调用不太可能发生。如果这是相反的情况，您可能应该更新您的数据结构以针对这种情况进行优化。再说一次，在这种情况下，数据在内存中的位置不再重要，因此您可以忍受数组中的“洞”，甚至使用完全不同的数据布局。

于 2013-02-20T14:48:08.043 回答
0

它取决于约束和工作量，但一种方法是将已删除的元素与数组中的最后一个元素交换，然后从末尾删除已删除的元素 ( pop_back)。这假设数组的顺序不是特别重要。另一种方法是稀疏数组，它可能在内存预算固定的环境中工作。

编辑：如果您要维护指向数组的外部指针，则可以使用智能指针来管理它们，其基础地址在shared_ptr::reset移动数组元素时更新（）。你最终会得到 2 个相同长度的并行数组：

typedef std::vector<thing> thingVec;
thingVec things;

// smart pointers for each object
std::vector<boost::shared_ptr<thingVec::iterator>> references;

在您的createThing函数中，您将返回shared_ptr带有自定义删除器的 a （一旦所有引用都已消失，它将自动执行数组更新）：

http://www.boost.org/doc/libs/1_51_0/libs/smart_ptr/sp_techniques.html#static

智能指针可以指向具有多个字段的结构，这些字段最终存储在不同的数组中，只要自定义删除器知道在删除元素时要压缩哪些数组。

于 2012-10-06T19:31:19.253 回答