Le moyen le plus rapide pour rechercher une liste en python

Quand vous faites quelque chose comme "test" in a où a une liste python de faire une recherche séquentielle sur la liste ou faut-il créer une table de hachage de la représentation afin d'optimiser la recherche? Dans l'application, j'ai besoin de cela pour je vais faire beaucoup de recherches sur la liste, donc serait-il préférable de faire quelque chose comme b = set(a) et puis "test" in b? Notez également que la liste des valeurs que je vais avoir de ne pas avoir de doublons et je n'ai pas vraiment de soins au sujet de l'ordre dans; j'ai juste besoin d'être en mesure de vérifier l'existence d'une valeur.

InformationsquelleAutor blcArmadillo | 2011-05-13
  1. 52

    Également de noter que la liste des valeurs que je vais avoir de ne pas avoir de doublons et je n'ai pas vraiment de soins au sujet de l'ordre dans; j'ai juste besoin d'être en mesure de vérifier l'existence d'une valeur.

    Ne pas utiliser une liste, utilisez un set() à la place. Il a exactement les propriétés que vous souhaitez, y compris un ultra-rapide in test.

    J'ai vu la vitesse de 20x et plus élevés dans les endroits (surtout lourds calculs) où une seule liste a été changé pour un jeu.

    • sont le chemin à parcourir puisque vous n'avez pas de données en double et ne se soucient pas de l'ordre de plus, vous pouvez toujours énumérer les membres de l'ensemble ou de se transformer rapidement en une liste, si nécessaire.
    • J'ai utilisé cela et passer des choses extrêmement. Je vous remercie.
    • Wow, j'ai eu un muet script de force brute par le biais de deux fichiers afin de trouver des lignes similaires, et cela il suffit de couper le temps vers le bas à partir de ~20 min à moins de 1. Merci!
    • Avec une liste très importante et presque ~2 millions vérifie le temps de calcul est descendu de 3 heures à < 1 min !!!!
    InformationsquelleAutor orlp
  2. 8

    "test" in a avec une liste a va faire une recherche linéaire. La configuration d'une table de hachage sur la mouche serait beaucoup plus cher qu'une recherche linéaire. "test" in b de l'autre coté, faire un amoirtised O(1) hachage look-up.

    Dans le cas que vous décrivez, il ne semble pas être une raison pour utiliser une liste sur un jeu.

    • Ceci n'est vrai que si il y en a beaucoup des recherches effectuées sur b après il est construit. Si b doit être (re)construit à chaque fois qu'une recherche est effectuée, puis "test" in b sera plus lente, depuis la construction de l'ensemble ne serait pas linéaire.
    • À partir de l'OP: "Dans l'application j'ai besoin pour ce que je vais faire beaucoup de recherches sur la liste [...]". Semble comme il y a de nombreuses recherches.
    • Je suis d'accord c'est la bonne solution, juste en essayant de la rendre claire.
    InformationsquelleAutor Sven Marnach
  3. 1

    Je pense qu'il serait mieux d'aller avec l'ensemble de la mise en œuvre. Je sais pour un fait que les ensembles de O(1) recherche de temps. Je pense que les listes d'O(n) temps de recherche. Mais même si les listes sont également en O(1) recherche, vous ne perdez rien à commutation de jeux.

    De plus, les ensembles de ne pas permettre à des valeurs en double. Cela rendra votre programme un peu plus de mémoire efficace, ainsi

    InformationsquelleAutor inspectorG4dget
  4. -1

    Liste et les tuples semble avoir le même temps, et à l'aide de "en" est lent pour des données de grande taille:

    >>> t = list(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.66235494614
>>> t = tuple(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.6594209671

    Ici est bien meilleure solution: Le moyen le plus efficace pour une recherche/la recherche dans une liste énorme (python)

    C'est super rapide:

    >>> from bisect import bisect_left
>>> t = list(range(0, 1000000))
>>> a=time.time();x = [t[bisect_left(t,b)]==b for b in range(100234,101234)];print(time.time()-a)
0.0054759979248
    • La liste doit être triée en premier.
    InformationsquelleAutor Grzegorz Świerad