IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Tri de liste en python


Sujet :

Python

  1. #21
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Août 2008
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2008
    Messages : 25
    Points : 34
    Points
    34
    Par défaut
    bonjour,

    il me semble que tu peut encore simplifier:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    def occurence(texte,k):
        for _,freq in texte[k:]:
            if freq != texte[k-1][1]: break
            k+=1
        return [lettre for lettre,_ in texte[:k]]
     
    Liste=  [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
     
    print occurence(Liste,2)

  2. #22
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    Malin malin ! , denis2.


    J’avais mis k = min(k,len(li)) pour éviter que k soit plus grand que la longueur de la liste.

    J’avais en effet vérifié que pour une liste li, l’écriture li[len(li):] renvoie bien [] sans erreur. Mais je suis resté avec l’idée que pour une valeur deb>len(li) , li[deb:] déclencherait une erreur d’ “index out of range“, sans le vérifier !
    En fait donc, si li =[1,2,3,4] alors li[2450:] renvoie [] quand même.

    Ce qui permet effectivement de simplifier comme tu l’as fait, denis2.



    Même au niveau de la disparition de la référence last, c’est astucieux.

    Dans un premier temps, j’ai pensé que c’était moins bien de faire disparaître last au profit de if freq != li[k-1][1]: au lieu de if freq != lasr:
    Car l’écriture if freq != li[k-1][1]: implique que le programme doit retourner chercher dans li[k-1][1] toujours la même valeur à chaque tour, ce qui est moins optimisé que de travailler avec l’alias last.

    Le problème est que si on élimine k = min(k,len(li)) en gardant last = li[k-1][1], on se retrouve avec une erreur sur last = li[k-1][1] quand k>len(li).

    On est donc alors obligé d’écrire last = li[min(k-1,len(li)-1)][1] ce qui est rendre à nouveau un peu lourd le code qu’on vient de simplifier en éliminant k = min(k,len(li)) .

    Mais tout ça pour quoi ? Pour gagner une ligne. Alors que ta solution d’éliminer aussi last et de mettre if freq != li[k-1][1]: au lieu de if freq != last: représente quel réel poids ? : celui que le programme doive retrouver la valeur li[k-1][1] plusieurs fois .... mais combien de fois ? certainement pas 250000 fois pour une analyse d’occurences des lettres dans un texte, sachant qu’il y a au maximum 26 + 30 (ùûüÿàâçéèêëïîôœÙÛÜŸÀÂÇÉÈÊËÏÎÔŒ) lettres dans l’alphabet français. L’avantage procuré par l’usage de last est femtoïque ( 1 femto = 10 puissance -15).

    Donc ton choix d'éliminer last est bien le meilleur, denis2



    Et là où il y a astuce, c’est que si k > len(li) , le programme ne rentre pas dans la boucle for _,freq in li[k:]: et ne rencontre donc pas l’erreur d’index pour li[k-1][1] qui se produirait parce que k > len(li).





    -----------------------------------


    À partir de là , je me suis amusé à réduire encore le nombre de lignes en m’efforçant d’éliminer l’instruction k+=1.




    Il faut remarquer qu’en faisant
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
        for _,freq in li[k:]:
            if freq != li[k-1][1]: break
            k+=1
    la valeur de [k-1] change et qu’on compare donc à chaque fois la nouvelle valeur de freq avec la précédente. Alors que ce n’est pas utile. On peut fort bien comparer freq à la valeur placée toujours à la même place [k initiale - 1]

    Donc éliminer k+=1 n’est pas gênant à ce niveau, mais seulement dans l’expression du return, où il est nécessaire que li[0:k] soit avec un k qui a été modifié.





    Qu’à cela ne tienne:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def occurence(li,k):
        for (i,(_,freq)) in enumerate(li[k:]):
            if freq != li[k-1][1]: break
        return [lettre for lettre,_ in li[0:k+i]]
     
    Liste=  [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
    print '  ',[str(c[1]) for c in Liste] # pour suivre les resultats
    for k in xrange(13):
        print str(k).rjust(2),occurence(Liste,k)


    Problème : quand k initiale > len(li) , i n’est pas défini car on ne rentre pas dans la boucle for (i,(_,freq)) in enumerate(li[k:]):
    ['4', '3', '3', '2', '2', '2', '2', '1', '1', '1']
    0 []
    1 ['A']
    2 ['A', 'B', 'J']
    3 ['A', 'B', 'J']
    4 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
    5 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
    6 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
    7 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
    8 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H']
    9 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H']
    10

    Traceback (most recent call last):
    File "D:\Python264\test.py", line 9, in <module>
    print str(k).rjust(2),occurence(Liste,k)
    File "D:\Python264\test.py", line 4, in occurence
    return [lettre for lettre,_ in li[0:k+i]]
    UnboundLocalError: local variable 'i' referenced before assignment





    On va créer i d’une autre manière:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    def occurence(li,k):
        i = sum(1 for (_,freq) in li[k:] if freq == li[k-1][1] )
        return [lettre for lettre,_ in li[0:k+i]]



    Seul problème: pour k==0, li[k-1] est li[-1] c’est à dire qu’on teste freq par rapport à la fréquence du dernier couple dans la liste li. Ce qui ne veut rien dire.

    Mais k==0 est un cas sans intérêt: on n’est pas censé demander au programme les lettres des zéros premières occurences.





    On aboutit ainsi à l’écriture cabalistique donnant la liste des lettres des k premières occurences, en une seule expression

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    Liste=  [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
     
    print '  ',[str(c[1]) for c in Liste] # pour suivre les resultats
    for k in xrange(13):
        print str(k).rjust(2),
        print [lt for lt,_ in Liste[0:k+sum(1 for (_,f) in Liste[k:]\
                                            if f == Liste[k-1][1] )]]


    Il me semble que cette solution n'est ni moins ni plus hermétique que celle de wiztricks initiale (que j’ai mise un sacré moment avant de capter) et celle de denis2.
    En toute subjectivité, c’est celle que je préfère.



    Python: quand on croit qu’on a fini, on peut encore continuer.

  3. #23
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 241
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 241
    Points : 36 698
    Points
    36 698
    Par défaut
    Heu

    @ wiztricks

    Ébouriffante “astuce“. Chapeau.

    Ce n’est en fait pas une astuce, mais une simple constatation logique: quelle que soit la répétitivité des occurences dans les k premiers couples, seule la répétition de l’occurence du k-ième comme occurence des suivants peut faire étendre ListeRetour au delà du k-ième élément.

    Cette “astuce“, je vais la retenir !
    wiztricks: anagramme de wiz’s trick
    La magie n'est pas dans le code mais dans la transformation d'un algorithme écrit en français en lignes de Python.
    Pour limiter les efforts de traduction à faire pour aller du français au Python, il faut rester une ligne de français une ligne de Python.

    Une fois cela écrit, nous avons une "chose" qui permet de faire des tests et de s'assurer que les résultats obtenus sont satisfaisants: dire "oui c'est bien çà qu'on veut".

    Une fois franchit ce pas important... on peut optimiser si nécessaire. Et pour cela vous êtes biens meilleurs que moi. Il n'y a pas photo.

    -W

    PS: Mon boulot est de faire de l'architecture, i.e. des croquis sur un coin de nappe. Leur fonction est de reformuler la demande "client" et expliquer à un ingénieur normalement constitué ce qu'on attend pour qu'il puisse le chiffrer et le réaliser.
    Ici nous avons fait la même chose avec un croquis fait en Python.
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

Discussions similaires

  1. Requête, tri sur liste de choix
    Par seb.kepka dans le forum Access
    Réponses: 1
    Dernier message: 15/05/2006, 15h47
  2. Algo de tri par liste chainée
    Par Treuze dans le forum C
    Réponses: 3
    Dernier message: 30/12/2005, 15h05
  3. quel est le meilleur algo de tri de liste ?
    Par sony351 dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 24/07/2005, 03h00
  4. [langage] tri avancé, liste de listes
    Par schnecke dans le forum Langage
    Réponses: 6
    Dernier message: 29/03/2004, 15h00
  5. tri de liste chainée
    Par RezzA dans le forum C
    Réponses: 7
    Dernier message: 26/01/2003, 21h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo