La complexité de LINQ OrderBy.First{OrDefault} a augmenté

  • Article

L’implémentation de OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) et OrderBy.FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) a changé, ce qui a entraîné une complexité accrue pour l’opération.

Description de la modification

Dans .NET Core 1.x - 3.x, l’appel OrderBy ou OrderByDescending suivi de First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) ou FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) fonctionne avec la complexité O(N). Étant donné que seul le premier élément (ou celui par défaut) est requis, une seule énumération est requise pour le trouver. Toutefois, le prédicat fourni à First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) ou FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) est appelé exactement N fois, où N est la longueur de la séquence.

Dans .NET 5 et versions ultérieures, une modification a été apportée de telle sorte que l’appel à OrderBy ou OrderByDescending suivi de First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) ou FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) fonctionne avec la complexité O(N log N) au lieu de O(N). Toutefois, le prédicat fourni à First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) ou FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) peut être appelé moins de N fois, ce qui est plus important pour les performances globales.

Notes

Cette modification correspond à l’implémentation et à la complexité de l’opération dans .NET Framework.

Raison du changement

L’avantage d’appeler le prédicat moins souvent l’emporte sur une complexité globale inférieure, de sorte que l’implémentation introduite dans .NET Core 1.0 a été rétablie. Pour plus d’informations, consultez ce problème dotnet/runtime.

Version introduite

5,0

Aucune action n’est requise de la part du développeur.

API affectées