Я сосредоточился больше на оптимизации, чтобы получить больше от Python, чем на оптимизации алгоритма, потому что я не думаю, что здесь есть что-то большее в алгоритмическом улучшении. Вот некоторые оптимизации Python, которые я придумал.
(1). Поскольку вы, похоже, используете Python 2.x, измените все range () на xrange (). range () генерирует полный список чисел перед их повторением, в то время как xrange генерирует их по мере необходимости.
(2). Сделайте следующие замены для max и min:
start = max(0,i-halflen)
с
start = i - halflen if i > halflen else 0
и
end = min(i+halflen+1,len2)
с
end = i+halflen+1 if i+halflen+1 < len2 else len2
в первом цикле и аналогичные для второго цикла. Есть также еще одна min () ниже и max () в начале функции, так что сделайте то же самое с ними. Замена min () и max () действительно помогла сократить время. Это удобные функции, но более дорогостоящие, чем метод, которым я их заменил.
(3). Используйте common1 вместо len (ass1). Вы отследили длину ass1 в common1, поэтому давайте использовать ее, а не вызывать дорогостоящую функцию, чтобы найти ее снова.
(4). Замените следующий код:
minlen = min(len1,len2)
for same in xrange(minlen+1):
if (str1[:same] != str2[:same]):
break
same -= 1
с
for same in xrange(minlen):
if str1[same] != str2[same]:
break
Причина этого в основном в том, что str1 [: same] каждый раз создает новую строку в цикле, и вы будете проверять уже проверенные детали. Кроме того, нет необходимости проверять, если '' != '', а затем уменьшать same, если нам не нужно.
(5). Используйте psyco , своего рода компилятор точно в срок. После того, как вы скачали и установили его, просто добавьте строки
import psyco
psyco.full()
вверху файла, чтобы использовать его. Не используйте psyco, если вы не сделаете другие изменения, которые я упомянул. По какой-то причине, когда я запустил его на исходном коде, он на самом деле замедлил его.
Используя timeit, я обнаружил, что я получаю уменьшение времени примерно на 20% или около того с первыми 4 изменениями. Однако, когда я добавляю psyco вместе с этими изменениями, код примерно в 3–4 раза быстрее оригинального.
Если вы хотите больше скорости
Достаточное количество оставшегося времени находится в методе find () строки. Я решил попробовать заменить это своим. Для первого цикла я заменил
index = workstr2.find(str1[i],start,end)
с
index = -1
for j in xrange(start,end):
if workstr2[j] == str1[i]:
index = j
break
и аналогичная форма для второго цикла. Без psyco это замедляет код, а с psyco - значительно ускоряет. С этим последним изменением код примерно в 8-9 раз быстрее, чем оригинал.
Если это не достаточно быстро
Тогда вам, вероятно, следует заняться созданием модуля C.
Удачи!