.net - 使用类的谓词搜索通用列表 - 比循环更快？

Question

假设我们有一个 Class1 的通用列表，通常有大约 100 个给定会话的对象。我想看看列表是否有特定的对象。ASP.NET 2.0 允许我这样做：

Dim objResult as Class1 = objList.Find(objSearch)

从性能的角度来看，与传统的 For 循环相比，这种方法的评价如何？

这将如何随着列表长度的增加或减少而变化？

Answer 1

它与循环完全相同 - 这就是它在内部所做的。

如果您的列表已排序并且您正在寻找特定值，则可能会使用BinarySearch它 - 但如果您考虑一下，如果您对谓词或数据顺序一无所知，则必须仔细查看每个项目，直到找到匹配项。碰巧，Find被指定返回列表中的第一项......所以它只是以明显的顺序查看。

这将与列表的大小成线性关系 - 即平均而言，搜索 10 倍大的列表将花费 10 倍的时间。当然，这取决于是否以及在何处找到匹配项；如果第一项在每种情况下都匹配，那么无论列表有多大，它都会在同一时间完成:)

老实说，只有 100 个对象，这听起来不太可能成为瓶颈。

Answer 2

您可以很容易地看到 .Net 如何使用 ReflectorList实现该Find方法：

Public Function Find(ByVal match As Predicate(Of T)) As T
    If (match Is Nothing) Then
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match)
    End If
    Dim i As Integer
    For i = 0 To Me._size - 1
        If match.Invoke(Me._items(i)) Then
            Return Me._items(i)
        End If
    Next i
    Return CType(Nothing, T)
End Function

两种实现之间的唯一区别是Find需要调用match而不是将此逻辑内联在循环中。

有趣的是，这个简单的表现：

var persons = new List<Person>();
for (int i = 0; i < 100; i++)
{
    persons.Add(new Person { ID = i });
}

GC.Collect();
var sw = Stopwatch.StartNew();
for (int i = 0; i < 10000000; i++)
{
    persons.Find(person => person.ID == i % 100);

}
sw.Stop();
Console.WriteLine(sw.Elapsed);

GC.Collect();
sw = Stopwatch.StartNew();
for (int i = 0; i < 10000000; i++)
{
    for (int j = 0; j < 100; j++)
    {
        if (persons[j].ID == i % 100)
        {
            break;
        }
    }
}
sw.Stop();
Console.WriteLine(sw.Elapsed);

表明：使用Find
查询列表所需的总时间为 05.7990078秒。使用循环 查询列表所需的总时间为 06.3551074秒。

这个结果在几次执行中似乎是一致的。

编辑Find- 找到了:优点的解释，
Find因为它在每次迭代中直接访问底层数组。循环通过List索引器访问它，这需要每次访问索引验证：

Public Default Property Item(ByVal index As Integer) As T
    Get
        If (index >= Me._size) Then
            ThrowHelper.ThrowArgumentOutOfRangeException
        End If
        Return Me._items(index) // _items is the underlying array.
    End Get