Amélioration d'une fonction de tri

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Dans mon stage je dois, à un moment, ordonner des chaînes de caractères en fonction du premier caractère dans un ordre précis. Voici un exemple d’entré :

"RH001-548",
"AH004-485",
"AH001-785",
"RH007-225",
"KH001-254"

Et voici la sortie que je dois obtenir :

AH001-785
AH004-485
RH001-548
RH007-225
KH001-254

Le tri doit donc :

  • Regrouper les premières lettres ensemble et dans le bon ordre ;
  • Trier ces petits groupes par numéro qui suit (la deuxième lettre sera toujours la même et les trois nombres suivants sont uniques pour une première lettre, on ne peut pas avoir deux fois 001 pour la lettre A.

Voici la fonction que j’ai imaginé :

def sort(list):
    tmp = {}
    res = []
    order = ["A", "R", "K"]

    for el in list:
        if el[0] not in tmp:
            tmp[el[0]] = []

        tmp[el[0]].append(el)

    for letter in order:
        for el in sorted(tmp[letter]):
            res.append(el)

    return res

Ce qui m’embête avec ce code, c’est le nombre de boucles et de listes/dictionnaires créés juste pour effectuer ce tri (sachant qu’il peut y avoir 2000 à 3000 éléments à trier).

Je me demandais donc s’il y avait moyen de faire plus simple (en utilisant map ou autre fonction un peu compliqué :lol: ) qui vous viendrait à l’esprit ?

Merci pour votre aide !

+0 -0

Cette réponse a aidé l’auteur du sujet

Salut,

Quand tu dois implémenter une méthode de tri spécifique, ne crée pas pour autant une fonction avec un algorithme de tri : utilise le paramètre key des fonctions sorted ou list.sort. Ce paramètre permet d’utiliser une fonction propre pour mettre en place la méthode de tri.

key doit être une fonction à un paramètre recevant un élément et renvoyant une valeur ordonnable. La fonction key sera appelée pour chaque élément de l’ensemble et le tout sera ordonné selon les valeurs renvoyées.

Dans ton cas, on pourrait imaginer une fonction key telle que ci-dessous.

order = ["A", "R", "K"]

def my_key(elem):
    left, right = elem.split('-')
    letter = left[0]
    num = left[-3:]
    return order.index(letter), num, right

Tu peux aussi précalculer les index d'order pour gagner en perfs et si t’es sûr de la structure de tes chaînes tu peux aussi simplement renvoyer order.index(letter), elem.

Édité par entwanne

Salut,

En quoi list.sort() ou sorted() ne répondent pas à tes besoins ? Ça trie les chaînes de caractères en comparant caractère par caractère et ça semble répondre à ta problématique.

tleb

K est avant R dans l’alphabet mais il veut avoir le R avant le K d’après son exemple. J’ai fait la même erreur au début.

+0 -0
Auteur du sujet

Salut,

En quoi list.sort() ou sorted() ne répondent pas à tes besoins ? Ça trie les chaînes de caractères en comparant caractère par caractère et ça semble répondre à ta problématique.

tleb

C’est bien ce que je faisais au départ, mais comme dis dans le sujet, il faut que les lettres soient dans un ordre précis qui n’est pas alphabétique (sinon ça serait trop simple :lol: )

@entwanne ta méthode fonctionne super bien ! Je ne savais pas que l’on pouvait aller aussi loin dans la fonction sort, merci beaucoup !

Édité par Wizix

+0 -0

C’est un peu hors-sujet mais pour des utilisations de dictionnaire comme tu le fais pour tmp (bouh le mauvais nommage au passage), je te conseille d’utiliser les defaultdict, depuis la bibli collections.

Plutôt que d’avoir

tmp = {}

for el in list:
    if el[0] not in tmp:
        tmp[el[0]] = []
    tmp[el[0]].append(el)

Tu as juste

from collections import defaultdict

tmp = defaultdict(list)

for el in list:
    tmp[el[0]].append(el)

Ce qui est plus joli. :)

Édité par melepe

+2 -0

Personnellement je n’aurais pas utilisé de relation d’ordre custom pour tout trier. Je serais plutôt passé par itertools.groupby pour ordonner des sous-listes déjà triées selon la relation lexicographique native :

>>> data = [
...     "RH001-548",
...     "AH004-485",
...     "AH001-785",
...     "RH007-225",
...     "KH001-254"
... ]
>>> groups = {k: list(i) for k, i in groupby(sorted(data), lambda k: k[0])}
>>> order = 'ARK'
>>> [e for k in order for e in groups[k]]
['AH001-785', 'AH004-485', 'RH001-548', 'RH007-225', 'KH001-254']

Édité par nohar

I was a llama before it was cool

+4 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte