代码之家 › 专栏 › 技术社区 › Srikanth Venugopalan

使用类的谓词搜索泛型列表-比循环更快?

predicate generics list .net

Srikanth Venugopalan · 技术社区 · 14 年前

假设我们有一个类1的通用列表,对于给定的会话,通常有大约100个对象。我想看看这个列表是否有特定的对象。ASP.NET 2.0允许我执行以下操作:

Dim objResult as Class1 = objList.Find(objSearch)

从性能角度看,与传统的for循环相比,这种方法如何评价?

这会随着列表长度的增加或减少而变化吗?

2 回复 | 直到 14 年前

Elisha 14 年前

你可以很容易地看到.NET List 实现 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

两种实现之间的唯一区别是 发现 需要呼叫 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);

表明:
查询列表所需的总时间 发现是5.7990078 秒。
查询列表所需的总时间 环是6.3551074 秒。

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

编辑 -找到了对 发现 :
发现 因为它在每次迭代中直接访问底层数组,所以工作速度更快。循环通过 表 索引器,要求每次访问索引验证:

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

Jon Skeet 14 年前

这和循环完全一样——这就是它在内部所做的。

如果您的列表已排序,并且正在查找特定的值,则可能会使用 BinarySearch 相反-但是如果你考虑它,如果你对谓词或数据的顺序一无所知,它有仔细检查每个项目,直到找到匹配项。碰巧, Find 指定返回第一列表中的项目…所以它只是按照明显的顺序看了看。

这将与列表的大小成线性关系,即平均而言,搜索一个大10倍的列表需要10倍的时间。当然,这取决于是否找到匹配项以及在哪里找到匹配项;如果每种情况下第一个项都匹配,则无论列表有多大,它都将在同一时间完成:)

说实话,只有100个物体,这听起来不太可能成为瓶颈。