Использование предиката класса для поиска общего списка - быстрее, чем цикл? - PullRequest
Новая
       19

Использование предиката класса для поиска общего списка - быстрее, чем цикл?

4 голосов
/ 01 мая 2010

Допустим, у нас есть общий список Class1, обычно имеющий ~ 100 объектов для данного сеанса.Я хотел бы видеть, есть ли в списке определенный объект.ASP.NET 2.0 позволяет мне сделать это: 

Dim objResult as Class1 = objList.Find(objSearch)

Как этот подход оценивается по сравнению с традиционным циклом For с точки зрения производительности?

Как это будет меняться с увеличениемили уменьшение длины списка?

Ответы [ 2 ]

7 голосов
/ 01 мая 2010

Это то же самое, что и цикл - это то, что он делает внутри.

Если ваш список отсортирован, и вы ищете определенное значение, вы могли бы вместо этого использовать BinarySearch - но если вы подумаете об этом, если вы ничего не знаете о предикате или порядок данных: имеет для просмотра каждого элемента, пока не найдет совпадение. Как это происходит, Find указывается для возврата первого элемента в списке ... так что он просто просматривает в очевидном порядке.

Это будет линейно с размером списка - то есть, в среднем, поиск списка, который в 10 раз больше, займет в 10 раз больше времени. Конечно, это зависит от того, где и где найдено совпадение; если первый элемент совпадает в каждом случае, он завершится в одно и то же время, независимо от размера списка:)

Честно говоря, всего с 100 объектами звучит так, как будто это узкое место.

3 голосов
/ 01 мая 2010

Вы можете легко увидеть, как .Net List реализует метод Find, используя Reflector: 

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);

Показывает, что:
Общее время, необходимое для запроса списка с помощью Найти , составляет 05,7990078 секунд.
Общее время, необходимое для запроса списка с использованием loop , составляет 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
...