Trouver le plus long algorithme de séquence commun en utilisant la table de hachage lent

Question

J'ai conçu un algorithme pour trouver la plus longue séquence commune. ce sont des étapes:

Commence par i = 0

1. Piques la première lettre du premier début de chaîne de ième lettre.
2. Aller à la deuxième chaîne à la recherche de cette lettre cueillies.
3. Si non trouvé retour à la première chaîne et reprend la lettre suivante et répétez 1 à 3 jusqu'à ce qu'il trouve une lettre qui se trouve dans la deuxième chaîne.
4. Maintenant que l'on trouve une lettre commune dans la deuxième chaîne, ajoute que pour $common_subsequence.
5. Magasin sa position dans $index.
6. Médiator lettre suivante de la première chaîne et à faire étape 2, mais cette fois-ci commence à partir $index.
7. Répéter 3 à 6 jusqu'à la fin de la chaîne atteint une chaîne ou 2.
8. Si $common_subsequence de longueur est supérieure à la longueur de la séquence commune jusqu'à ajouter que le changement lcs au $common_subsequence.
9. Ajoutez 1 à i et répéter 1 à 9, tandis que i est moins que la longueur de la première chaîne.

Ceci est un exemple:

X=A, B, C, B, D, A, B‬‬  
‫‪Y=B, D, C, A, B, A‬‬ 

1. d'abord choisir A.
2. Rechercher A dans Y.
3. Maintenant que l'on trouve A ajouter que la $common_subsequence.
4. Ensuite, choisissez B de X.
5. Rechercher B dans Y mais cette fois commencer la recherche A.
6. Maintenant choisir C. Il est pas là dans la chaîne 2, alors choisissez la lettre suivante X qui est B.
   ...
   ...
   ...

La complexité de cet algorithme est thêta (n * m).

Je mis en œuvre sur les deux méthodes. La seconde utilise une table de hachage, mais après la mise en œuvre, je trouve qu'il est beaucoup plus lent par rapport au premier algorithme. Je ne peux pas undrestand pourquoi.

Voici mon implémentation:

Premier algorithme:

import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

seconde en utilisant la table de hachage:

import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

Answer 1

Une optimisation consiste à remplacer l'accès à reached_index[item] par une variable locale qui est initialisé à partir de la table de hachage au début de la boucle de for item, et stocké à la table de hachage à la fin de la boucle.

Une autre optimisation qui permettra d'accélérer les choses est de remplacer les tables de hachage avec des tableaux de taille 256.