0
while len(s2) >= 34:

    code1 = s2[:17]
    code2 = s2[17:34]
    if code2 in symbolsDictDecode:
        lastCode = generator(lastCode)
        symbolsDictDecode[lastCode] = symbolsDictDecode[code1] + symbolsDictDecode[code2][0]
    else:
        lastCode = generator(lastCode)
        symbolsDictDecode[lastCode] = symbolsDictDecode[code1] * 2
    string += symbolsDictDecode[code1]
    s2 = s2[17:]

Данный код для строки s2 длинной 3465528 символов выполняется порядка 30 секунд, а код:

while len(s2) >= i + 34:
    code1 = s2[i:17+i]
    code2 = s2[17+i:34+i]
    if code2 in symbolsDictDecode:
        lastCode = next(gen)
        symbolsDictDecode[lastCode] = symbolsDictDecode[code1] + symbolsDictDecode[code2][0]
    else:
        lastCode = next(gen)
        symbolsDictDecode[lastCode] = symbolsDictDecode[code1] * 2
    string += symbolsDictDecode[code1]
    i += 17

Выполняется меньше 1 секунды. Интересно узнать каким образом происходит создание новой строки в Python 3.x

2
  • 1
    Если вместо сложения строк, результат добавить в список, а после сделать join, то еще быстрее будет. Сравните: x = '' for _ in range(1000000): x += '1' и x = ''.join(['1' for _ in range(1000000)])
    – gil9red
    19 мар 2018 в 23:20
  • связанный вопрос: Непонятное замедление конкатенации в цикле
    – jfs
    20 мар 2018 в 6:16

1 ответ 1

1

Можно разницу продемонстрировать на более простом примере:

s = "a" * 1000_000
step = 10
for i in range(0, len(s), step):
    chunk = s[i:i+step]  # O(1)

это линейный алгоритм O(n) (количество действий пропорционально len(s)).

Сравните с:

s = "a" * 1000_000
step = 10
for i in range(0, len(s), step):
    chunk = s[:step]
    s = s[step:]  # O(n)

что является квадратичным алгоритмом O(n*n).

Результаты сравнения

name                  time ratio comment
slices_linear    18.1 usec  1.00 10**3
slices_quadratic 34.9 usec  1.93 10**3
name                  time ratio comment
slices_linear     181 usec  1.00 10**4
slices_quadratic  576 usec  3.19 10**4
name                  time ratio comment
slices_linear    1.79 msec  1.00 10**5
slices_quadratic 37.2 msec 20.81 10**5
name                  time  ratio comment
slices_linear    18.2 msec   1.00 10**6
slices_quadratic 4.92  sec 270.50 10**6

Видно, что при увеличении размера строки в 10 раз, время исполнения линейного алгоритма возрастает в 10 раз. Квадратичный алгоритм ведёт себя тем хуже по сравнению с линейным чем размер ввода больше.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.