当试图查找某个范围内不存在的值时，查询是否比for循环更快

本文关键字：是否 查询 for 循环 查找 不存在 范围内 | 更新日期: 2023-09-27 18:23:54

我有一个方法，它应该考虑一个类的实例集合，并找到第一个没有作为属性出现在这些实例中的正数。

以下是我的情况：我有一个名为GestorePersonale（一个员工管理器类）的类，它管理Dipendente（一个雇员类）实例的List。每个Dipendente具有一个ID，该ID必须在List中存在的Dipendente的所有其他实例中是唯一的。

创建新的Dipendente时，我必须找到一个唯一的ID来分配给它。
对于此任务，我首先找出列表中所有实例中最高的ID（Matricola），然后循环从0到该ID的所有数字，试图找到一个间隙ID用于新的Dipendente。如果所有其他操作都失败，我将只分配一个对应于max + 1的ID。

以下是方法MatricolaMax()，它负责返回List中所有实例之间的最高ID（我发布此代码只是为了清楚起见，它不是问题关注的部分，尽管这里也非常感谢任何改进性能的建议）:

private uint MatricolaMax ()
{
    // Looking for the highest ID
    return dipendenti.OrderByDescending( dipendente => dipendente.Matricola ).First().Matricola;
}

这是这个问题的标题所指的方法：

private uint MatricolaLibera ()
{
    var max = MatricolaMax();
    for ( uint i = 0; i < max; i++ )
    {
        var conto = dipendenti.Where( dipendente => dipendente.Matricola == i ).Count();
        if ( conto == 0 )
            return i;
    }
    return max + 1;
}

正如您在上面的代码中所看到的，为了找到间隙ID，我使用Where查询来检查是否存在具有与i对应的Matricola（ID）的Dipendente实例。

如果我使用for循环而不是查询来完成这项工作，这将是我要写的代码：

private uint MatricolaLibera ()
{
    var max = MatricolaMax();
    bool found;
    for ( uint i = 0; i < max; i++ )
    {
        found = false;
        for( int j = 0; j < dipendenti.Count; j++)
            if ( dipendenti[j].Matricola == i )
            {
                found = true;
                break;
            }
        if ( !found )
            return i;
    }
    return max + 1;
}

基本上添加了内部CCD_ 17循环和布尔检查以查看是否找到了空闲ID。

我想问你的问题如下：

给出的两种方法（查询与内部for循环）中哪一种性能最好？是否存在更好的解决方案

当试图查找某个范围内不存在的值时，查询是否比for循环更快

当然，正如Eric所说，您应该运行代码来回答哪个性能更好的问题。（但它应该在与你在实际使用中看到的尺寸相似的尺寸上运行，而不仅仅是小尺寸。）

我建议：

您的MatricolaMax方法正在对列表进行排序，以查找最高值。排序的最小值是O（n*logn），而简单地枚举列表并比较值将是O（n）。

两个MatricolaLibra函数都在遍历每个可能值的整个集合。这是O（n*m）。我建议浏览一下这个列表，把每个键都放在字典里，然后枚举字典，找到第一个不存在的。这应该快得多。

Eric Lippert对您的主要问题有最好的答案，但对于您的"是否有更好的方法问题"，这里有一个答案。

您可以使用整数来保存找到的最高选项，也可以使用布尔数组来保存已使用的值。假设你有一个很好的上限，你可以用一个数组来实现，如果你没有，你将需要根据需要处理数组的增长。然后，您可以简单地枚举您的列表，标记已使用的值，并在需要时更新最大值。如果你不知道上限，或者它可以任意高，那么使用不同的算法。

然而，在这一点上，您看到的是一些非常不平凡的代码（如果不知道上限，这些代码可能会执行得很糟糕），因此，如果您现有的解决方案有效，请使用它们。

相关文章：