Python : Liste vs Dict pour look up table

Question

J'ai environ 10millions valeurs que j'ai besoin de mettre dans un certain type de look up table, donc je me demandais ce qui serait plus efficace d'une liste ou dict?

Je sais que vous pouvez faire quelque chose comme ceci pour les deux:

if something in dict_of_stuff:
    pass

et

if something in list_of_stuff:
    pass

Ma pensée est que le dict sera plus rapide et plus efficace.

Merci pour votre aide.

EDIT 1
Peu plus d'infos sur ce que je suis en train de faire. Euler Problème 92. Je suis en train de faire une table pour voir si une valeur calculée a tous les prêts été calculé.

EDIT 2
L'efficacité pour les regarder.

EDIT 3
Il n'existe pas de valeurs assosiated avec la valeur...de sorte que serait un jeu de mieux?

Answer 1

Vitesse

Recherches dans les listes de O(n), les recherches dans les dictionnaires sont amorti O(1), à l'égard du nombre d'éléments dans la structure de données. Si vous n'avez pas besoin d'associer des valeurs, utiliser des ensembles.

De mémoire

Les deux dictionnaires et des jeux de l'utilisation des fonctions de hachage et ils utilisent beaucoup plus de mémoire que seulement pour objet de stockage. Selon A. M. Kuchling dans Belle de Code, la mise en œuvre essaie de garder le hachage 2/3 plein, de sorte que vous pourriez déchets de très peu de mémoire.

Si vous n'avez pas d'ajouter de nouvelles entrées à la volée (dont vous le faites, basées sur la mise à jour de votre question), il pourrait être utile pour trier la liste et utiliser les binaires de recherche. Ce est O(log n), et est susceptible d'être plus lente pour les cordes, impossible pour les objets qui n'ont pas d'ordre naturel.

Answer 2

Une dict est une table de hachage, donc c’est vraiment rapide pour trouver les clés. Ainsi, entre dict et liste, dict serait plus rapide. Mais si vous n’avez pas une valeur à associer, il est même préférable d’utiliser un ensemble. C’est une table de hachage, sans la partie « table ».

---

EDIT : pour votre nouvelle question, oui, un ensemble serait préférable. Il suffit de créer 2 ensembles, l’un pour les séquences s’est terminés en 1 et d’autres pour les séquences s’est terminés en 89. J’ai réussi a résolu ce problème en utilisant les ensembles.

Answer 3

``est exactement ce que vous voulez. Les recherches d’o (1) et plus petit qu’une dict.

Answer 4

J'ai fait un peu de benchmarking et il s'avère que dict est plus rapide que les deux liste et définir de grands ensembles de données, l'exécution de python 2.7.3 sur un core i7 CPU sous linux:

• python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

  10 boucles, best of 3: 64.2 msec par boucle

• python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

  10000000 boucles, best of 3: 0.0759 usec par boucle

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  1000000 boucles, best of 3: 0.262 usec par boucle

Comme vous pouvez le voir, dict est considérablement plus rapide que la liste et environ 3 fois plus vite que prévu. Dans certaines applications, vous pouvez toujours choisir de définir pour la beauté de la chose, bien que. Et si les ensembles de données sont vraiment petites (< 1000 éléments) des listes d'exécuter assez bien.

Answer 5

Si les données sont uniques set() sera le plus efficace, mais de deux - dict (qui nécessite aussi unicité, oops  :)