Как я могу оптимизировать этот код Python, чтобы работать быстрее?

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

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

Это проблема программа пытается решить:

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

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

подобия (AAAB, AAAB) + подобия (AAAB, ААВ) + подобия (AAAB, АВ) + подобия (AAAB, В) = 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

источник

2012-01-05 Ankit Soni

Если вы используете Python 2.x , вы можете начать с изменения всех этих 'range' до' xrange'. Есть ли веская причина, по которой вам нужно читать по очереди, а не в одном большом куске? – wim

Кстати, реальная проблема - избавиться от этого тройного вложенного цикла. Я уверен, что есть какая-то умная логика, которую вы можете переопределить! – wim

Вы должны искать более быстрый алгоритм. –

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

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

источник

2012-01-05 09:54:13 Ross

Теперь, когда я думаю об этом, основной алгоритм может быть значительно улучшен, поэтому я буду работать над этим. Небольшие исправления ('xrange', чтение ввода по строкам) были недостаточными. Это не совсем самая длинная проблема с общей подстрокой, но она близка, и я собираюсь применить аналогичную идею, поэтому я приму этот ответ. –

Первый шаг заключается в снижении количества индексации вы делаете :

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/

источник

2012-01-05 10:18:10

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

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

где инстр = Ваш струну

источник

2012-01-05 10:29:20 Abhijit

Как я могу оптимизировать этот код Python, чтобы работать быстрее?

ответ

Смежные вопросы