List<比;循环优化

本文关键字：循环 优化 List | 更新日期: 2023-09-27 18:12:36

我有一个项目，该项目使用大量相同类型的对象。

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

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

如何优化循环 ?我应该更改集合类型，还是将项移动到数据库中?

循环是这样的:

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);中可以生成新的人员。

Skill有chanceToBeInvoken和chanceTobeInherited字段

List<比;循环优化

_worldPopulation.RemoveAt(i)对列表的操作将是一个开销很大的操作。

它涉及将每个后续项向下分流一个位置。在外循环的每次迭代中都要多次调用这个函数，对于每个"死亡"实例调用一次。

对于一个长列表来说，这将增加一个非常显著的开销，复杂度为0 (n2)(如果我的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相比，它在集合上的传递次数仍然更少，特别是在每个周期的死亡率很高的情况下。你又回到了0 (n)复杂度，我怀疑对于一个大的集合，这将比使用RemoveAt更有效。

如果这两种方法都不能令人满意，您可以考虑使用LinkedList<T>作为容器，它支持简单的前向迭代和低成本的删除(以随机访问索引为代价)，但可能存在其他限制使其不切实际。您提供的代码中没有任何内容表明这不会工作。只是不要被Linq操作符(如ElementAt)的诱惑来绕过随机访问限制，否则你会回到同样的问题。

相关文章：