tri et insertion dans une liste de liste

Version imprimable

Bonjour, j'ai écrit un petit programme qui:

1- insere un élément d'une liste (sim) dans une autre liste (k_nn).
Code:

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

Code:

sim[1] = [9,'F']

3- l'insertion par ordre de plus grand (tri):
le output doit être celà

Code:

[[1, 'A'], [2, 'B'], [3, 'C'], [3, 'C'], [3, 'C'], [6, 'D'], [8, 'E']]

Voilà mon programme:
Code:

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]

Salut,

Ta première comparaison n'est pas bonne.
Remarque que tu n'as pas besoin de maxi = len(k_nn)

Code:

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:

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']]
>>>

Citation:
Envoyé par VinsS
Salut,

Ta première comparaison n'est pas bonne.
Remarque que tu n'as pas besoin de maxi = len(k_nn)
Code:

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:

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.

26/04/2016, 13h19
VinsS
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:

1 2 3 4 def add_s(elem): k_nn.append(elem) k_nn = sorted(k_nn)[:7]

Citation:
Envoyé par VinsS
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:

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:

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 ? :)

26/04/2016, 17h07
tyrtamos

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.

Citation:

Envoyé par tyrtamos

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.

Merci pour votre proposition.
Oui, pour mon programme principal la liste ne dépasse pas 24 éléments.
Même avec 24 éléments, votre suggestion est bonne un tri à chaque insertion.
Sinon avez-vous une autre proposition.

J'ai suivi votre idée. J'ai fait cela:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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) k_nn.pop() boolean = True else: i += 1 boolean = False for s in sim: if s[0] < k_nn[-1][0]: add_s (boolean, s) print k_nn

Bonjour,

Voilà un petit code pour rechercher très rapidement un emplacement dans une liste par dichotomie:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def dichot(x, L, key=lambda c: c): """On cherche l'index de l'élément x dans la liste L Retourne une liste: [code, index] si [-1, i] => x non trouvé, mais il est avant l'index i si [0, i] => x trouvé à l'index i si [1, i] => x non trouvé, mais il est après l'index i de fin Si x est trouvé en plusieurs exemplaires, on trouve l'index du 1er. key permet de trouver l'élément trié dans une liste d'objets complexes """ i, j = 0, len(L)-1 while i<j: k=(i+j)//2 if cmp(x,key(L[k]))<=0: j = k else: i = k+1 return [cmp(x,key(L[i])), i]
Le code fonctionne avec Python 2. Pour l'adapter à Python 3, il faut lui ajouter la définition de cmp (fonction de comparaison) qui n'existe plus:

Code:

cmp = lambda a, b: (a > b) - (a < b)

Cette fonction "dichot" comporte un argument "key" qui fonctionne de la même façon que "sort" ou "sorted": il permet de chercher dans une liste de listes ou même dans une liste d'objets plus complexes. C'est logique, parce que la recherche par dichotomie suppose que la liste est déjà triée selon le même critère que le critère de recherche.

Le docstring indique ce que la fonction retourne: l'index trouvé, précédé par un code de résultat.

Prenons justement l'exemple d'insertion dans une liste de listes, déjà triée selon le 2ème élément des sous-listes (=la lettre):

Code:

