Python: comment vérifier si un élément est dans une liste de manière efficace?
J'ai une liste de chaînes de caractères (mots), et, alors que je suis de l'analyse d'un texte, j'ai besoin de vérifier si un mot appartient au groupe de mots de ma liste.
Cependant, mon entrée est assez grand (environ 600 millions de lignes), et vérifier si un élément appartient à une liste est un O(n) opérations selon la documentation Python.
Mon code est quelque chose comme:
words_in_line = []
for word in line:
if word in my_list:
words_in_line.append(word)
Que ça prend trop de temps (jours, en fait), j'ai voulu améliorer cette partie qui est la plupart du temps. J'ai un oeil à Python collections, et, plus précisément, à deque. Cependant, le seul à donner un O(1) temps de fonctionnement de l'accès à la tête et la queue d'une liste, pas dans le milieu.
Faire quelqu'un a une idée sur comment le faire dans une meilleure façon?
O(1) en effet, en supposant que relativement peu de collisions de hachage 🙂
Vous ne pouvez pas vérifier si un élément est dans une liste de manière efficace. Ce n'est pas ce que sont les listes de pour la. Vous devez choisir vos types de données (en particulier les collections) pour être adapté à ce que vous allez faire avec eux, car aucun type de données n'est bon en tout.
OriginalL'auteur Jiehong | 2012-06-07
Vous devez vous connecter pour publier un commentaire.
Vous pourriez envisager une trie ou un DAWG ou une base de données. Il existe plusieurs implémentations de Python de la même chose.
Ici est une certaine forme de temps pour vous de considérer un ensemble vs une liste:
Imprime:
ie, correspondant à un ensemble de 10000 mots à l'encontre d'un ensemble de 250 000 mots est 17,085 X plus rapide que la contrepartie d'une liste de même 10000 mots dans une liste de la même 250 000 mots. À l'aide d'une liste pour la source et un ensemble d'adhésion de test est 28,392 X plus rapide qu'une liste non triée seul.
De l'adhésion les tests, une liste est en O(n) et définit et dicts sont en O(1) pour les recherches.
Conclusion: mieux Utiliser les structures de données de plus de 600 millions de lignes de texte!
Cela sonne bien. Mon premier code a besoin d'environ 500 jours de calcul, et environ 50 jours avec un astucieux re-factoring. Maintenant, il n'a besoin que quelque chose comme 1 heure! Même si mon jeu est de 200 000 de long, c'est impressionnant.
La clé de retarder facteur est le Python opérateur
in
contre le une liste. Si vous mélangez ces deux structures de données et utiliser une liste pour l'accès aux données (c'est à dire, utiliserfor word in test_list
) et de les utiliser ensemble pour l'adhésion de stockage (c'est à dire,if word in all_word_set
), il est même plus rapide. Les ensembles sont plus rapides à l'adhésion d'essai; les listes sont plus rapides à créer un accès, d'une manière linéaire.Know your tools Luke.
C'est ce que j'ai utilisé après j'ai vu votre réponse! Merci encore.
N'hésitez pas à accepter la réponse si cela vous a aidé.
OriginalL'auteur the wolf
Il utilise compréhension de liste
qui serait plus efficace que le code que vous avez posté, mais la façon dont beaucoup plus pour votre énorme quantité de données est difficile de savoir.
if word in my_list
), il n'affecte pas le vrai problème.OriginalL'auteur Levon
Je ne suis pas clair sur pourquoi vous avez choisi une liste, en premier lieu, mais voici quelques alternatives:
À l'aide d'un set() est probablement une bonne idée. C'est très rapide, bien que non ordonnée, mais parfois, c'est exactement ce qui est nécessaire.
Si vous avez besoin de choses ordonné et avoir arbitraire des recherches ainsi, vous pouvez utiliser un arbre de la sorte:
http://stromberg.dnsalias.org/~strombrg/python-arbre-et-tas-comparaison/
Si l'appartenance à des essais avec un petit nombre de faux positifs, ici ou là, est acceptable, vous pouvez vérifier dans un filtre de bloom:
http://stromberg.dnsalias.org/~strombrg/drs-bloom-filtre/
En fonction de ce que vous êtes en train de faire un trie pourrait également être très bon.
OriginalL'auteur user1277476
Il y a deux améliorations que vous pouvez faire ici.
dequeue
, depuis son ajout performance est supérieure à la liste.Ci-dessous est un exemple de mise en œuvre basé sur mes suggestions (en optant pour un générateur, car je ne peux imaginer que vous avez besoin de tous ces mots dans la mémoire à la fois).
input.txt
Sortie
OriginalL'auteur cheeken