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 :

Recherche rapide de liste


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2009
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2009
    Messages : 58
    Par défaut 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 : 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.

  2. #2
    Membre Expert Avatar de pacificator
    Profil pro
    Inscrit en
    Août 2006
    Messages
    1 074
    Détails du profil
    Informations personnelles :
    Âge : 45
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 074
    Par défaut
    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

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2009
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2009
    Messages : 58
    Par défaut
    Oui, mon main est déjà sous psyco.
    Utile, mais ça n'accélère pas tout !

  4. #4
    Membre émérite

    Profil pro
    Inscrit en
    Août 2004
    Messages
    723
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2004
    Messages : 723
    Par défaut
    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.

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2009
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2009
    Messages : 58
    Par défaut
    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 ?

  6. #6
    Expert confirmé
    Avatar de tyrtamos
    Homme Profil pro
    Retraité
    Inscrit en
    Décembre 2007
    Messages
    4 486
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2007
    Messages : 4 486
    Billets dans le blog
    6
    Par défaut
    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

Discussions similaires

  1. Recherche rapide de chaine dans une liste
    Par Esil2008 dans le forum Langage
    Réponses: 3
    Dernier message: 04/11/2008, 14h03
  2. Recherche rapide dans une liste
    Par jblecanard dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 02/09/2008, 23h53
  3. Recherche rapide
    Par Pylz dans le forum C++Builder
    Réponses: 14
    Dernier message: 28/02/2005, 13h53
  4. 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
  5. [Kylix] Combobox recherche rapide
    Par litbos dans le forum EDI
    Réponses: 3
    Dernier message: 29/08/2003, 10h13

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