L = [[1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']]

Elle aura été si nécessaire triée comme ça:

Code:

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

On va maintenant insérer plusieurs sous-listes qui vont couvrir tous les cas possibles:
Code:

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 ############################################################################# # insertion de [3, 'A'] qui sera avant le 1er élément de la liste y = [3, 'A'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'F']: le 'F' existant déjà, le [3, 'F'] sera inséré juste avant y = [3, 'F'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'J'] avec un 'J' qui n'existe pas: l'insertion sera au bon endroit y = [3, 'J'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'Z']: l'insertion sera à la fin de la liste y = [3, 'Z'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print
Ce qui affichera:
Code:

1 2 3 4 5 6 7 8 9 10 11 Insertion de [3, 'A'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'F'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'J'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [3, 'J'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'Z'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [3, 'J'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X'], [3, 'Z']]
Le "i+int(c==1)" est facile à comprendre: si c==1, la valeur à insérer est au delà du dernier indice. Au lieu d'utiliser append, on utilise insert avec un index supérieur au dernier index. Et comme int(True)==1, on trouve cet index.

Pour illustrer la rapidité de la fonction dichot proposée, on peut tester facilement: on retrouve l'emplacement d'insertion dans une liste de un million d'entier en moins de ... 1/100000 seconde! Cela se comprend bien puisqu'il faut seulement 20 boucles (2**20) avec la dichotomie pour trouver une valeur parmi un million de valeurs triées.

Tu trouveras plus d'infos sur le sujet sur mon site: http://python.jpvweb.com/mesrecettes...?id=dichotomie. Et comme j'ai du retard pour la mise à jour, c'est encore compatible avec Python 2!

Citation:
Envoyé par tyrtamos
Bonjour,

Voilà un petit code pour rechercher très rapidement un emplacement dans une liste par dichotomie:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def dichot(x, L, key=lambda c: c): """On cherche l'index de l'élément x dans la liste L Retourne une liste: [code, index] si [-1, i] => x non trouvé, mais il est avant l'index i si [0, i] => x trouvé à l'index i si [1, i] => x non trouvé, mais il est après l'index i de fin Si x est trouvé en plusieurs exemplaires, on trouve l'index du 1er. key permet de trouver l'élément trié dans une liste d'objets complexes """ i, j = 0, len(L)-1 while i<j: k=(i+j)//2 if cmp(x,key(L[k]))<=0: j = k else: i = k+1 return [cmp(x,key(L[i])), i]
Le code fonctionne avec Python 2. Pour l'adapter à Python 3, il faut lui ajouter la définition de cmp (fonction de comparaison) qui n'existe plus:

Code:

cmp = lambda a, b: (a > b) - (a < b)

Cette fonction "dichot" comporte un argument "key" qui fonctionne de la même façon que "sort" ou "sorted": il permet de chercher dans une liste de listes ou même dans une liste d'objets plus complexes. C'est logique, parce que la recherche par dichotomie suppose que la liste est déjà triée selon le même critère que le critère de recherche.

Le docstring indique ce que la fonction retourne: l'index trouvé, précédé par un code de résultat.

Prenons justement l'exemple d'insertion dans une liste de listes, déjà triée selon le 2ème élément des sous-listes (=la lettre):

Code:

L = [[1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']]

Elle aura été si nécessaire triée comme ça:

Code:

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

On va maintenant insérer plusieurs sous-listes qui vont couvrir tous les cas possibles:
Code:

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 ############################################################################# # insertion de [3, 'A'] qui sera avant le 1er élément de la liste y = [3, 'A'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'F']: le 'F' existant déjà, le [3, 'F'] sera inséré juste avant y = [3, 'F'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'J'] avec un 'J' qui n'existe pas: l'insertion sera au bon endroit y = [3, 'J'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print ############################################################################# # insertion de [3, 'Z']: l'insertion sera à la fin de la liste y = [3, 'Z'] print "Insertion de ", y c, i = dichot(y[1], L, key=lambda v:v[1]) L.insert(i+int(c==1), y) print L print
Ce qui affichera:
Code:

1 2 3 4 5 6 7 8 9 10 11 Insertion de [3, 'A'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'F'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'J'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [3, 'J'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X']] Insertion de [3, 'Z'] [[3, 'A'], [1, 'B'], [0, 'D'], [4, 'E'], [7, 'E'], [3, 'F'], [2, 'F'], [5, 'G'], [3, 'J'], [6, 'Q'], [9, 'S'], [3, 'T'], [8, 'X'], [3, 'Z']]
Le "i+int(c==1)" est facile à comprendre: si c==1, la valeur à insérer est au delà du dernier indice. Au lieu d'utiliser append, on utilise insert avec un index supérieur au dernier index. Et comme int(True)==1, on trouve cet index.

Pour illustrer la rapidité de la fonction dichot proposée, on peut tester facilement: on retrouve l'emplacement d'insertion dans une liste de un million d'entier en moins de ... 1/100000 seconde! Cela se comprend bien puisqu'il faut seulement 20 boucles (2**20) avec la dichotomie pour trouver une valeur parmi un million de valeurs triées.

Tu trouveras plus d'infos sur le sujet sur mon site: http://python.jpvweb.com/mesrecettes...?id=dichotomie. Et comme j'ai du retard pour la mise à jour, c'est encore compatible avec Python 2!
Bonjour :D
Merci j'aime bien votre proposition.
Merci pour le partage :)