FindAll vs Где расширение-метод - PullRequest
29 голосов
/ 07 октября 2009

Я просто хочу знать, будет ли "FindAll" быстрее метода "Где" и почему?

Пример:

myList.FindAll(item=> item.category == 5);

или

myList.Where(item=> item.category == 5);

Что лучше?

Ответы [ 5 ]

50 голосов
/ 07 октября 2009

Ну, FindAll копирует соответствующие элементы в новый список, тогда как Where просто возвращает лениво оцененную последовательность - копирование не требуется.

Поэтому я ожидал бы, что Where будет немного быстрее, чем FindAll, даже если результирующая последовательность будет полностью оценена - и, конечно, стратегия ленивой оценки Where означает, что если вы посмотрите только на (скажем) Первый матч, не нужно проверять оставшуюся часть списка. (Как указывает Мэтью, есть работа по поддержанию конечного автомата для Where. Однако это будет иметь только фиксированную стоимость памяти - тогда как построение нового списка может потребовать многократного выделения массивов и т. Д.)

По сути, FindAll(predicate) ближе к Where(predicate).ToList(), чем к Where(predicate).

Просто чтобы немного больше отреагировать на ответ Мэтью, я не думаю, что он проверил его достаточно тщательно. Его предикат выбирает половину предметов. Вот короткая, но полная программа, которая тестирует один и тот же список, но с тремя разными предикатами: один выбирает без элементов, один выбирает все элементы и один выбирает половину из них. В каждом случае я запускаю тест пятьдесят раз, чтобы увеличить время.

Я использую Count(), чтобы убедиться, что результат Where полностью оценен. Результаты показывают, что, собрав около половины результатов, два шеи и шеи. Не собирая результатов, FindAll выигрывает. Собрав все результаты, Where выигрывает. Я нахожу это интригующим: все решения становятся медленнее по мере того, как обнаруживается все больше и больше совпадений: FindAll имеет больше возможностей для копирования, а Where должен возвращать совпадающие значения, а не просто зацикливаться в реализации MoveNext(). Однако FindAll становится медленнее, чем Where, поэтому теряет раннее преимущество. Очень интересно.

Результаты:

FindAll: All: 11994
Where: All: 8176
FindAll: Half: 6887
Where: Half: 6844
FindAll: None: 3253
Where: None: 4891

(скомпилировано с / o + / debug- и запущено из командной строки, .NET 3.5.)

Код:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Test
{
    static List<int> ints = Enumerable.Range(0, 10000000).ToList();

    static void Main(string[] args)
    {
        Benchmark("All", i => i >= 0); // Match all
        Benchmark("Half", i => i % 2 == 0); // Match half
        Benchmark("None", i => i < 0); // Match none
    }

    static void Benchmark(string name, Predicate<int> predicate)
    {
        // We could just use new Func<int, bool>(predicate) but that
        // would create one delegate wrapping another.
        Func<int, bool> func = (Func<int, bool>) 
            Delegate.CreateDelegate(typeof(Func<int, bool>), predicate.Target,
                                    predicate.Method);
        Benchmark("FindAll: " + name, () => ints.FindAll(predicate));
        Benchmark("Where: " + name, () => ints.Where(func).Count());
    }

    static void Benchmark(string name, Action action)
    {
        GC.Collect();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 50; i++)
        {
            action();
        }
        sw.Stop();
        Console.WriteLine("{0}: {1}", name, sw.ElapsedMilliseconds);
    }
}
14 голосов
/ 07 октября 2009

Как насчет того, чтобы проверить, а не угадать? Стыдно видеть неверный ответ.

var ints = Enumerable.Range(0, 10000000).ToList();
var sw1 = Stopwatch.StartNew();
var findall = ints.FindAll(i => i % 2 == 0);
sw1.Stop();

var sw2 = Stopwatch.StartNew();
var where = ints.Where(i => i % 2 == 0).ToList();
sw2.Stop();

Console.WriteLine("sw1: {0}", sw1.ElapsedTicks);
Console.WriteLine("sw2: {0}", sw2.ElapsedTicks);
/*
Debug
sw1: 1149856
sw2: 1652284

Release
sw1: 532194
sw2: 1016524
*/

Edit:

Даже если я переверну вышеуказанный код с

var findall = ints.FindAll(i => i % 2 == 0);
...
var where = ints.Where(i => i % 2 == 0).ToList();

... до ...

