Палиндромы и нарезка струны. Производительность ⇐ Python

[Anonymous]

Есть много способов проверить, является ли строка палиндром. Многие из них перечислены здесь
Этот вопрос не о «Как», а скорее о производительности.
Я утверждал, что is_palindrome должен быть в два раза быстрее, чем is_palindrome0 , потому что он делает len/2 итерации в худшем случае. is_palindrome занимает более 30 секунд, чтобы проверить все строки, в то время как is_palindrome0 выполняет задание менее чем за половину секунды!def is_palindrome(s):
for i in range(len(s) // 2):
if s != s[len(s)-i-1]:
return 0
return 1

def is_palindrome0(s):
if s == s[::-1]:
return 1
else:
return 0

N = 500
L = 99999

sss = '101' * L

import time

start = time.time()
print(sum([1 for i in range(N) if is_palindrome0(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

start = time.time()
print(sum([1 for i in range(N) if is_palindrome(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

output
168
0.40
168
34.20
< /code>
Есть идеи, почему нарезка строки такая сумасшедшая? Как дальше отладить?def is_palindrome(s):
l = len(s)
for i in range(l // 2):
if s != s[l-i-1]:
return 0
return 1

def is_palindrome0(s):
if s == s[::-1]:
return 1
else:
return 0

N = 500
L = 99999

sss = '101' * L

import time

start = time.time()
print(sum([1 for i in range(N) if is_palindrome0(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')

start = time.time()
print(sum([1 for i in range(N) if is_palindrome(sss+sss[i:])]))
end = time.time()
print(f'{(end - start):.2f}')
< /code>
Немного быстрее, но все же примерно в 50 раз медленнее. < /p>
168
0.41
168
25.11


Подробнее здесь: https://stackoverflow.com/questions/796 ... erformance