Оптимизация скорости внедрения LCS - PullRequest
Новая
       10

Оптимизация скорости внедрения LCS

0 голосов
/ 10 марта 2019

Я изучаю Python, выполняя упражнения, а затем «нажимая» в разных направлениях, например, оптимизируя время выполнения.Итак, я написал этот код для алгоритма LCS, то есть поиска самого длинного набора символов, присутствующего в двух разных строках одинакового размера, s1 и s2.

Я использовал известный алгоритм, но со строкой длиннее, скажем, 1000, код никогда не заканчивается, потому что он строит матрицу 1000 x 1000.

Итак, сначала я уменьшил количество строк в матрице lcs, потому что нам на самом деле просто нужна последняя строка + 1 строка, и удалил первую строку на каждой итерации.Увеличение скорости было огромным, но я все еще не мог достичь 5000.

Тогда у меня появилась идея повторно использовать первую строку вместо того, чтобы бросить ее, и снова я получил огромное улучшение и наконец смог добитьсяочень длинные строки: 26 с для 5000 знаков.

Но я хотел пойти «до конца», поэтому я попытался заменить max (a, b) на if a> b then ... else ...,и я набрал 20%.Для меня это довольно потрясающе.

Итак, если вы посмотрите на код, есть ли способ получить еще больше, чего я не вижу?

Как вы думаете, пишете ли вы библиотекув C только для этого упражнения можно было бы добиться определенных успехов?Я знаю, что это просто упражнение, но для меня это тоже хороший способ учиться.

Вот код: 

len_s = len(s1)
lcs = [[0] * (len_s + 1)] + [[0] * (len_s + 1)]  
m_1 = 0
for i in range(0,len_s):
    m_1 = 1 - m_1
    for j in range(0, len_s):  
        if s1[j] == s2[i]:
            lcs[m_1][j+1] = lcs[1 - m_1][j] + 1 
        #else: lcs[m_1][j+1] = max(lcs[m_1][j], lcs[m_0][j+1])  
        elif lcs[m_1][j] > lcs[1 - m_1][j+1]: 
            lcs[m_1][j+1] = lcs[m_1][j]
        else: 
            lcs[m_1][j+1] = lcs[1 - m_1][j+1]
print(lcs[m_1][len_s])
...