Discussion :

[aschnt]

Bonjour tout le monde,

J'espère que vous allez bien.
J'essaye de comprendre les algorithmes de tri dans python mais faut bien avouer que je cale..

Pour le test, j'ai créé un inventaire (/liste) de différents objets héritant d'une classe "Product". Je souhaiterais donc appliquer plusieurs tris (simple ou complexe) à cet inventaire;
- par nom des objets le composants,
- par état, ensuite type
- par type, ensuite prix



Cependant je dois être fameusement idiot quand même parce que le simple tri par nom me met déjà de fameux troncs d'arbre dans les roues..

print(inventory) de main() renvoie __repr__ mais comme si aucun tri n'avait été opéré au préalable, quant à print(new_inventory), censé recevoir le résultat du tri par la fonction sorted(), renvoie un splendide "None".

Malgré avoir lu la doc concernant sort(), sorted() et le guide pour le tri en python, je nage toujours en grande nébuleuse.. Auriez-vous une idée de comment résoudre ça ? Ou du moins que j'arrive à comprendre ce que je fais de mal ?

Un grand merci d'avance !

[aschnt]

Afin d'éventuellement "aider" à la lecture du screenshot ci dessus;

Inventory :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from operator import itemgetter
 
 
class Inventory:
    def __init__(self):
        self.inventory = []
 
    """Ajoute un produit à l'inventaire"""
    def add_product(self, product):
        self.inventory.append(product)
 
    """Retire un produit de l'inventaire"""
    def remove_product(self, product):
        for index, item in enumerate(self.inventory):
            if product.name == item.name:
                self.inventory.pop(index)
 
    def __repr__(self):
        for index, item in enumerate(self.inventory):
            print(f"{index}. {item}")
        return "---------------------------"
 
    """Algos de tri"""
    def sort_by_name(self):
        return sorted(self.inventory, key=itemgetter("name"))
 
    def sort_by_type(self):
        return sorted(self.inventory, key=itemgetter(2, 3))
 
    def sort_by_price(self):
        return sorted(self.inventory, key=itemgetter(3, 1))

Products :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from abc import ABC
 
 
class Product(ABC):
    def __init__(self, name, price):
        self.name = name
        self.price = price
        self.state = "CRU"
        self.product_type = None
 
    def __str__(self):
        return f"{self.product_type} | {self.name} ({self.price}€) - {self.state}"
 
    def __repr__(self):
        return self.__str__()
 
    def __getitem__(self, item):
        return getattr(self, item)

User (sort_inventory function)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    def sort_inventory(self, inventory):
        while True:
            print("Sort by state and :")
            print("1. Name")
            print("2. Type")
            print("3. Price")
            sort_type = input("Enter number : ")
            if sort_type == "1":
                inventory.sort_by_name()
                break
            elif sort_type == "2":
                inventory.sort_by_type()
                break
            elif sort_type == "3":
                inventory.sort_by_price()
                break
            else:
                print("Enter a valid number..\n")

MAIN

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from store.inventory import Inventory
from store.bucher import Bucher
from store.seller import Seller
from store.baker import Baker
from store.user import User
"""--------------------------------"""
"""---------Initialisation---------"""
"""--------------------------------"""
inventory = Inventory()
boucher_nelson = Bucher("nelson", "nelson1")
baker_john = Baker("john", "john1")
seller_arthur = Seller("arthur", "arthur1")
user = User("user", "pwd")
 
"""--------------------------------"""
"""-----Creation des produits------"""
"""--------------------------------"""
boucher_nelson.create_new_item(inventory=inventory, item_name="cote de porc", item_price="5")
boucher_nelson.create_new_item(inventory=inventory, item_name="saussisse", item_price="2")
 
baker_john.create_new_item(inventory=inventory, item_name="pain", item_price="1.5")
baker_john.create_new_item(inventory=inventory, item_name="pistolet", item_price="0.5")
 
seller_arthur.create_new_item(inventory=inventory, item_name="tomate", item_price="0.3")
seller_arthur.create_new_item(inventory=inventory, item_name="oignon", item_price="0.4")
seller_arthur.create_new_item(inventory=inventory, item_name="avocat", item_price="1.6")
 
boucher_nelson.create_new_item(inventory=inventory, item_name="saussisse", item_price="2")
seller_arthur.create_new_item(inventory=inventory, item_name="oignon", item_price="0.4")
baker_john.create_new_item(inventory=inventory, item_name="pain", item_price="1.5")
 
print(baker_john)
print(boucher_nelson)
print(seller_arthur)
print(user)
 
sorted_inventory = user.sort_inventory(inventory=inventory)
 
print(inventory)
print(sorted_inventory)

[wiztricks]

Salut,

