La plupart Pythonic façon de recouper deux listes

Question

Problème:

J'ai une tâche des références croisées un peu compliqué, je dois effectuer entre une liste long (~ 600.000 entrées) et une liste short (~ 300.000 entrées). J'essaie de trouver les entrées similaires entre les deux listes, et chaque entrée unique est identifiée par trois entiers différents (appelez-les int1, int2, et int3). Sur la base des trois identifiants d'entiers dans une liste, je veux voir si ces trois mêmes nombres sont dans l'autre liste, et retourner lesquels ils sont.

Tentative:

D'abord, je compressé chaque tuple trois entier dans la liste long dans un tableau appelé a. De même, je zippé chaque tuple trois int dans la liste short dans un tableau appelé b:

a = [(int1,int2,int3),...] # 600,000 entries 
b = [(int1,int2,int3),...] # 300,000 entries 

J'itérés chaque entrée a pour voir si elle était en b. Si c'était, je les tuples correspondant apposé à un tableau en dehors de la boucle appelée c:

c= [] 
for i in range(0,len(a),1): 
    if a[i] in b: 
     c.append(a[i]) 

L'itération est (sans surprise) très lent. Je devine que Python doit vérifier b pour a[i] à chaque itération (~ 300 000 fois!), Et son itérer 600 000 fois. Il a pris plus d'une heure maintenant et n'a toujours pas fini, donc je sais que je devrais optimiser quelque chose.

Ma question est la suivante: quel est le moyen le plus rapide ou le plus rapide pour effectuer ce référencement croisé?

Answer 1

Vous pouvez utiliser des ensembles:

c = set(b).intersection(a) 

j'ai choisi de convertir b à un ensemble comme est la plus courte des deux listes. L'utilisation de intersection() ne nécessite pas que la liste a soit d'abord convertie en ensemble.

Vous pouvez aussi le faire:

c = set(a) & set(b) 

cependant, les deux listes nécessitent une conversion au type set premier.

De toute façon vous avez une opération O (n), voir time complexity.

Answer 2

solution Pandas:

a = [(1,2,3),(4,5,6),(4,5,8),(1,2,8) ] 
b = [(1,2,3),(0,3,7),(4,5,8)] 
df1 = pd.DataFrame(a) 
print (df1) 
    0 1 2 
0 1 2 3 
1 4 5 6 
2 4 5 8 
3 1 2 8 

df2 = pd.DataFrame(b) 
print (df2) 
    0 1 2 
0 1 2 3 
1 0 3 7 
2 4 5 8 

df = pd.merge(df1, df2) 
print (df) 
    0 1 2 
0 1 2 3 
1 4 5 8 

solution pure python avec set s:

c = list(set(b).intersection(set(a))) 
print (c) 
[(4, 5, 8), (1, 2, 3)] 

Answer 3

Une autre façon intéressante de le faire:

from itertools import compress 
list(compress(b, map(lambda x: x in a, b))) 

Et autre:

filter(lambda x: x in a, b)