Discussion :

[Ggamer]

Bonjour à tous,

J'ai une colle à vous poser. En gros, la question est : Comment rechercher le plus vite possible dans une liste ?

Voici mon problème (il est très simple !) : J'ai une zone de dessin avec des rectangles dont les coordonnées sont simplement mémorisées dans une liste du style :

Code :

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

[ (rect1, 10, 10, 20, 20), (rect2, 45, 60, 100, 230), ...]

Quand je clique dans cette zone de dessin, j'obtiens les coordonnées de la souris (x,y) grâce auxquelles je vais savoir si j'ai cliqué sur un de mes rectangles ou non.

Pour faire cette recherche, j'ai donc une fonction du style :

Code :

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

1
2
3
for rect in listeRectangles :
    if (rect[1] <= x <= rect[3]) and (rect[2] <= y <= rect[4]) :
        print u"j'ai cliqué sur le rectangle qui a le nom : " + rect[0]

Bref facile ! Mais mon souci est que quand j'ai 10 rectangles dans ma liste : la boucle est très vite faite et ma solution arrive vite... MAIS QUAND J'AI 500 RECTANGLES dans la liste, là c'est bien plus LENT !

Auriez-vous une autre méthode pour effectuer cette recherche plus vite ?

Je vous remercie pour vos réponses !

[anthyme]

psyco ?

[Ggamer]

psyco ?

..pathe ? Ben là, la réponse est trop obscure pour moi !

Par contre, pour les autres réponses, je vais essayer tout celà...

Merci à tous.

[xavier-Pierre]

je dirais même plus: psycopg
utilise une base postgres avec la cartouche spatiale postgis
il ya toutes les fonctions qui vont bien

[anthyme]

erf psyco est un compilateur jit qui divise le temsp d executionde *2 a *100 ...

maisregarde d abords le set()

[xavier-Pierre]

pour une recherche spatiale je pense qu'un sgbd comme postgis est plus approprié

[alexdevl]

Tu pourrais créer un dictionnaire :
pour toutes les couples x,y des rectangles associées à un rectangle
Cela donnerai un résultat direct :

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
 
 
rec={}
 
for x in range (10,20):
    for y in range (10,20):
        rec[(x,y)]="rect1"
 
for x in range (45,100):
    for y in range (60,230):
        rec[(x,y)]="rect2"
 
 
 
def test (dico,x,y):
    try :
        print dico[(x,y)]
    except KeyError :
        print "pas dans un rec"
 
test(rec,11,11)
test(rec,9,11)
test(rec,70,70)

[GnuVince]

Utilise un set, c'est fait spécialement pour de la recherche rapide:

Code :

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

1
2
3
4
5
6
7
8
9
 
>>> import timeit
>>> t1 = timeit.Timer('"875999" in L', 'L = map(str, range(1000000))')
>>> t2 = timeit.Timer('"875999" in S', 'S = set(map(str, range(1000000)))')
>>> t1.timeit(1000)
69.72383713722229
>>> t2.timeit(1000)
0.00040507316589355469
>>>

Pour trouver 1000 fois la chaîne "875999" dans une liste de "0" à "999999", utiliser une liste prend 70 secondes sur ma machine. Avec un set, c'est 4 DIX-MILLIÈME de secondes.

La liste cherche séquentiellement, donc plus l'élément est loin dans la liste, plus ça prend de temps à le trouver. Le set utilise une fonction de hashing, donc c'est quasi instantané. O(1) vs O(N).