Как я могу оптимизировать этот код Python для более быстрой работы? - PullRequest
1 голос
/ 05 января 2012

Я решаю проблему, которая имеет некоторые ограничения по времени и памяти, и, к сожалению, это не соответствует ограничениям по времени.

Я довольно новичок в Python, поэтому любые отзывы о более быстрых / лучших методах приветствуются.

Вот проблема, которую пытается решить программа:

Определите сходство двух строк A & B как длину самого длинного общего префикса, который они разделяют.т.е. сходство AAAB и AABCAAAB равно 2.

Программа должна вывести сумму сходств входной строки со всеми ее суффиксами.то есть для AAAB, он должен вывести

сходство (AAAB, AAAB) + сходство (AAAB, AAB) + сходство (AAAB, AB) + сходство (AAAB, B) = 4 + 2 + 1 + 0 = 7

Первая строка ввода - это количество строк, которые нужно ввести, и каждая последующая строка содержит строку для обработки.

from array import array

n = int(sys.stdin.readline()) 
A = [0] * n #List of answers

for i in range(1,n+1):
  string = sys.stdin.readline().strip()    
  A[i-1] = len(string)
  for j in range(1, len(string)):
    substr = string[j:len(string)]
    sum = 0
    for k in range(0, len(substr)):
        if substr[k] != string[k]:
            break
        else:
            sum += 1
    A[i-1] += sum

for i,d in enumerate(A):
  print d

Ответы [ 3 ]

2 голосов
/ 05 января 2012

С точки зрения производительности, предпочитайте xrange как более быстрый для итерации в python2.X Но лучший совет, который я могу дать, это использовать timeit для измерения изменений и улучшений при настройке вашего алгоритма.

Погуглил здесь еще одну реализацию: Решение Longest Common substring , но библиотека python-Levenshtein , вероятно, является лучшим выбором, поскольку она имеет расширение C для скорости ...

1 голос
/ 05 января 2012

Вы можете попробовать альтернативную реализацию

sum(len(os.path.commonprefix([instr,instr[i:]])) for i in xrange(0,len(instr)))

где instr = Ваша указанная строка

1 голос
/ 05 января 2012

Первый шаг - уменьшить объем выполняемой вами индексации:

import sys

n = int(sys.stdin.readline())

for i in range(n):
    string = sys.stdin.readline().strip()
    sum = 0
    for offset in range(len(string)):
        suffix = string[offset:]
        for c1, c2 in zip(string, suffix):
            if c1 != c2:
                break
            sum += 1
    print sum

Впрочем, это все равно O (N ^ 2).Для O (N) используйте дерево или массив суффиксов, например http://code.google.com/p/pysuffix/

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...