Comment faire correspondre efficacement des chaînes entre deux grandes listes avec python? (510.000.000 comparaisons)

def two_list (a, b): pour élément dans a: pour num dans b: si élément == num: print (élément)

print (liste_deux (a, b))

Vous pouvez également le faire avec les pandas.

adf = (
    pandas.DataFrame(A,columns=['text'])
    .assign(strlen=lambda x: x['text'].str.len())
) #create a df from the first array

bdf = (
    pandas.DataFrame(B,columns=['text'])
    .assign(strlen=lambda x: x['text'].str.len())
    .sort_values('strlen')
) #create a df from the second array

resultdf = pandas.DataFrame()

for i,row in bdf.itterrows():
   if len(row['text']) > adf.text.max():
       break
   resultdf = resultdf.append(
           adf[lambda x: x['text'].str.contains(row['text'])],ignore_index=True)

resultdf

Vous pouvez essayer ceci:

d={}
for i in range(1,101):
    d[i]=[]
    for x in A:
        for y in range(min(101, len(x))-i+1):
            d[i].append([x[y:y+i]), A])

result=[]
for item in B:
    s=d[len(item)]
    for k in s:
        if item==s[0]:
            result.append(s[1])

Explication: Nous créons un dict avec les clés 1-100 qui représentent les longueurs possibles des éléments dans B. Nous bouclons dans la liste A. Pour chaque élément de A, nous bouclons de 1 à max (minimumn à partir de la longueur de l'élément ou 100) et sauvegardons toutes les parties de A à la clé associée en d. Lorsque cela se termine, nous n'avons qu'à boucler la liste B une fois, et comparer l'élément (de B) avec les valeurs dans la clé respective de d. Par exemple, si la longueur de l'élément est 20, nous ne vérifierons que d [20]. Si l'élément est unique avec un élément, nous sauvegardons l'élément A respectif

Première réponse: si vous ne devez le faire qu'une seule fois, forcez-le simplement. Les opérations de sous-chaînes 570M représentent beaucoup, oui, je suppose que cela prendra environ une heure, mais c'est moins de temps qu'il n'en faudra pour comprendre, écrire et déboguer une solution plus rapide.

Deuxième réponse: essayez de mettre les chaînes de B dans un trie . En théorie, cela le rendra plus rapide, mais en pratique, ce ne sera probablement pas le cas à moins que vous ne trouviez une bibliothèque de trie python implémentée en C. Sinon, parcourir un trie (ou vraiment toute autre structure de données de recherche de chaîne) en python va être lent.

Le problème auquel vous êtes confronté est que si vous avez une seule chaîne de A et une seule chaîne de B, alors b in a sera relativement rapide car sous le capot, la correspondance de sous-chaîne fonctionnera en C.Mais si vous codez un plus théoriquement solution efficace en python, même si le temps d'exécution du "gros O" est plus rapide, le temps d'exécution réel sera probablement plus lent car le python interprété est beaucoup plus lent que C.

Voici deux solutions (où l1 est la première liste et l2 est la deuxième liste):

Solution A, recherche binaire (complexité temporelle O (nlogn)):

B_d = {key: [] for key in l2}
results = []
for l in l1:
    if l in B_d:
        results.append(l)

Table de hachage de la deuxième solution (complexité temporelle O (n)):

import bisect
def method_bisect(x, b):
    index = bisect.bisect_left(b, x)
    if x == b[index]:
        return x
    return None


results = []
l2.sort()
for l in l1:
    result = method_bisect(l, l2)
    if result:
        results.append(result)

En fin de compte, j'ai choisi la solution suggérée par @busfighter dans les commentaires:

"Vous pouvez trier les deux listes par longueur de chaînes et donc rompre votre boucle interne si la longueur de l'élément est supérieure à celle de l'élément . Cela ne rendra pas la complexité plus faible mais cela diminuera le nombre d'opérations."

Speedwise il dit:

"le tri a une complexité O (nlogn) (qui est inférieure à O (nm) si n et m sont d'un ordre) et trouver la longueur de la chaîne est moins chère (O (1)) que de vérifier si la chaîne est une sous-chaîne d'une autre ( O (n * m) où n et m sont des longueurs de chaînes)) "