Si je passe dans un ICOMPARER personnalisé à une instance de la méthode de tri () de la liste, la méthode de comparaison de la comparaison (x, y) sera-t-elle jamais appelée avec le même article?
IE. Est-il possible que edit: plus intéressé par le cas où les éléments de la liste sont comparaison (x, x) puisse être appelé.
4 Réponses :
du docs :
Cette méthode utilise array.sort, qui utilise l'algorithme QuicksTort.
Quicksort ne comparera jamais un article à lui-même. quelques implémentations de QuicksTort comparer des articles à eux-mêmes. Cela peut également se produire si cet article survient plus d'une fois dans votre liste.de toute façon, pour que votre fonction de comparaison soit une fonction de comparaison appropriée et bien élevée, vous devez gérer le cas d'éléments étant comparés à eux-mêmes.
Comment cela explique-t-il la réponse de Johnd? Est-ce que je manque quelque chose d'évident?
Cette réponse continue à être élue et en hausse V__V. Quelqu'un peut-il confirmer le comportement QuicksTort indiqué ici, ce qui semble contraire à la lutte contre le programme de Johnd's Sample?
Hmm, c'est intéressant! Je suis heureux que les deux réponses apparaissent près du sommet, maintenant que Johnd a été accepté. Dans ce cas, nous devons conclure que les docs sont faux.
Il existe de nombreuses implémentations de Quicksort, dont certaines comparer les éléments contre-même . Il n'y a rien de mal avec les docs.
Je suis corrigé - je n'ai jamais vu QuicksTort en train d'être écrit de cette façon. Cependant, je maintiens que les DOCS ont tort d'appeler ce détail de mise en œuvre comme faisant partie de la spécification, ce qui n'est pas. Tout algorithme moyen-nlogn-Nlogn-Nlogn-Nlogn peut être utilisé comme fonction de tri.
Bien que ce ne soit pas strictement garanti, je suis à peu près sûr que la méthode de tri de la liste, je n'appellera jamais votre méthode de comparaison pour comparer un objet à lui-même à moins que cet objet ne soit apparu dans la liste plusieurs fois. Je baste cette conclusion sur le fait que List.sort est implémenté à l'aide de l'algorithme QuicksTort (selon MSDN), que ne compare jamais n'implique généralement pas comparer le même élément à lui-même (Et ni aucun des algorithmes de tri documenté, je ne peux penser). (Edit: Il semble que la mise en œuvre de Microsoft comparait l'élément à elle-même. Voir la réponse acceptée ci-dessus.)
Toutefois, de bonnes pratiques de codage dicteraient que votre implémentation d'IComparer devrait être en mesure de pouvoir fonctionner le même objet dans les deux paramètres, car votre implémentation ne remplisse pas le contrat défini par Icomarer. Cela fonctionnerait probablement pour votre scénario, mais vous comptez sur la mise en œuvre des détails de la méthode de tri (ce qui pourrait changer à l'avenir), et vous ne seriez pas en mesure de vous utiliser Icomarer implémenter dans d'autres scénarios où il n'y a pas de tel Garantie (ou pire, vous ou quelqu'un d'autre utilise-le et crée éventuellement un bogue difficile à trouver).
J'ai écrit un programme de test pour l'essayer. On dirait que est em> comparer () le même élément à lui-même (au moins comparer () est appelé pour le même article deux fois). Dans ce programme, Comparer () est appelé avec des arguments (2, 2). Compare(1, 2)
Compare(1, 3)
Compare(2, 3)
Compare(1, 2)
Compare(2, 2)
Compare(2, 3)
Compare(2, 2)
Hmm .. Ouais. A ajouté une console.writeine () au début de la méthode Comparer (). Comparer (2,2) est appelé deux fois pour la liste donnée.
Confirmé à l'aide de mono 2.6.7.0. (J'ai pris la liberté d'ajouter en utilisant des directives et une instruction writeine pour faciliter la tâche des gens d'essayer pour eux-mêmes.)
Cela ne se produit plus (code C # identique au vôtre ci-dessus) avec .NET 4.6.2. Maintenant, il écrit juste: Comparer (1, 2) Comparer (1, 3) Comparer (2, 3) Efficace.
Bien sûr, si la liste <> contient le même objet plus d'une fois.
@Hans: Oui, je suis confus un peu dans mon commentaire supprimé. Je travaillais avec une liste contenant des instances d'une classe. Bien entendu, dans certains programmes, il peut également être possible que le même cas se produise plusieurs fois dans la liste. Mais comme édité, je me demandais le cas où la liste contenait des instances distinctes de la classe.
Je me suis trompé. Le commentaire de la source de référence indique: Prétraitez les valeurs bas, moyennes (pivot) et élevées en place. Cela améliore les performances face à des données déjà triées, ou des données composées de plusieurs courses triés ajoutées ensemble.
Que ce soit possible ou non, vous devez le soutenir car cela fait partie du contrat de fonction de comparaison.