Discussion :

[zargooo04]

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

Code :

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

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

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]

[VinsS]

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

[zargooo04]

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.

[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 :

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]

[zargooo04]

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 ?

[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.

[zargooo04]

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 :

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

[tyrtamos]

Bonjour,

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

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

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

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 :

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

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 :

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

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

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

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
#############################################################################
# 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 :

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

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!

[zargooo04]

Bonjour,

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

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

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

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 :

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

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 :

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

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

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

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
#############################################################################
# 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 :

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

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
Merci j'aime bien votre proposition.
Merci pour le partage