Сегодня я обманывал пару паролей программирования. Столкнувшись с задачей тестирования строки, чтобы увидеть, является ли она палиндром, я задумал несколько способов сделать это. Основы этих трех методов изображены ниже (наиболее аккуратный и тестовый код опущен).Производительность различных методов тестирования для палиндрома [Python]
def check_palin(victim, method):
if method is 1: # check progressively inner chars
x = 0
while x < (len(victim)/2): # len/2 is num of iter needed for guarantee
if victim[x+0] is victim[-(1+x)]: # on pass n, compare nth letter
# and nth to last letter
x += 1 # then increment the n counter
else:
return False
return True
elif method is 2: # check first and last chars repeatedly
tmp = []
for i in victim:
tmp.append(i) # convert string into list
while len(tmp) > 1: # if 1 or 0 char left, palin is guaranteed
if tmp[0] is tmp[-1]: # if the first and last characters are the same letter
tmp.pop(0) # remove them both
tmp.pop(-1)
else:
return False
return True
elif method is 3: # reverse string and compare to original
tmp = ""
for i in victim: # for every letter
tmp = i + tmp # cat it to the beginning, not append
return tmp == victim
else:
return -1
Метод 1 использует тот факт, что символы в строке могут быть проиндексированы как элементы списка. Мы можем представить этот метод таким образом: вы начинаете своими пальцами под первой и последней буквами слова; с каждой итерацией вы сначала проверяете, совпадают ли буквы над вашими пальцами; если они разные, слово не является палиндром; если они одинаковы, вы перемещаете каждое из ваших пальцев 1 букву в центр слова и повторяете.
Основная масса вычислений с помощью этого метода будет состоять в тестировании условий, разрезе индексов и сравнений. Существует также переменная счетчика, которая является постоянной частью расчета для нарезки индекса.
Способ 2 также использует индексацию символов в строке. Первый и последний символы сравниваются, затем отбрасываются, и эти шаги повторяются до тех пор, пока палиндром не будет гарантирован (или опровергнут).
Затраты будут аналогичны методу 1 с некоторыми отличиями: добавление преобразования из str -> list, выскакивающие элементы из списка и минус переменная счетчика.
Способ 3 отменяет данную строку, а затем сравнивает ее с оригиналом. Существуют различные способы изменения строки (list.__reversed__() и т. Д.), Но я показал только одну такую возможность: преобразование строки в список и последующее объединение каждого элемента этого списка в НАЧАЛО новой строки.
С помощью различных методов для реверсирования строки могут быть разные операции и, следовательно, затраты. Для моего выбранного метода здесь мы имеем стоимость нарезки каждого элемента из списка и объединения его с переменной str.
Мои вопросы:
Какой из этих методов были бы быстрее выполнения и почему? Кроме того, есть ли способ повысить эффективность этих методов? (По касательной, как вы проверяете скорость выполнения модулей в Python?)
Там очень простой способ узнать, какой метод является самым быстрым: ** измерить их скорость **. –
Oneliner для метода 3: ispalin = lambda s: s == s [:: - 1] –
Не используйте 'is' для сравнения ни с чем, кроме одиночных, таких как' True' или 'False' - это может вести себя странно. Реализация Python не требуется, чтобы каждая строка с одним символом была одиночной, поэтому сравнение может завершиться неудачей. Даже с CPython '2048 равно 2047 + 1' является False, так как' 'ab 'is' abc '[0: 2]', а другой интерпретатор может даже сделать '' a' is 'a'' False. – Tanriol