L'utilisation d'une telle fonction de comparaison qui doit choisir entre "plus grand", "plus petit" ou "égal" est loin d'être aisé dans le cas général où on peut être "aucun des trois".
Tu as un exemple de cela ? Si tu veux trier, tu dois forcement pouvoir définir un ordre, au moins arbitraire. Tu peux te contenter de <= pour établir une relation d'ordre. Il y a un mapping bijectif entre key et cmp, du moins je pense.
Finalement, comme plusieurs l'ont fait remarquer, utiliser key est généralement plus efficace que cmp, puisque key est appelé une seule fois par élément (O(n) donc), puis la comparaison (O(n log n) pour ordonner) est effectuée en C si les clés sont des type de base. À l'opposé, utiliser cmp fait en sorte que ces O(n log n) comparaisons impliqueront toutes un appel d'une fonction Python.
En effet, mais l'overhead mémoire peut ne pas être négligeable. Je n'ai pas regardé l'implementation, mais j'imagine que le tri en place avec cmp peut se faire en O(1) en mémoire, si on ignore la mémoire prise par la liste initiale. Alors que le tri avec le DSU ajoute forcement un overhead en O(n) pour stocker les résultats de l'appel à key. En fonction du problème cela peut être une limitation, même si j'avoue que dans le cas d'un tableau énorme on passera surement par une autre structure, type numpy.
[^] # Re: En ce qui concerne Python
Posté par Guillaum (site web personnel) . En réponse au journal Haskell et le tri. Évalué à 3.
Merci, je ne connaissais pas
cmp_to_key.Tu as un exemple de cela ? Si tu veux trier, tu dois forcement pouvoir définir un ordre, au moins arbitraire. Tu peux te contenter de <= pour établir une relation d'ordre. Il y a un mapping bijectif entre key et cmp, du moins je pense.
En effet, mais l'overhead mémoire peut ne pas être négligeable. Je n'ai pas regardé l'implementation, mais j'imagine que le tri en place avec
cmppeut se faire enO(1)en mémoire, si on ignore la mémoire prise par la liste initiale. Alors que le tri avec le DSU ajoute forcement un overhead enO(n)pour stocker les résultats de l'appel à key. En fonction du problème cela peut être une limitation, même si j'avoue que dans le cas d'un tableau énorme on passera surement par une autre structure, typenumpy.