Quand j'ai ce genre de problème, j'écris un exemple plus petit histoire de le triturer sans autres bruits.
En plus, si on ne s'en sort pas, ça fait du code permettant de reproduire quelque chose facilement... Et pas des photos à regarder.

- W

[papajoker]

bonjour,
Existe une doc
Et il te suffit de faire cet exemple (100 fois plus simple que ton code) avec plusieurs parametres pour comprendre...
si tu désires classer par prix c'est (1, autre_attr_si_prix_est_egal) - je suppose qu'avec ton itemgetter(3, 1) tu pensais faire 2 tri à la suite (sur 3 puis sur 1) : clairement pas optimisé. Et ici tu ne fais qu'un seul apel à sorted() et non 2

[tyrtamos]

Bonjour,

La fonction de tri "sort" est basée sur un algorithme très efficace (Timsort) et possède plusieurs points clé pour son utilisation:

- "sort" trie "sur place" (la liste source est triée) alors que "sorted" renvoie la liste triée (la liste source n'est pas modifiée)

- "sort" fait un tri "stable", c'est à dire que les éléments égaux ne changent pas de place dans le tri. La conséquence, c'est qu'on peut faire un tri "multicritères" en faisant plusieurs tris à la suite. A condition, bien sûr, de les faire dans le bon ordre.

- l'option "key" permet de préciser les éléments à comparer pour faire le tri. Cela permet de trier à peu près n'importe quelle liste d'objets quelconques, y compris des listes de listes et des listes d'instances de classes.

- l'option "reverse" permet de faire des tris dans l'ordre inverse (les éléments les plus forts au début).

- les comparaisons de base des chaînes de caractères se font dans l'ordre du codage des caractères "ASCII", ce qui pose le problème des chaînes de caractères ayant des majuscules et minuscules ainsi que des caractères accentués. Dans cet ordre, 'a' est rangé APRES 'X', de même que 'à' est rangé APRES 'x'. Grâce à l'option key, on peut préciser comment il faut faire pour avoir l'ordre qu'on veut, y compris l'ordre du dictionnaire français. Voir en particulier le module "unicodedata".

Exemple: tri sur place d'une liste de listes L = [[5,3], [8,9], [7,1], [0,3]] selon le 2ème élément des sous-listes (indice 1):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

L.sort(key=lambda e: e[1])

Grâce à lambda, on précise que les comparaisons du tri ne se feront pas selon les éléments de la liste (comme [8,9]), mais comme le 2ème élément des sous-listes (comme 9 ici).

Ce qui donnera pour L:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[[7, 1], [5, 3], [0, 3], [8, 9]]

On voit bien, sur cet exemple, que les éléments de la liste de même critère de tri [5, 3] et [0, 3] ont conservé l'ordre initial (=tri stable).

Je suggère de s'exercer sur des exemples simples afin de bien comprendre comment ça marche, au lieu de vouloir faire ça sur un programme complexe.

[Sve@r]

Bonjour

J'essaye de comprendre les algorithmes de tri dans python mais faut bien avouer que je cale..

Pourquoi faire? Tant que ça marche...

Mais bon pour comprendre un algorithme il faut aller lire l'algorithme. Ou regarder leurs représentation

(le plus fun c'est le "bogo sort")

Afin d'éventuellement "aider" à la lecture du screenshot ci dessus;

Oui parce que pour faire du copier/coller... mais en tout cas c'est magnifique. Surtout les liens entre les différents éléments.
Malheureusement ton exemple est incomplet. Il manque des import comme Bucher, Seller, etc... donc non reproductible

Donc pareil mais en plus simple:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
>>> auteurs=("Hugo", "Racine", "Balzac")
>>> for x in sorted(auteurs, key=lambda x: x[2]): print(x)		# Tri sur le 3° caractère
...
Racine
Hugo
Balzac

quant à print(new_inventory), censé recevoir le résultat du tri par la fonction sorted(), renvoie un splendide "None".

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    def sort_inventory(self, inventory):
        while True:
            print("Sort by state and :")
            print("1. Name")
            print("2. Type")
            print("3. Price")
            sort_type = input("Enter number : ")
            if sort_type == "1":
                inventory.sort_by_name()
                break
            elif sort_type == "2":
                inventory.sort_by_type()
                break
            elif sort_type == "3":
                inventory.sort_by_price()
                break
            else:
                print("Enter a valid number..\n")

Il ne manquerait pas un truc à ta fonction? Soit un print() des choses qu'elle calcule, soit un return de ces mêmes choses??? Parce qu'en l'état, appeler inventory.sort_by_price() (qui lui-même ne printe rien) dans le vide ça ne sert pas des masses...

C'est exactement comme si j'écrivais ceci

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
>>> def carre(n): return n*n
...
>>> def calcul(n): carre(n)
...
>>> print(calcul(5))
None

Pareil, un splendide "None".

[aschnt]

Bonjour tout le monde !

Tout d'abord merci pour vos réponses. J'ai bien lu vos critiques quant au code trop complexe. J'en suis bien conscient cependant c'est toujours en tentant des choses plus compliquées qu'on se met dans des situations de blocage, sinon ça va toujours tout seul !

Anyway, j'ai enlevé le superflu du code précédent et effectivement l'idiot que je suis avait oublié de mettre qqes 'return' dans la fonction de tri du user.. il a également fallu modifier les appels à la fonction itemgetter() afin qu'elle passe des string et non des int, sinon __getitem__() crie à l'hérésie.
(Cette fonction est encore un peu trop magique à mon gout mais je me plongerai dedans plus tard, notamment les différences concrètes avec __repr__(). Tout ce que je sais c'est qu'elle est obligatoire pour utiliser itemgetter()).


Bref, avec tout ça il est possible de faire des tris complexes/multiples, mais seulement en créant plusieurs instances de la liste (sans compter celles probablement déjà créés dans la fonction sorted() elle-même), voir 2 instances d'objet Inventaire pour le code original. Résultat ; de l'eczéma.
Est-il possible de faire la même chose mais avec list.sort() histoire de calmer le radar à optimisation ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from operator import itemgetter
 
 
"""----------------------------------------------------------------------------"""
"""----------------------------------------------------------------------------"""
"""----------------------------------------------------------------------------"""
 
 
class Product:
    def __init__(self, name, price, type=None):
        self.name = name
        self.price = price
        self.state = "CRU"
        self.product_type = type
 
    def __str__(self):
        return f"{self.product_type} | {self.name} ({self.price}€) - {self.state}"
 
    def __repr__(self):
        return self.__str__()
 
    def __getitem__(self, item):
        return getattr(self, item)
 
 
"""----------------------------------------------------------------------------"""
"""----------------------------------------------------------------------------"""
"""----------------------------------------------------------------------------"""
 
 
def create_new_item(item_name, item_price, type):
    new_product = Product(item_name, item_price, type)
    inventory.append(new_product)
 
 
def display(be_displayed_inventory):
    for index, item in enumerate(be_displayed_inventory):
        print(f"{index}. {item}")
    return "---------------------------"
 
 
"""----------------------------------------------------------------------------"""
"""-----------------------------RETURN SORTED LIST-----------------------------"""
"""----------------------------------------------------------------------------"""
 
 
def sorted_by_name():
    return sorted(inventory, key=itemgetter("name"))
 
 
def sorted_by_type():
    return sorted(inventory, key=itemgetter("state", "product_type"))
 
 
def sorted_by_price():
    return sorted(inventory, key=itemgetter("product_type", "price"))
 
 
"""----------------------------------------------------------------------------"""
"""-------------------------SORT THE LIST AND NO RETURN------------------------"""
"""----------------------------------------------------------------------------"""
 
 
def sort_by_name():
    #sorted(inventory, key=itemgetter("name"))
    inventory.sort(key=lambda e: e["name"])
 
 
def sort_by_type():
    #sorted(inventory, key=itemgetter("state", "product_type"))
    pass
 
 
def sort_by_price():
    #sorted(inventory, key=itemgetter("product_type", "price"))
    pass
 
 
"""----------------------------------------------------------------------------"""
"""-----------------------------------MAIN-------------------------------------"""
"""----------------------------------------------------------------------------"""
inventory = []
sorted_inventory = []
 
create_new_item(item_name="cote de porc", item_price="5", type="Buchery")
create_new_item(item_name="saussisse", item_price="2", type="Buchery")
create_new_item(item_name="pain", item_price="1.5", type="Bakery")
create_new_item(item_name="pistolet", item_price="0.5", type="Bakery")
create_new_item(item_name="tomate", item_price="0.3", type="Vege")
create_new_item(item_name="oignon", item_price="0.4", type="Vege")
create_new_item(item_name="avocat", item_price="1.6", type="Vege")
 
sorted_inventory = sorted_by_price()
display(sorted_inventory)
print("---------------------------------")
print("---------------------------------")
print("---------------------------------")
sort_by_name()
display(inventory)

[Sve@r]

notamment les différences concrètes avec __repr__()

Alors __str__() permet de surcharger l'opérateur str() (tout comme __int__() permettrait de surcharger l'opérateur int()) et __repr__ permet de surcharger l'opérateur repr().
Toutefois __str__() sera utilisé par défaut si repr() est demandé mais que __repr__() n'est pas présent (donc écrire un __repr__() qui appelle juste __str__()...)
Pour simplifier: __str__() permet de montrer un truc au format "humain" tandis que __repr__() permet de montrer un truc au format Python.

Bon les erreurs de ton code: tu utilises les globales (exemple la fonction create_new_item() qui utilise inventory => le jour où ton tableau change de nom...). D'ailleurs pourquoi passer par des fonctions à 2 lignes (fonctions à 2 balles) peu utiles ??? Eviter aussi de nommer ses variable "type" (sinon babye la fonction type() !!!) Et puis sais pas, j'ai l'impression que tu codes et recodes 150 fois la même chose, fatalement tu obtiens 150 fois 150 instances de ta même liste...

Bref, avec tout ça il est possible de faire des tris complexes/multiples, mais seulement en créant plusieurs instances de la liste (sans compter celles probablement déjà créés dans la fonction sorted() elle-même), voir 2 instances d'objet Inventaire pour le code original. Résultat ; de l'eczéma.

Est-il possible de faire la même chose mais avec list.sort() histoire de calmer le radar à optimisation ?

Tu veux dire "est-il possible de faire ça proprement"? Bah oui. Suffit de faire ça proprement...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/env python3
# coding: utf-8
 
#from operator import itemgetter			# Si ça te fait plaisir...
 
class Product:
	def __init__(self, name, price, tpe=None):
		self.name = name
		self.price = price
		self.state = "CRU"
		self.type = tpe
	# __init__()
 
	def __str__(self):
		return "{0}|{1} ({2}$) - {3}".format(self.type, self.name, self.price, self.state)
 
        @staticmethod
	def sort_by_name(lst, *args, **kwargs):
		return sorted(lst, key=lambda x:x.name, *args, **kwargs)
 
        @staticmethod
	def sort_by_price(lst, *args, **kwargs):
		return sorted(lst, key=lambda x:x.price, *args, **kwargs)
 
        @staticmethod
	def sort_by_any(lst, item, *args, **kwargs):
		return sorted(lst, key=lambda x:x.__dict__[item], *args, **kwargs)
# class Product
 
inventory = []
for (name, price, tpe) in (
	("cote de porc", 5, "Buchery"),
	("saucisse", 2, "Buchery"),
	("pain", 1.5, "Bakery"),
	("pistolet", 0.5, "Bakery"),
	("tomate", 0.3, "Vege"),
	("oignon", 0.4, "Vege"),
): inventory.append(Product(name, price, tpe))
 
# Autre écriture bien plus cool qui montre que vraiment create_new_item() sert à que dalle...
inventory=list(
	Product(name, price, tpe) for (name, price, tpe) in (
		("cote de porc", 5, "Buchery"),
		("saucisse", 2, "Buchery"),
		("pain", 1.5, "Bakery"),
		("pistolet", 0.5, "Bakery"),
		("tomate", 0.3, "Vege"),
		("oignon", 0.4, "Vege"),
	)
)
print(inventory)
 
# Bon, après la phase "wonderful", passons à la phase "topissitude"
print(Product.sort_by_name(inventory, reverse=True))
print(Product.sort_by_price(inventory))
print(Product.sort_by_any(inventory, "type", reverse=False))
 
# Et si on veut avoir une liste définitivement triée (phase topest)
sorted_inventory=Product.sort_by_any(inventory, "price", reverse=True)
print(sorted_inventory)

il a également fallu modifier les appels à la fonction itemgetter() afin qu'elle passe des string et non des int, sinon __getitem__() crie à l'hérésie.

Mouais... moi je m'en passe carrément. Ca évite de se faire mal aux cheveux pour pas grand chose...

[aschnt]

J'avoue que j'aurais pu réduire plus encore, oupsie.. le code se présente de la sorte pcq sur celui d'origine, divisé en plusieurs fichiers, classes etc, je ne souhaite pas qu'un inventaire soit modifié ailleurs que dans la classe inventaire. Et si modification de l'inventaire il doit y avoir, seule une classe héritant de Moderateur devrait pouvoir faire les appels de fonctions nécessaires, toussa toussa. Bref de l'honteux copié collé à peine modifié

Cela étant dit, bien vu pour la création de l'inventaire!

Quant au code suivant, j'avoue ne pas connaître cette histoire de packetage et dépacketage, donc c'est encore un poil mystérieux. Mais merci beaucoup, vais creuser ça

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
@staticmethod
	def sort_by_name(lst, *args, **kwargs):
		return sorted(lst, key=lambda x:x.name, *args, **kwargs)
 
        @staticmethod
	def sort_by_price(lst, *args, **kwargs):
		return sorted(lst, key=lambda x:x.price, *args, **kwargs)
 
        @staticmethod
	def sort_by_any(lst, item, *args, **kwargs):
		return sorted(lst, key=lambda x:x.__dict__[item], *args, **kwargs)