Trier une liste de listes avec une fonction de comparaison personnalisée

Question

Je sais qu'il existe plusieurs questions de ce type, mais elles ne semblent pas fonctionner pour moi.

J'ai une liste de listes, 50 fois 5 éléments. Je souhaite trier cette liste en appliquant une fonction de comparaison personnalisée à chaque élément. Cette fonction calcule l'aptitude de la liste en fonction de laquelle les éléments doivent être triés. J'ai créé deux fonctions, compare et fitness :

def compare(item1, item2):
    return (fitness(item1) < fitness(item2))

et

def fitness(item):
    return item[0]+item[1]+item[2]+item[3]+item[4]

J'ai ensuite essayé de les appeler :

sorted(mylist, cmp=compare)

ou

sorted(mylist, key=fitness)

ou

sorted(mylist, cmp=compare, key=fitness)

ou

sorted(mylist, cmp=lambda x,y: compare(x,y))

J'ai également essayé list.sort() avec les mêmes paramètres. Mais dans tous les cas, les fonctions ne reçoivent pas une liste en argument, mais un fichier None . Je n'ai aucune idée de la raison de cela, venant principalement du C++, cela contredit toute idée de fonction de rappel pour moi. Comment puis-je trier ces listes avec une fonction personnalisée ?

Editer J'ai trouvé mon erreur. Dans la chaîne qui crée la liste originale, une fonction n'a rien retourné mais la valeur de retour a été utilisée. Désolé pour le dérangement

Answer 1

De plus, votre fonction de comparaison est incorrecte. Elle doit renvoyer -1, 0 ou 1, et non un booléen comme vous le faites. La fonction de comparaison correcte serait :

def compare(item1, item2):
    if fitness(item1) < fitness(item2):
        return -1
    elif fitness(item1) > fitness(item2):
        return 1
    else:
        return 0

# Calling
list.sort(key=compare)

Answer 2

Puisque l'OP demandait d'utiliser une fonction de comparaison personnalisée (et c'est ce qui m'a amené à cette question également), je veux donner une réponse solide ici :

En règle générale, vous souhaitez utiliser la fonction sorted() qui prend en paramètre un comparateur personnalisé. Nous devons faire attention au fait que dans Python 3, le nom et la sémantique des paramètres ont changé.

Fonctionnement du comparateur personnalisé

Lorsqu'un comparateur personnalisé est fourni, il doit généralement renvoyer une valeur entière ou flottante qui suit le modèle suivant (comme dans la plupart des autres langages de programmation et frameworks) :

• renvoie une valeur négative ( < 0 ) lorsque l'élément de gauche doit être trié avant le bon article
• renvoie une valeur positive ( > 0 ) lorsque l'élément de gauche doit être trié après le bon article
• retour 0 lorsque l'élément de gauche et l'élément de droite ont le même poids et doivent être classés "également" sans ordre de préséance

Dans le cas particulier de la question du PO, la fonction de comparaison personnalisée suivante peut être utilisée :

def compare(item1, item2):
    return fitness(item1) - fitness(item2)

L'utilisation de l'opération moins est une astuce astucieuse car elle permet d'obtenir des valeurs positives lorsque le poids de gauche item1 est plus grand que le poids de la droite item2 . D'où item1 sera triée après item2 .

Si vous souhaitez inverser l'ordre de tri, il suffit d'inverser la soustraction : return fitness(item2) - fitness(item1)

Appel de sorted() en Python 2

sorted(mylist, cmp=compare)

ou :

sorted(mylist, cmp=lambda item1, item2: fitness(item1) - fitness(item2))

Appel de sorted() en Python 3

from functools import cmp_to_key
sorted(mylist, key=cmp_to_key(compare))

ou :

from functools import cmp_to_key
sorted(mylist, key=cmp_to_key(lambda item1, item2: fitness(item1) - fitness(item2)))

Answer 3

Vous devez modifier légèrement votre compare fonction et utilisation functools.cmp_to_key pour le transmettre à sorted . Exemple de code :

import functools

lst = [list(range(i, i+5)) for i in range(5, 1, -1)]

def fitness(item):
    return item[0]+item[1]+item[2]+item[3]+item[4]
def compare(item1, item2):
    return fitness(item1) - fitness(item2)

sorted(lst, key=functools.cmp_to_key(compare))

Sortie :

[[2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9]]

Fonctionne :)

Answer 4

>>> l = [list(range(i, i+4)) for i in range(10,1,-1)]
>>> l
[[10, 11, 12, 13], [9, 10, 11, 12], [8, 9, 10, 11], [7, 8, 9, 10], [6, 7, 8, 9], [5, 6, 7, 8], [4, 5, 6, 7], [3, 4, 5, 6], [2, 3, 4, 5]]
>>> sorted(l, key=sum)
[[2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9], [7, 8, 9, 10], [8, 9, 10, 11], [9, 10, 11, 12], [10, 11, 12, 13]]

Ce qui précède fonctionne. Faites-vous quelque chose de différent ?

Notez que votre fonction clé est simplement sum il n'est pas nécessaire de l'écrire explicitement.

Answer 5

Une façon simple de voir les choses est que le sorted() (ou list.sort() ) en Python opère sur une seule touche à la fois. Elle construit une liste de clés en un seul passage à travers les éléments de la liste. Ensuite, elle détermine quelle clé est la plus grande ou la plus petite et les place dans le bon ordre.

La solution, telle que je l'ai trouvée, consiste donc à créer une clé qui donne le bon ordre. Ici, Python peut utiliser une clé en tant que str ou tuple . Il n'est pas nécessaire pour cela que le functools comme dans d'autres exemples :

# task: sort the list of strings, such that items listed as '_fw' come before '_bw'
foolist = ['Goo_fw', 'Goo_bw', 'Foo_fw', 'Foo_bw', 'Boo_fw', 'Boo_bw']

def sortfoo(s):
    s1, s2 = s.split('_')
    r = 1 if s2 == 'fw' else 2     # forces 'fw' to come before 'bw'
    return (r, s1)                 # order first by 'fw'/'bw', then by name

foolist.sort(key=sortfoo)          # sorts foolist inplace

print(foolist)
# prints:
# ['Boo_fw', 'Foo_fw', 'Goo_fw', 'Boo_bw', 'Foo_bw', 'Goo_bw']

Cela fonctionne parce qu'un tuple est une clé légale à utiliser pour le tri. Il peut être personnalisé en fonction des besoins, les différents éléments de tri étant simplement empilés dans ce tuple dans l'ordre d'importance du tri.