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)...
InformationsquelleAutor Brent Arias | 2010-05-07
  1. 51

    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.

    • Si j'ai un objet référencé comme seulement IEnumerable<Foo> comment Linq savoir si c'est de Linq-to-Objets ou autre chose?
    • IEnumerable est toujours Linq to objects (vs IQueryable qui est Linq to que ce soit d'autre)
    • IEnumerable<T> est une interface, donc cela dépend de quel type est la collection sous-jacente (je ne suis d'accord avec @John). Par exemple, List<T> implémentant IEnumerable<T>, et vous pourriez avoir une Liste<T>, a déclaré que IEnumerable<T>. Si vous effectuez une commande sur cette liste, le Linq-to-objets fournisseur est utilisé. Sur l'autre main. DbSet<T> aussi implémentant IEnumerable<T>. Si vous effectuez une commande sur ce DbSet, même si elle est déclarée comme un IEnumerable, Linq-to-sql fournisseur seront utilisés. Si vous souhaitez utiliser linq-to-objets sur un dbset, vous pourriez faire dbset.AsEnumerable().OrderBy(lambda)
    InformationsquelleAutor Jb Evain
  2. 37

    Démarrage du réflecteur, ouvrir aux Système.Linq.EnumerableSorter révèle que Linq2Objects utilise le tri rapide

    • +1 pour les regarder
    • +1 pour les regarder
    • +1 pour le regarder. Mais un simple test ne montre pas de n^2 croissance dans le temps de la consommation comme des éléments nombre d'inverser la Liste triée des int augmente, comme cela devrait être, selon en.wikipedia.org/wiki/Quicksort j'ai essayé de 1k et 1M éléments pire-cas - temps, la consommation a augmenté de seulement environ 50 fois
    • Quicksort ne fonctionne pas dans quadratique du temps. Eh bien, il peut, mais c'est la limite supérieure et rare. Si c'était theta(n**2) tout le monde serait tout simplement utiliser mergesort.
    • Maintenant .NET de base est ouvert à tout le monde 🙂 Pourquoi ne pas vous avez un oeil de plus près? referencesource.microsoft.com/#System.Core/System/Linq/...
    InformationsquelleAutor LorenVS
  3. 12

    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

    • cool. je ne savais pas que
    • Ont été à la recherche pour un tandis que pour l'open source lien, merci
    • En théorie, on pourrait stabiliser tout algorithme de tri par dont les indices dans le comparateur. Le défi est de déterminer la meilleure structure de données à utiliser pour garder une trace de ces indices.
    InformationsquelleAutor Wesner Moise
  4. 3

    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

    • Oui, mais c'est seulement vrai pour Linq to SQL et d'autres de la base de données fournisseurs Linq. Linq n'est pas seulement un ORM... (Linq to Objects, Linq to XML...)
    • +1 Pour étudier autre chose que LINQ to Objects
    InformationsquelleAutor John Weldon