Сегодня я дурачился с парой загадок программирования.Столкнувшись с задачей тестирования строки, чтобы определить, является ли она палиндромом, я придумал несколько способов сделать это.Основы этих трех методов показаны ниже (большая часть кода для тестирования и тестирования не приводится).
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-> список, извлечение элементов из списка и минус переменная счетчика.
Метод 3 переворачивает заданную строку, а затем сравнивает ее с оригиналом. Существуют различные способы обратить строку (list.__reversed__() и т. Д.), Но я показал только одну такую возможность: преобразовать строку в список, а затем объединить каждый элемент этого списка в НАЧАЛОновая строка.
При использовании различных методов обращения строки могут быть разные операции и, соответственно, затраты.Для выбранного мной метода у нас есть стоимость вырезания каждого элемента из списка и конкатенации его с переменной str.
Мои вопросы:
Какой из этих методов будет самым быстрыми почему?Кроме того, есть ли способ повысить эффективность этих методов?(По касательной, как вы тестируете скорость выполнения модулей в Python?)