Discussion :

[mister2502]

Bonjour,
sous python 2.5, je dois trouver la position d'une liste dans une liste de listes au format homogène (même nombre d'éléments, mêmes types).
Ex.:
dans

Code :

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

tab=[['359974000073A', 362.0], ['3017800110768F', 362.0], ['T083680094092', 62.0], ['3245390062390', 32.0]]

position de

t=['3017800110768F', 362.0]

renvoie ind=1.

Mon soucis, c'est que je peux avoir 2, 3 et + éléments dans t, que tab peut contenir jusqu'à un million de listes et que je dois répéter l'opération des millions de fois !
Bref, je dois optimiser à tout prix mes codes.
J'ai tenté simplement:

ind=tab.index(t)

mais c'est lent.
Est-ce intéressant de trier tab avant de lancer la recherche (éventuellement dichotomique) ?
J'avais essayé (si len(t)>1):

Code :

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

1
2
3
4
5
tab=numpy.array(tab)
inter=set(numpy.argwhere(tab==t[0]).T[0])
for v in range(1,len(t)):
         inter=inter.intersection(set(numpy.argwhere(tab==t[v]).T[0]))
ind=inter.pop()

ça marche, mais c'est encore + lent.
Et tab devient un ndarray de numpy, donc pas de méthode .index.

Qui aurait une solution + rapide?
Merci.

[pacificator]

Sans répondre directement à ta question, il serait peut être interessant d'utiliser le module psyco:

Code :

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

1
2
3
4
5
try:
    import psyco
    psyco.full()
except:
    pass

[mister2502]

Oui, mon main est déjà sous psyco.
Utile, mais ça n'accélère pas tout !

[oiffrig]

Si possible, utilise des tuples, comme ça, Python saura que c'est fixe, leur avantage: ils sont hashables, donc la comparaison ira plus vite.
Concernant le tri : inutile pour une seule recherche, rentable pour un nombre suffisamment grand de recherches.

[mister2502]

Hélas, je ne peux pas me passer des listes qui sont modifiables (par append, remove, etc...) contrairement aux tuples.
J'estime que j'ai un million de recherches de listes dans une liste d'environ 500000 listes à faire. Le tri est peut-être intéressant ?
Avez-vous des solutions ?

[tyrtamos]

Bonjour,

Les fonctions de tri de Python (sort() et sorted()) sont très rapides, et très adaptables grâce aux fonctions paramétrables cmp et key.

On peut aussi assez facilement passer par l'intermédiaire d'une liste d'index permettant d'obtenir les éléments triés sans modifier la liste principale.

Une fois la liste triée, si on insére ou on supprime un élément, on peut simplement corriger le tri sans le refaire grâce à une recherche de l'endroit précis de cette correction par recherche dichotomique.

Et d'une façon générale, la recherche dichotomique dans une liste triée, même de 1 million d'éléments est très très rapide.

Tout cela reste possible même si le même élément de la liste apparait plusieurs fois.

Tu peux t'inspirer de mes tutos ici concernant les tris et les recherches par dichotomies de listes d'objets quelconques: http://python.jpvweb.com/mesrecettes...herche_rapides

Tyrtamos

[oiffrig]

Je précise un peu pour les tuples, il s'agirait d'utiliser une liste de tuples au lieu d'une liste de listes, puisque tu as toi-même dit que les sous-listes sont toutes de même longueur.
Ensuite, concernant le tri, oui, là ce sera rentable !
Quelques données, en notant n la longueur de la grosse liste :
Recherche d'un élément, méthode classique : au plus n comparaisons
Tri : au moins en O(n log n) comparaisons
Recherche dichotomique : O(log n) comparaisons

Si on regarde d'un peu plus près, pour n = 1000000, ça devient rentable dès que le nombre de recherches est de l'ordre de 6... (plus généralement de l'ordre de log n)

[alexdevl]

Bonjour,
Si on place les éléments dans un dictionnaire ?,
Ce n'est pas optimisé en place mais c'est direct pour avoir le résultat

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
 
#!/usr/bin/env python
#coding=utf-8
import time
 
tab=[]
index={}
for i in xrange(1000000):
    tab.append(['359974000073A', i]) # Création du tableau
    index[tuple(tab[i])]=i # Attribution du dico
 
t0=time.clock()
print index[('359974000073A', 700000)] # Affichage d'un index par dico
print time.clock()-t0
t0=time.clock()
print tab.index(['359974000073A', 700000]) # Affichage d'un index par tab.index
print time.clock()-t0

Avec le dico : 7.43111205474e-005
Avec tab.index 0.213654249353

[mister2502]

Merci, c'est vrai que l'enregistrement avec des dictionnaires peut servir.
oiffrig, en passant à une liste de tuples au lieu d'une liste de listes, je gagne du temps (pas des masses!).
Je suis finalement passé par:
http://docs.python.org/library/bisect.html

tab.sort()
insert_point=bisect.bisect(tab,t)
is_present=tab[insert_point-1]==t

C'est très rapide.
Je vais voir s'il faut encore optimiser le code.