在字典中维护数据局部性<>



我正在制作一个游戏,出于原因,我决定为每个游戏对象提供一个int实体ID,我可以轻松地搜索它们,而不必线性搜索列表或更糟糕的是,许多列表。这个想法的灵感来自 ECS 模式,我想如果我确保在 int 被销毁时重用它们,这将有助于将所有数据在内存中保持紧密并减少一点缓存未命中。(我知道这更多地取决于访问顺序,只是在这里抽象地思考(。问题是我现在怀疑自己,我已经读了很多东西,以至于我无法在脑海中保持这些想法。

问题本质上是,如果我不断向Dictionary<int, SomeClass>添加更高编号的键,速度/内存使用量会比我尝试重用较低编号更差吗?

注意:我觉得答案将是"编写自己的类",但我试图避免这种情况,如果我不理解这个概念,我认为我不会做得很好。

不,这根本没有区别。从 MSDN:

字典泛型类提供从一组键到一组值的映射。字典中的每个添加项都包含一个值及其关联的键。使用值键检索值非常快,接近 O(1(,因为 Dictionary 类是作为哈希表实现的。

因此,速度将始终为 O(1(,因为它在内部使用哈希表,键的值根本不影响它。

你可以面对的唯一问题是,如果你达到int.MaxValue,这取决于你的场景。

好的,这是我自己尽力回答这个问题,如果我弄错了,请道歉。

简短的回答:不可以。如果你添加更高的数字,它们只会卡在数组的某个地方,直到它被填满。示例问题的解决方案是用GameObject数组替换字典并使用 int 作为索引,并在必要时编写一个类来处理扩展它。

更长的答案:我认为我的困惑来自于在某处读到字典只是一对并行数组或类似的东西。我想这是真的,但由于它是通过哈希代码索引的,因此它不适用于连续的索引值。所以它正在做一堆多余的工作来处理我永远不会使用它的情况。

最新更新