Как мне оптимизировать этот код на Python?

#python #optimization

#python #оптимизация

Вопрос:

Я решаю задачу по программированию для развлечения и для работы над своими навыками — некоторые из вас, возможно, помнят появление Code challenge в декабре прошлого года, я работаю над этим. У меня есть этот код как решение одной из проблем, которое работает, но бесполезно медленно.

 inp = "1113122113"

def iterate(num):
    pos = 0
    new = ""
    while pos < len(num):
        counter = 0
        d = num[pos]
        for i in range(pos, len(num)):
            if num[i] == d:
                counter  = 1
            else:
                break
        new =str(counter)
        new =str(d)
        pos  = counter
    print len(new)
    return new

for i in range (50):
    inp = iterate(inp)

После 35-й итерации или около того доходит до того, что на каждую итерацию уходит несколько минут. Цель состоит в том, чтобы сгенерировать последовательность «посмотри и скажи» — так что 1 переходит в 11, затем 21, 1211, 111221, 3112211 и так далее. Мне нужно найти длину строки после 50-й итерации, но после 40 итераций она составляет 360154 символа, и мой код просто недостаточно оптимизирован для обработки строк такой длины за разумное время. Кто-нибудь может дать мне несколько советов?

1. Вопросы об улучшении рабочего кода лучше подходят для проверки кода .

2. «некоторые из вас, возможно, помнят появление Code challenge в декабре прошлого года» — Извините, но я не знаю, не могли бы вы немного рассказать о том, в чем заключалась проблема? И, кстати, этот вопрос лучше подходит для проверки кода

3. Это не особенно важно, это сайт, который появился в прошлом году. Он все еще существует, поэтому я решил поработать над ним еще немного. Вы можете найти его по адресу adventofcode.com , это задача 10-го дня.

4. И спасибо за совет, я пойду спрошу о проверке кода

5. Мне не нравится этот вызов большого диапазона () в середине. Обычно я использую range для небольших циклов for , но у меня возникли проблемы с созданием действительно большого списка из range, когда мне это было не нужно.

Ответ №1:

Использование itertools.groupby сделает это очень быстро.

 from itertools import groupby
def next_say(s):
    return ''.join(str(sum(1 for _ in g)) k for k, g in groupby(s))

def iterate(num):
    """Generator that yields the first num iterations"""
    val = '1'
    for i in range(num):
        val = next_say(val)
        yield val

https://docs.python.org/2/library/itertools.html#itertools.groupby

1. вместо того, чтобы тратить место на ненужный список, вы можете получить тот же результат с sum( 1 for _ in g ) помощью, также вам нужно преобразовать это в строку…

2. @Copperfield Хорошие моменты, мне было интересно, как обойти этот list вызов.