J'ai une liste de chaînes (mots comme) et, alors que je suis en train d'analyser un texte, j'ai besoin de vérifier si un mot appartient au groupe de mots de ma liste actuelle.
Cependant, mon entrée est jolie Big (environ 600 millions de lignes) et vérifiant si un élément appartient à une liste est une opération O (n) selon la documentation Python. P>
Mon code est quelque chose comme: P>
words_in_line = []
for word in line:
if word in my_list:
words_in_line.append(word)
4 Réponses :
Ceci utilise compréhension de la liste
words_in_line = [word for word in line if word in my_list]
Nope, ce n'est pas le genre de réponse que nous recherchons dans ce cas. Cela fait toujours 600m O (n) Opérations ( si Word dans ma_list ), cela n'affecte pas le problème réel.
Vous pourriez envisager un Trie ou un dawg ou une base de données. Plusieurs implémentations de Python sont de la même manière.
Voici quelques horaires relatifs pour que vous envisagez d'un ensemble VS Liste: impression: IE, correspondant à un ensemble de 10000 mots contre un ensemble de 250 000 mots est pour le test d'adhésion, une liste est O (n) et des ensembles et Les dict sont O (1) pour recherches. Conclusion: utilisez de meilleures structures de données pour 600 millions de lignes de texte!
Cela semble super. Mon premier code avait besoin d'environ 500 jours de calcul et environ 50 jours avec une nouvelle factorisation intelligente. Maintenant, il n'a besoin que de quelque chose comme 1 heure! Même si mon ensemble est de 200 000 longs, c'est impressionnant.
@ user1443418: Le facteur de retard de clé est l'opérateur Python dans contre une liste. Si vous mélangez ces deux structures de données et utilisez une liste pour l'accès aux données (c.-à-d. Utilisez pour Word dans test_list ) et utilisez le jeu pour le stockage des membres (c'est-à-dire si Word dans all_word_set ) C'est encore plus rapide. Les ensembles sont bien plus rapides pour les tests d'adhésion; Les listes sont plus rapides pour créer un accès de manière linéaire. Connaissez vos outils Luke.
C'est ce que j'ai utilisé après avoir vu votre réponse! Merci encore.
@Jiehong: N'hésitez pas à accepter la réponse si cela vous a aidé.
Il y a deux améliorations que vous pouvez faire ici.
dequeue code>, car sa performance ajoutée est supérieure à des listes. li>
- Si vous n'avez pas besoin de tous les matchs en mémoire, envisagez d'utiliser un générateur. Un générateur est utilisé pour itérer sur des valeurs assorties en fonction de la logique que vous spécifiez, mais elle stocke uniquement une partie de la liste résultante en mémoire à la fois. Cela peut offrir des performances améliorées si vous rencontrez des goulots d'étranglement d'E / S. LI>
ul> li>
ul>
ci-dessous est un exemple de mise en œuvre basé sur mes suggestions (opting pour un générateur, car je ne peux pas imaginer que vous avez besoin de toutes ces mots en mémoire à la fois). P>
a
b
c
b
Je ne suis pas clair sur la raison pour laquelle vous avez choisi une liste en premier lieu, mais voici quelques alternatives:
Utiliser un ensemble () est probablement une bonne idée. Ceci est très rapide, bien que non ordonné, mais parfois c'est exactement ce qui est nécessaire.
Si vous avez besoin de choses commandées et d'avoir des recherches arbitraires également, vous pouvez utiliser un arbre de quelque sorte: http://stromberg.dnsalias.org/~strombrg/python- Tree-and-Heap-Comparaison /
Si définissez le test d'adhésion avec un petit nombre de faux positifs ici ou il est acceptable, vous pouvez vérifier dans un filtre de floraison: http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/
Selon ce que vous faites, une trie pourrait aussi être très bonne.
Y a-t-il une raison pour laquelle vous ne pouvez pas travailler avec un ensemble de mots à la place? Il peut y avoir 600 millions de lignes, mais il y a beaucoup moins de mots anglais utilisés (même incluant la ponctuation de pointe et de la ponctuation de la fuite, si vous ne le nettoyez pas.) Les tests d'adhésion à un ensemble doivent être très rapides.
@DSM: o (1) en fait, en supposant 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 quelles repestes sont pour. Vous devez choisir vos types de données (en particulier les collections) pour convenir à ce que vous allez faire avec eux, car aucun type de données n'est bon pour tout.