Quel Algorithme de Tri Est Utilisé Par LINQ “OrderBy”?
Évidemment LINQ "OrderBy" avait à l'origine été spécifié comme instable, mais le temps de Orca il a été spécifié comme stable. Pas l'ensemble de la documentation a été mise à jour en conséquence - tenir compte de ces liens:
Mais si LINQ OrderBy est maintenant "stable", alors cela signifie qu'il n'est pas à l'aide d'un quicksort (ce qui est par nature instable), même si certains documents (par exemple, Troy livre) dit qu'il est. Donc ma question est: si pas de quicksort, alors qu'est-ce que l'algorithme réel LINQ orderBy est l'aide?
- Stictly, Linq
OrderBy
n'est pas spécifié pour la stabilité.Enumerable.OrderBy
est spécifié comme stable, les autres fournisseurs sont libres d'offrir que des promesses, mais ne peut pas. Cela peut être impossible ou très coûteux (tenir compte de l'impact que cela aurait sur la parallélisation en termes de p-linq par exemple) ou relativement bon marché, ce qui est une grande influence sur ce que les fournisseurs de faire. - Un très related post ici.
- serait-il mauvais de cette balise [c#]? ou au moins [.net]? J'ai manqué cette question parce que je commence toutes mes requêtes avec [c#] (à moins que j'arrive à faire du javascript dans la journée)...
Vous devez vous connecter pour publier un commentaire.
LINQ to Objects, c'est un stable quicksort qui est utilisé. Pour tout autre type de LINQ, il est laissé à l'implémentation sous-jacente.
IEnumerable<Foo>
comment Linq savoir si c'est de Linq-to-Objets ou autre chose?Démarrage du réflecteur, ouvrir aux Système.Linq.EnumerableSorter révèle que Linq2Objects utilise le tri rapide
Quicksort est utilisé, mais la raison pour laquelle il est stable est parce que les indices de chaque paire d'éléments sont comparés si toutes les clés du test d'égalité.
En d'autres mots, vous pouvez faire tout quicksort stable, en incluant dans le comparateur de fonction d'une comparaison de l'original indices de ces deux éléments comme une solution de repli.
Source: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34
Je suis en vertu de la compréhension que
OrderBy
se traduit en SQL qui effectue le tri sur la Base de données. Au moins dans le cas de LINQ to SQL