Найти () против перечисления в списках
Я работаю с базой кода, где в списках нужно часто искать один элемент.
Быстрее ли использовать Predicate и Find (), чем вручную выполнять перечисление в списке?
Например:
string needle = "example";
FooObj result = _list.Find(delegate(FooObj foo) {
return foo.Name == needle;
});
против.
string needle = "example";
foreach (FooObj foo in _list)
{
if (foo.Name == needle)
return foo;
}
Хотя они эквивалентны по функциональности, эквивалентны ли они и по производительности?
Ответы 6
Они не равноценны по производительности. Метод Find () требует вызова метода (в данном случае делегата) для каждого элемента в списке. Вызов метода платный и стоит относительно дорого по сравнению со встроенным сравнением. Версия foreach не требует дополнительного вызова метода для каждого объекта.
При этом я бы не выбрал тот или другой в зависимости от производительности, пока я не профилировал свой код и не обнаружил, что это проблема. Я еще не обнаружил, что накладные расходы этого сценария представляют собой проблему «горячего пути» для кода, который я написал, и я часто использую этот шаблон с Find и другими подобными методами.
@Konrad, у меня нет никаких данных. Но мы регулярно профилируем наш код внутри компании, а я профилирую несколько внешних проектов. В достаточно сложном проекте это никогда не было узким местом. Это медленнее, но как только вы добавляете реальное приложение поверх, это не заметно.
@Kronrad (прод.) Компилятор может встроить этот код, но в настоящее время компилятор C# не сильно переписывает ваш код в целях оптимизации. AFAIK, он никогда не вставляет лямбду. Хотя это, безусловно, возможно. Посмотрите на F#. Они сильно переписывают код.
Как указал Джаред, есть различия.
Но, как всегда, не волнуйтесь, если вы не знаете, что это узкое место. И если это узкое место, вероятно, потому, что списки большие, и в этом случае вам следует подумать об использовании более быстрого поиска - хеш-таблицы или двоичного дерева, или даже просто сортировки списка и выполнения двоичного поиска даст вам log (n) производительность, которая будет иметь гораздо большее влияние, чем настройка вашего линейного корпуса.
Если поиск по вашему списку слишком медленный как есть, вы, вероятно, добьетесь большего успеха, чем линейный поиск. Если вы можете сохранить список отсортированным, вы можете использовать двоичный поиск, чтобы найти элемент за время O (lg n).
Если вы ищете лот весь, подумайте о замене этого списка Словарём, чтобы индексировать ваши объекты по имени.
Технически производительность во время выполнения версии делегата будет немного хуже, чем у другой версии, но в большинстве случаев вам будет трудно заметить какую-либо разницу.
Более важным (IHMO) является время выполнения кода, позволяющее написать то, что вы хотите, а не то, как вы этого хотите. Это имеет большое значение в ремонтопригодности.
Этот исходный код:
string needle = "example";
foreach (FooObj foo in _list)
{
if (foo.Name == needle)
return foo;
}
требует, чтобы любой сопровождающий прочитал код и понял, что вы ищете конкретный элемент.
Этот код
string needle = "example";
return _list.Find(
delegate(FooObj foo)
{
return foo.Name == needle;
});
дает понять, что вы ищете конкретный предмет, - быстрее для понимания.
Наконец, этот код, использующий возможности C# 3.0:
string needle = "example";
return _list.Find( foo => foo.Name == needle);
делает то же самое, но в одной строке, что еще быстрее для чтения и понимания (ну, во всяком случае, если вы поймете лямбда-выражения).
Таким образом, учитывая, что производительность альтернатив почти одинакова, выберите тот, который упрощает чтение и сопровождение кода.
«Я работаю с базой кода, где списки должно быть часто обыскивают для одного элемента»
Лучше изменить структуру данных на Dictionary вместо List, чтобы повысить производительность.
Аналогичный вопрос был задан для List.ForEach vs. foreach-iteration (foreach против someList.Foreach () {}).
В этом случае List.ForEach был немного быстрее.
У вас есть данные для подтверждения вашего иска? Как уже упоминал Далле, тесты показывают обратное для очень похожего кода. Я не вижу причин, по которым компилятор в принципе не должен иметь возможность встроить лямбду, что делает этот метод по крайней мере таким же эффективным, как итерация вручную.