IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Rechercher dans une liste


Sujet :

Python

  1. #1
    Membre éclairé
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    328
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 328
    Par défaut Rechercher dans une liste
    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 !

  2. #2
    Membre éprouvé Avatar de anthyme
    Homme Profil pro
    Inscrit en
    Mars 2004
    Messages
    1 559
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2004
    Messages : 1 559
    Par défaut
    psyco ?

  3. #3
    Membre expérimenté Avatar de alexdevl
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    265
    Détails du profil
    Informations personnelles :
    Âge : 56
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Avril 2007
    Messages : 265
    Par défaut Dictionnaire pour chaque point
    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)

  4. #4
    Membre émérite
    Avatar de GnuVince
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2004
    Messages
    679
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2004
    Messages : 679
    Par défaut
    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).

  5. #5
    Membre éclairé
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    328
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 328
    Par défaut
    Citation Envoyé par anthyme Voir le message
    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.

  6. #6
    Membre émérite
    Homme Profil pro
    Inscrit en
    Janvier 2006
    Messages
    491
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Corse (Corse)

    Informations forums :
    Inscription : Janvier 2006
    Messages : 491
    Par défaut
    je dirais même plus: psycopg
    utilise une base postgres avec la cartouche spatiale postgis
    il ya toutes les fonctions qui vont bien

  7. #7
    Membre éprouvé Avatar de anthyme
    Homme Profil pro
    Inscrit en
    Mars 2004
    Messages
    1 559
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2004
    Messages : 1 559
    Par défaut
    erf psyco est un compilateur jit qui divise le temsp d executionde *2 a *100 ...

    maisregarde d abords le set()

  8. #8
    Membre émérite
    Homme Profil pro
    Inscrit en
    Janvier 2006
    Messages
    491
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Corse (Corse)

    Informations forums :
    Inscription : Janvier 2006
    Messages : 491
    Par défaut
    pour une recherche spatiale je pense qu'un sgbd comme postgis est plus approprié

  9. #9
    Membre éclairé
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    328
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 328
    Par défaut
    Un grand merci pour vos réponses...

    ... mais s'il me faut un dictionnaire pour décrypter un mot sur deux dans vos phrases : "postgres cartouche spatiale postgis"...

    Par contre, j'ai fait des recherches pendant quelques heures sur "SET" qui me paraît en effet très intéressant. Mais j'ai été incapable de l'appliquer (avec également MAP) à l'exemple que je vous donnais :

    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]
    Une âme charitable pourrait-elle me mettre sur le bonne voie svp ? Merci !

  10. #10
    Membre confirmé Avatar de KINENVEU
    Profil pro
    Inscrit en
    Mai 2007
    Messages
    184
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2007
    Messages : 184
    Par défaut Quelques pistes
    Je ne sais pas exactement ce que tu veux faire avec tes rectangles,
    mais je pense qu'il existe des solutions plus simples que de parcourir l'ensemble de tes rectangles pour savoir dans lequel tu as clicque.

    je ne sais pas ce que ca vaut, mais
    voici quelques pistes que je te conseille:

    1 - si tu cherches a developper un jeu avec des graphismes, regarde dans les modules de jeu, il doit exister des trucs deja tout fait.

    2 - si tes rectangles sont assez "stables", tu peux envisager un genre de pixelisation de ta zone de dessin. c'est a dire que tu construis une matrice (ou un dictionnaire) avec les coordonnees entieres de ta zone de dessin, et tu y "imprimes" l'ensemble de tes rectangles.(comme conseille plus haut par alexdevl)
    * Avantage: une fois ta zone de dessin pixelisee, la recherche du rectangle sur lequel tu cliques est tres rapide.
    * Inconvenient: a chaque fois que tu veux changer un rectangle, tu dois mettre a jour ta zone de dessin.

    3 - si tu travailles avec une interface graphique (GTK, ...)
    tu pourrais creer tes rectangles comme des objet derives des boutons. donc losque tu cliques dessus, le signal est directement relie a ton rectangle.

    4 - une autre idee rapide qui me vient aussi: si tu as beacoup de rectangles, tu peux faire des decoupages de ta zone de dessin. genre tu decoupes ta zone de dessin en plusieurs sous-zones avec chacune des sous-zones, ...
    un genre de pre-tri des rectangles pour optimiser tes recherches.
    tu peux par exemple travailler avec des quadrans recursifs.

    je ne sais pas si ca pourra t'aider, mais bonne chance.

  11. #11
    Membre Expert
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Par défaut Ma proposition
    Le défi intellectuel m'a intéressé. Il m'a semblé que ce problème qui peut s'énoncer simplement devait pouvoir se résoudre simplement.
    En voyant
    if (rect[1] <= x <= rect[3]) and (rect[2] <= y <= rect[4]) :
    j'ai tout de suite pensé que c'était déjà astreindre le programme à un gros boulot puisqu'on l'oblige, sur tous les rectangles, à faire 2 tests.
    Il me semble que
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    if (rect[1] <= x <= rect[3]) :
        if (rect[2] <= y <= rect[4]) :
    doit déjà améliorer les choses.
    L'absence d'instruction break prévue quand la condition est vérifiée donne aussi à penser que les rectangles ne sont pas nécessairement disjoints mais peuvent se chevaucher.
    Ces deux remarques m'ont conduit à penser à découper le problème de recherche en trois: une étape sur l'abscisse fournie, une étape sur l'ordonnée fournie, et une étape d'intersection des deux ensembles trouvés.
    Pour cela, il faut préalablement référencer les positions de tous les rectangles. Je l'ai fait ainsi: on découpe le plan en bandes verticales dont les limites sont toutes les abscisses r[1] , r[3] et on référence les rectangles sur lesquels passe chaque bande; de même on référence tous les rectangles qui passe dans chacune des bandes horizontales définies par l'ensemble des ordonnées r[2], r[4].
    J'ai rapidement (à mon étonnement) écrit le programme suivant, qui tourne bien, mais n'est pas parfait:
    - en le rédigeant, je n'ai pensé qu'à des rectangles et des points examinés situés dans le quadrant (x>=0, y>=0). On doit pouvoir généraliser le programe à l'ensemble du plan
    - je n'ai pas regardé précisément ce qu'il se passe quand le point examiné est sur un segment de droite délimitant un rectangle. Peut être que dans certains cas, le point ne sera pas détécté être dans un rectangle alors qu'il l'est , et inversement....? Il faut regarder de près.

    Ma solution se rapproche de l'idée 4 de kinenveu.
    Il faut voir ce que cela donne en temps d'exécution quand il y a 500 rectangles à référencer. J'aimerais bien savoir, mais je n'ai pas le courage de définir à la main une liste de 500 rectangles.

    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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    lr = [ ('rect1', 10, 10, 20, 20), ('rect2',30,18,60,60), ('rect3',40,50,60,70),('rect4',23,40,48,80)]
    print lr
     
     
    # RÉFÉRENCEMENT PRÉALABLE DES RECTANGLES
    ##############################E#########
     
    listex = [] # liste des limites des bandes verticales
    listey = [] # liste des limites des bandes horizontales
    # Création de ces deux listes
    for r in lr:
        if r[1] not in listex:
            listex.append(r[1])
        if r[2] not in listey:
            listey.append(r[2])
        if r[3] not in listex:
            listex.append(r[3])
        if r[4] not in listey:
            listey.append(r[4])
    listex.sort()
    listey.sort()
    print 'listex =',listex
    print 'listey =',listey
     
     
    # Création du dictionnaire dx de listes de rectangles dont les clés sont les bandes verticales
    # et du dictionnaire dy de listes dont les clés sont les bandes horizontales.
    # En réalité, chaque bande verticale est repérée par sa limite gauche listex[k],
    # et chaque bande horizontale est repérée par sa limite inférieure listy[k].
    dx = {}
    dx[0] = []
    dx[listex[-1]] = []
    for k in range(0,len(listex)-1): # pour chaque bande verticale definie par k
        print '\nk =',k,' intervalle en x : (',listex[k],',',listex[k+1],')'
        li = []
        for r in lr: # on passe en revue successivement tous les rectangles
            print r[0],' : x =',r[1],'a',r[3],
            if r[1]<=listex[k] and r[3]>=listex[k+1]: # on détermine si le rectangle intersecte la bande examinée
                print r[0],'est dedans'
                li.append(r[0]) # tout rectangle intersectant la bande est référenc dans une liste provisoire
            else: # simplement pour l'organisation de l'affichage
                print ''
        dx[listex[k]] = li # la liste des rectangles intersectant la bande k est mise dans le dictionnaire dx
                            # sous la clé=limite gauche de la bande
     
     
     
    dy = {}
    dy[0] = []
    dy[listey[-1]] = []
    for k in range(0,len(listey)-1):
        print '\nk =',k,' intervalle en y : (',listey[k],',',listey[k+1],')'
        li = []
        for r in lr:
            print r[0],' : y =',r[2],'a',r[4],
            if r[2]<=listey[k] and listey[k+1]<=r[4]:
                print r[0],'est dedans'
                li.append(r[0])
            else: # simplement pour l'organisation de l'affichage
                print ''
        dy[listey[k]] = li
     
     
    print 'dx =',dx
    print 'dy =',dy
     
     
     
     
    # UTILISER LE PROGRAMME
    #######################
     
    print ''
    while 1:
        a = input('\nEntrer abscisse : ')
        b = input('Entrer ordonnee : ')
     
        xt = 0
        for x in listex:
            if x<=a:
                xt = x
            else:
                break
     
        yt = 0
        for y in listey:
            if y<=b:
                yt = y
            else:
                break
     
        result = []
        for r in dx[xt]:
            if r in dy[yt]:
                result.append(r)
     
        if result!=[]:
            print 'Le point (',a,',',b,') est dans les rectangles :',result
        else:
            print 'Le point est en dehors de tout rectangle.'

Discussions similaires

  1. [VBA-Excel] Effectuer une recherche dans une liste view
    Par Miles Raymond dans le forum Macros et VBA Excel
    Réponses: 6
    Dernier message: 23/11/2006, 17h21
  2. Imposer une methode Equals pour une recherche dans une List
    Par petozak dans le forum Débuter avec Java
    Réponses: 5
    Dernier message: 03/10/2006, 10h41
  3. Réponses: 2
    Dernier message: 07/07/2006, 10h00
  4. Réponses: 2
    Dernier message: 10/10/2005, 02h25
  5. Recherche dans une liste non trié
    Par Oberown dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 13/09/2004, 13h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo