Почему эти два кода имеют разное время выполнения?

Question

Я не понимаю, чем эти два кода отличаются, потому что они выполняют более или менее одинаковые операции, но чем больше я увеличиваю, тем больше разница во времени между этими двумя кодами. Большое О из двух кодов одинаково, потому что, в то время как l oop в первом коде служит для той же цели, что и для l oop во втором, а вложенное для l oop в первом сканировании все элементы как два вложенных в то время как л oop во втором. Если это так, как это может быть? (Эти два кода являются реализациями последовательности взгляда и произнесения: https://en.wikipedia.org/wiki/Look-and-say_sequence)

import time

a = time.time()

def look_and_say_sequence(first_element, n):

    while n != 1 :

        next_element , start , k = '' , first_element[0] , 0

        for x in first_element :
            if x != start :
                next_element , start , k = next_element + str(k) + start , x , 1
            else :
                k = k + 1

        first_element = next_element + str(k) + start
        n  = n - 1

    return first_element

look_and_say_sequence('1', 48)

b = time.time()

print(b-a)  # 10 SECONDS



#########################################################################################`

a = time.time()

def look_and_say_sequence(first, n):    
    result = first

    for _ in range(n-1):

        sequence = result
        result = ''
        index = 0

        while index < len(sequence):

            pending = sequence[index]
            count = 0

            while index < len(sequence) and pending == sequence[index]:
                count += 1
                index += 1

            result += "{}{}".format(count, pending)

    return result

look_and_say_sequence('1', 48)


b = time.time()

print(b-a) # 2 SECONDS

Спасибо за помощь!

Answer 1

Ваше замедление лежит в строке

next_element , start , k = next_element + str(k) + start , x , 1

, что приводит к большим потерям времени выполнения, когда next_element - очень длинная строка (что, безусловно, имеет место при увеличении n - next_element длиной более 500 000 символов для n = 48). Попробуйте запустить следующие два сценария:

import time

a = time.time()
s = ''
for i in range(99999):
  s = (s + '1') + '1' # comment this out
  # s += '1' + '1'  # and uncomment this to see the speed difference

b = time.time()
print(b-a)

вы заметите, что использование строки с использованием + = выполняется значительно быстрее. Python вычисляет слева направо, то есть (s + '1') должен вычислить новую строку перед добавлением + '1'. Это то, что добавляет так много замедления.

Между прочим, если вы измените эту проблемную строку на

next_element += str(k) + start
start = x
k = 1

, вы действительно увидите, что ваш главный алгоритм работает быстрее