Recherche rapide de liste

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:

---

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:

---

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.

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

Code:

---

1 2 3 4 5

try: import psyco psyco.full() except: pass

---

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

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.

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 ?

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

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)

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:

---

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

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.