Прочитать на английском

Поделиться через

Увеличена сложность LINQ OrderBy.First{OrDefault}

  • Статья

Реализация OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) и OrderBy.FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) изменилась, что привело к увеличению сложности операции.

Описание изменения

В .NET Core версий 1.x–3.x вызов OrderBy или OrderByDescending, за которым следовал вызов First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) или FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>), выполнялся с уровнем сложности O(N). Так как требуется только первый элемент (элемент по умолчанию), для его поиска требуется только одно перечисление. Однако предикат, передаваемый в First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) или FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>), вызывается ровно N раз, где N — длина последовательности.

В .NET 5 и более поздних версиях было внесено изменение, вследствие которого вызов OrderBy или OrderByDescending, за которым следует First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) или FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>), выполняется с уровнем сложности O(N log N), а не O(N). Однако предикат, который передается в First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) или FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>), может вызываться менее чем N раз, что более важно для общей производительности.

Примечание

Это изменение соответствует реализации и сложности операции в .NET Framework.

Причина изменения

Преимущество вызова предиката меньшее число раз перевешивает общее снижение сложности, поэтому реализация, появившаяся в .NET Core 1.0, была отменена. Дополнительные сведения в описании этой проблемы dotnet/runtime.

Представленные версии

5,0

От разработчика не требуется никаких действий.

Затронутые API