Rechercher un article dans la liste avec 2MILLION articles - Python

Question

J'ai une liste de chaînes de 1,9-2 MILLION d'articles.

Le code suivant:

items = [...] 
item_in_list = items[-1] in items 

prend 0,1 secondes

Avec sqlite3 prend 0,7 secondes

---

Maintenant problème est je dois effectuer cette vérifier 1 million de fois et je voudrais compléter cela en quelques minutes plutôt que des jours.

Plus précisément, j'essaie de synchroniser le contenu d'un fichier CSV avec les valeurs calculées dans un DB.

---

Des idées? Serait vraiment génial :)

Answer 1

Placez les deux collections dans des ensembles de cellules. petit test de performance

:

import random 
from timeit import Timer 

def random_strings(size): 
    alpha = 'abcdefghijklmnopqrstuvwxyz' 
    min = 3 
    max = 8 
    strings = [] 
    for count in xrange(1, size): 
     current = '' 
     for x in random.sample(alpha, random.randint(min,max)): 
      current += x 
     strings.append(current) 
    return strings 

string_list_1 = random_strings(10000) 
string_list_2 = random_strings(10000) 

def string_test(): 
    common = filter(lambda x: x in string_list_2, string_list_1) 
    return common 

def set_test(): 
    string_set_1 = frozenset(string_list_1) 
    string_set_2 = frozenset(string_list_2) 
    common = string_set_1 & string_set_2 
    return common 

string_timer = Timer("__main__.string_test()", "import __main__") 
set_timer = Timer("__main__.set_test()", "import __main__") 
print string_timer.timeit(10) 
# 22.6108954005 
print set_timer.timeit(10) 
# 0.0226439453 

Comme vous pouvez le voir, est fixé de façon exponentielle plus rapide. Doit fonctionner mieux que le dictionnaire, aussi.

De note importante est que j'ai inclus le temps nécessaire pour faire les ensembles. Cette surcharge affectera également vos performances, mais à l'exception d'un ensemble beaucoup plus petit que l'autre, vous obtiendrez un gain important.

Answer 2

Pour une recherche comme celle-ci je voudrais aller avec une recherche binaire. Une des méthodes à jeun pour les longues listes SORTED. Si ce n'est pas trié, n'utilisez pas la recherche binaire.

Answer 3

Vous avez deux millions de chaînes que vous devez faire correspondre un million d'autres strings‽

Un couple de choses à essayer:

1. Utilisez un ensemble au lieu d'une liste pour les 2 millions d'articles.
2. Si cela ne l'accélère pas, essayez d'avoir les chaînes comme clés dans un dictionnaire.
3. Si cela ne vous aide pas non plus, procurez-vous une implémentation d'arbre binaire sympa et utilisez-la.

Mise à jour:

Comme mentionné dans les commentaires, les ensembles et dicts ne pas utiliser des arbres binaires, ils utilisent des tables de hachage. Cela devrait être plus rapide qu'une liste, et en fait probablement même plus rapide qu'une recherche binaire.

Answer 4

du haut de ma tête, avec si peu d'informations sur la raison pour laquelle vous faites cela quelques millions de fois:

1.) vous pouvez importer le csv dans une table et faire les contrôles dans SQL?2.) que diriez-vous de trier et d'indexer la liste pour un accès rapide?

acclamations, P