列表<>循环优化

Question

我有一个项目需要处理大量相同类型的对象。

现在我使用 List<Person>，但是当我有大约 1 000 000 个项目时，循环遍历此列表似乎很困难。

在循环中，每个Person都有一个方法被调用，并且有随机生成的新项目，也有一些项目被删除。

我可以做些什么来优化这个 loop？我应该更改集合类型，还是将项目移动到数据库？

这是循环的样子：

while (_worldIsLiving)
{
    int beginningPopulation = WorldPopulationNumber;

    for (int i = 0; i < beginningPopulation; i++)
    {
        _worldPopulation[i].InvokeSkills(this);
    }

    // Remove dead persons
    for (int i = 0; i < WorldPopulationNumber;)
    {
        if (_worldPopulation[i].IsDead()) _worldPopulation.RemoveAt(i);
        else i++;
    }

    WorldCycles++;
    if (_hasStopCondition && (WorldPopulationNumber >= WorldMaximumPopulation || WorldPopulationNumber == 0))
        Destroy();
}

在_worldPopulation[i].InvokeSkills(this);中可以生成新人物。

技能有一个 chanceToBeInvoken 和 chanceTobeInherited 字段。

Answer 1

列表中的

_worldPopulation.RemoveAt(i) 将是一项昂贵的操作。

它涉及将每个后续项目按位置分流。您在外循环的每次迭代中多次调用此方法，每个 "dead" 实例调用一次。

对于长列表来说，这将增加非常大的开销，复杂度为 O(n²)（如果我今天的 CS 帽子正确佩戴的话）。

写一个新列表可能会快得多：

_worldPopulation = _worldPopulation.Where(p=>!p.IsDead())

如果这看起来仍然很昂贵，那么删减列表是否重要？（该列表能否包含所有活着和死去的人口成员，或者这会占用可用内存吗？）

例如，您可以：

var livingPopulace = _worldPopulation.Where(p => !p.IsDead());
foreach(var pop in livingPopulace)
{
    pop.InvokeSkills(this)
}
var newPopulationCount = _worldPopulation.Count(p => !p.IsDead());

虽然这需要对集合进行 2 次扫描，但与使用 RemoveAt 相比，它仍然会减少对集合的遍历，尤其是在每个循环的死亡率很高的情况下。你又回到了 O(n) 的复杂性，我怀疑对于一个大的集合，这将比使用 RemoveAt.

更有效

如果这些都不令人满意，您可以考虑使用 LinkedList<T> 作为容器，它支持简单的前向迭代和低成本移除（以随机访问索引为代价），但可能还有其他使这不切实际的限制。您提供的代码中没有任何内容表明这行不通。只是不要被 ElementAt 等 Linq 运算符诱惑来绕过随机访问限制，否则您将回到同样的问题。

列表<>循环优化

List<> looping optimization

c#

collections

parallel-processing

optimization

large-data