var findall = ints.FindAll(i => i % 2 == 0).Count;
...
var where = ints.Where(i => i % 2 == 0).Count();

Я получаю эти результаты

/*
Debug
sw1: 1250409
sw2: 1267016

Release
sw1: 539536
sw2: 600361
*/

Редактировать 2,0 ...

Если вы хотите получить список подмножества текущего списка, то самый быстрый метод, если FindAll (). Причина этого проста. Метод экземпляра FindAll использует индексатор текущего списка вместо конечного автомата перечислителя. Метод расширения Where () - это внешний вызов другого класса, который использует перечислитель. Если вы переходите от каждого узла в списке к следующему узлу, вам придется вызывать метод MoveNext () под обложками. Как вы можете видеть из приведенных выше примеров, еще быстрее использовать записи индекса для создания нового списка (который указывает на исходные элементы, так что объем памяти будет минимальным), чтобы даже просто получить количество отфильтрованных элементов.

Теперь, если вы собираетесь преждевременно прервать использование Enumerator, метод Where () может быть быстрее. Конечно, если вы переместите логику раннего прерывания в предикат метода FindAll (), вы снова будете использовать индексатор вместо перечислителя.

Теперь есть другие причины для использования оператора Where () (например, другие методы linq, блоки foreach и многие другие), но вопрос был в том, быстрее ли FindAll (), чем Where (). И если вы не выполняете Where (), ответ будет положительным. (При сравнении яблок с яблоками)

Я не говорю, не используйте LINQ или метод .Where (). Они делают для кода, который намного проще для чтения. Вопрос был о производительности, а не о том, насколько легко вы можете читать и понимать код. Быстрее всего, самый быстрый способ сделать эту работу - использовать шаг блока для каждого индекса и выполнять любую логику по своему усмотрению (даже ранние выходы). Причина, по которой LINQ так хорош, заключается в том, что деревья выражений и преобразования могут быть с ними сложными. Но использование итератора из метода .Where () должно пройти через тонны кода, чтобы найти путь к машине состояний в памяти, которая просто получает следующий индекс из списка. Также следует отметить, что этот метод .FindAll () полезен только для объектов, которые его реализовали (таких как Array и List.)

Еще больше ...

for (int x = 0; x < 20; x++)
{
    var ints = Enumerable.Range(0, 10000000).ToList();
    var sw1 = Stopwatch.StartNew();
    var findall = ints.FindAll(i => i % 2 == 0).Count;
    sw1.Stop();

    var sw2 = Stopwatch.StartNew();
    var where = ints.AsEnumerable().Where(i => i % 2 == 0).Count();
    sw2.Stop();

    var sw4 = Stopwatch.StartNew();
    var cntForeach = 0;
    foreach (var item in ints)
        if (item % 2 == 0)
            cntForeach++; 
    sw4.Stop();

    Console.WriteLine("sw1: {0}", sw1.ElapsedTicks);
    Console.WriteLine("sw2: {0}", sw2.ElapsedTicks);
    Console.WriteLine("sw4: {0}", sw4.ElapsedTicks);
}


/* averaged results
sw1 575446.8
sw2 605954.05
sw3 394506.4
/*
2 голосов
/ 07 октября 2009

Ну, по крайней мере, вы можете попытаться измерить это.

Статический метод Where реализован с использованием блока итераторов (ключевое слово yield), что в основном означает, что выполнение будет отложено. Если вы сравните вызовы с этими двумя методами, первый будет медленнее, поскольку это сразу подразумевает, что вся коллекция будет повторяться.

Но если вы включите полную итерацию полученных результатов, все может быть немного иначе. Я почти уверен, что решение yield медленнее, из-за созданного им механизма конечного автомата. (см. @Matthew anwser)

1 голос
/ 07 октября 2009

Я могу дать некоторую подсказку, но не уверен, какая из них быстрее. FindAll () выполняется сразу же. Где () отложено выполняется.

0 голосов
/ 12 октября 2015

Преимущество где - отсроченное исполнение. Посмотрите разницу, если бы у вас была следующая функциональность

BigSequence.FindAll( x =>  DoIt(x) ).First();
BigSequence.Where( x => DoIt(x) ).First();

FindAll покрыл полную последовательность, тогда как Where в большинстве последовательностей перестанет перечислять, как только будет найден один элемент.

Те же самые эффекты будут теми же, используя Any (), Take (), Skip () и т. Д. Я не уверен, но я думаю, у вас будут огромные преимущества во всех функциях, которые имеют отложенное выполнение

...