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