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 et insertion dans une liste de liste


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Décembre 2005
    Messages
    41
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 41
    Par défaut tri et insertion dans une liste de liste
    Bonjour, j'ai écrit un petit programme qui:

    1- insere un élément d'une liste (sim) dans une autre liste (k_nn).
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    k_nn = [[999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X']]
    sim = [[2,'B'], [9,'F'], [3,'C'], [130, 'J'], [40,'I'], [23,'G'], [1, 'A'], [3,'C'], [8,'E'], [3,'C'], [25,'H'], [6,'D']]
    2- l'élément inséré est une liste, par exemple l'élément
    3- l'insertion par ordre de plus grand (tri):
    le output doit être celà

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    [[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E']]
    Voilà mon programme:
    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
    k_nn = [[999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X']]
    sim = [[2,'B'], [9,'F'], [3,'C'], [130, 'J'], [40,'I'], [23,'G'], [1, 'A'], [3,'C'], [8,'E'], [3,'C'], [25,'H'], [6,'D']]
     
    def add_s(boolean, s):
    	i = 0
    	while boolean == False:
     
    		if s[0] < k_nn[i][0]:
    			k_nn.insert(i, s)
    			del k_nn[7:]
    			boolean = True
    		else:
    			i += 1
    boolean = False
    maxi = len(k_nn)
     
    for s in sim:
        if s[0] < k_nn[maxi-1]:
            add_s (boolean, s)
    print k_nn
    L'erreur :
    Traceback (most recent call last):
    File "C:\Users\....\Desktop\.....\test_1.py", line 25, in <module>
    add_s (boolean, s)
    File "C:\Users\....\Desktop\......\test_1.py", line 14, in add_s
    if s[0] < k_nn[i][0]:
    IndexError: list index out of range
    [Finished in 0.2s with exit code 1]

  2. #2
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Salut,

    Ta première comparaison n'est pas bonne.
    Remarque que tu n'as pas besoin de maxi = len(k_nn)
    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
     
    >>> k_nn = [[999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X']]
    >>> sim = [[2,'B'], [9,'F'], [3,'C'], [130, 'J'], [40,'I'], [23,'G'], [1, 'A'], [3,'C'], [8,'E'], [3,'C'], [25,'H'], [6,'D']]
    >>> sim[0][0]
    2
    >>> k_nn[-1]
    [999, 'X']
    >>> # donc
    ... sim[0][0] < k_nn[-1]
    True
    >>> # OK, resultat attendu, mais :
    ... k = [1, 'j']
    >>> sim[0][0] < k
    True
    >>> # Faux !
    C'est, bien sur sim[0][0] < k_nn[-1][0] qu'il faut faire.

    Cependant, ne serait-ce pas simplement ceci que tu veux faire:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    >>> new = sorted(sim)
    >>> new
    [[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E'], [9, 'F'], [23, 'G'], [25, 'H'], [40, 'I'], [130, 'J']]
    >>> k_nn = new[:7]
    >>> k_nn
    [[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E']]
    >>>

  3. #3
    Membre averti
    Inscrit en
    Décembre 2005
    Messages
    41
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 41
    Par défaut
    Citation Envoyé par VinsS Voir le message
    Salut,

    Ta première comparaison n'est pas bonne.
    Remarque que tu n'as pas besoin de maxi = len(k_nn)
    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
     
    >>> k_nn = [[999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X']]
    >>> sim = [[2,'B'], [9,'F'], [3,'C'], [130, 'J'], [40,'I'], [23,'G'], [1, 'A'], [3,'C'], [8,'E'], [3,'C'], [25,'H'], [6,'D']]
    >>> sim[0][0]
    2
    >>> k_nn[-1]
    [999, 'X']
    >>> # donc
    ... sim[0][0] < k_nn[-1]
    True
    >>> # OK, resultat attendu, mais :
    ... k = [1, 'j']
    >>> sim[0][0] < k
    True
    >>> # Faux !
    C'est, bien sur sim[0][0] < k_nn[-1][0] qu'il faut faire.

    Cependant, ne serait-ce pas simplement ceci que tu veux faire:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    >>> new = sorted(sim)
    >>> new
    [[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E'], [9, 'F'], [23, 'G'], [25, 'H'], [40, 'I'], [130, 'J']]
    >>> k_nn = new[:7]
    >>> k_nn
    [[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E']]
    >>>
    Merci pour votre réponse.
    Votre dernière suggestion (sorted(sim)). M'a donnée une autre idée.
    Pour mieux expliquer mon objectif.
    Dans mon programme principal il y a une fonction (similarity) qui calcule sim[1][0], exemple
    sim[1] = [2, 'B'] et sim[1][0] = 2

    La fonction (similarity) calcule et envoi à la fonction de tri s = [nombre, 'lettre']
    Puis la 2ème fonction (tri) ajoute l'élément (s) dans une liste (k_nn) en fonction du nombre (ajouter avec un tri)
    à condition la liste k_nn . Ne doit pas dépasser 7 éléments.

  4. #4
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Tu veux dire que la liste sim n'est pas données toute faite mais à chaque élément nouveau retourné par similarity() il faut procéder à son insertion dans k_nn.

    Alors tu peux faire comme ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    def add_s(elem):
        k_nn.append(elem)
        k_nn = sorted(k_nn)[:7]

  5. #5
    Membre averti
    Inscrit en
    Décembre 2005
    Messages
    41
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 41
    Par défaut
    Citation Envoyé par VinsS Voir le message
    Tu veux dire que la liste sim n'est pas données toute faite mais à chaque élément nouveau retourné par similarity() il faut procéder à son insertion dans k_nn.

    Alors tu peux faire comme ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    def add_s(elem):
        k_nn.append(elem)
        k_nn = sorted(k_nn)[:7]
    Merci pour votre aide
    J'ai fait cela:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    k_nn = [[999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X'], [999,'X']]
    sim = [[2,'B'], [9,'F'], [3,'C'], [130, 'J'], [40,'I'], [23,'G'], [1, 'A'], [3,'C'], [8,'E'], [3,'C'], [25,'H'], [6,'D']]
     
     
    for elem in sim:
        if elem[0] < k_nn[-1]:
            k_nn.append(elem)
            k_nn = sorted(k_nn)[:7]
     
    print k_nn

    Avez-vous une idée d'un algorithme pour des K plus proches voisins avec sa documentation ?

  6. #6
    Expert confirmé
    Avatar de tyrtamos
    Homme Profil pro
    Retraité
    Inscrit en
    Décembre 2007
    Messages
    4 486
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2007
    Messages : 4 486
    Billets dans le blog
    6
    Par défaut
    Bonjour,

    Je n'ai pas tout suivi, mais il me semble dommage de devoir trier à chaque insertion. Il vaudrait mieux trouver l'emplacement d'insertion avec une méthode rapide comme la dichotomie, et insérer avec .insert(...).

    Mais bien sûr, cela ne se justifierait que pour des listes très longues (ce qui n'est pas le cas des exemples).

    En cas de besoin, je pourrais proposer du code pour faire ça.

Discussions similaires

  1. Réponses: 1
    Dernier message: 08/10/2011, 05h16
  2. Tri dans une zone de liste
    Par scorpion1611 dans le forum VBA Access
    Réponses: 1
    Dernier message: 12/02/2008, 15h00
  3. [MySQL] Insertion dans une liste déroulante depuis une BD
    Par merymaru dans le forum PHP & Base de données
    Réponses: 6
    Dernier message: 24/05/2007, 21h28
  4. insertion dans une liste déroulante
    Par x0249 dans le forum IHM
    Réponses: 3
    Dernier message: 23/05/2007, 15h09
  5. [LG]Tri par insertion dans une liste chainée
    Par mister_dsg dans le forum Langage
    Réponses: 4
    Dernier message: 18/12/2003, 22h34

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