Как оптимизировать код Python лестничной задачи для работы с большими значениями?

Question

Мне пришлось создать программу для задачи с лестницей, где мне нужно было проектировать лестницу с n количеством кирпичей.Сложность в том, что количество кирпичей на каждом шаге должно быть уникальным и меньше, чем на предыдущем шаге.например, используя 6 кирпичей, я могу сделать лестницу с высотой шага (5,1) , (4,2) and (3,2,1), но не (3,3) or (1,2,3) or (2,4) или любой другой перестановкой.

Я разработал код, но проблема в том, что он работает нормально до n почти 100 или 120, но останавливается, если входные значения больше этих значений.Я новичок в программировании на Python и изучаю концепции на ходу.

Я пробовал запоминать, но безрезультатно.Мне нужно знать, есть ли что-то еще, что я могу сделать, чтобы мой код был более оптимизирован для работы с n как 200-250?

    import cProfile

    def solution(n):

        memory = {0: [], 1: [1], 2: [2]}

        def rec(max_val, i):

            t = []
            r = []

            for j in range(1,i):

                y = i - j

                if y < max_val:

                    if y > j:
                        t = [y, j]
                        r.append(t)

                        if n / 2 >= j >= 3 and j in memory:
                            mem = memory[j]
                            [r.append([y, item]) for item in mem]

                    else:
                        if y >= 3 and n / 2 >= j >= 3 and j in memory:
                            mem = memory[j]
                            for item in mem:
                                if y > item[0]:
                                    r.append([y, item])
                        else:
                            v = rec(y, j)
                            if v:
                                for item in v:
                                    t = [y, item]
                                    r.append(t)

            if r:
                if i in memory:
                    if len(memory[i]) < len(r):
                        memory[i] = r
                else:
                    memory[i] = r
            return r

        def main_func(n):

            stair = []
            max_val = 201
            total = 0
            for i in range (1,n):

                x = n - i

                if x > i:
                    s = [x, i]
                    total += 1

                    if i >= 3:
                        u = rec(max_val, i)
                        total += len(u)

                elif x == i and i >= 3:
                        u = rec(max_val, i)
                        total += len(u)

                elif x < i and i >= 3:
                        u = rec(x, i)
                        total += len(u)

            return total

        stairs = main_func(n)
        return (stairs)

    print(solution(100))

Answer 1

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

Например, при 6 кирпичах первый вызов прошел бы через базовые размеры n = 5,4,3,2 и сделал бы рекурсивные вызовы, чтобы узнать, сколько комбинаций возможно для уровней следующего шага, используя оставшиеся кирпичи и с максимальная база n-1. Сумма отсчетов следующих уровней будет составлять общее количество возможных схем лестниц.

В верхней части лестницы вам нужно как минимум 3 кубика, чтобы добавить более одного уровня, чтобы вы могли остановить рекурсию со счетом 1, когда осталось менее 3 кубиков. Это свернет рекурсивные вызовы для формирования больших итогов и даст правильный ответ после завершения исходного вызова.

Чтобы оптимизировать этот процесс, вы можете использовать запоминание, а также замыкать вычисления, используя базовый размер, указанный в каждой рекурсии.

Для данной базы наибольшее количество кирпичей, которые можно использовать, будет суммой чисел от 1 до этой базы. Это можно рассчитать по формуле Гаусса: base*(base+1)/2. Если у вас больше кирпичей, чем максимальное количество кирпичей для базы, то вы можете остановить рекурсию и вернуть нулевой счет (так как у вас слишком много оставшихся кирпичей и вы не сможете разместить их все по базе предыдущего уровня)

Еще один способ оптимизировать вычисления - это циклически проходить через базовые размеры в порядке убывания Это позволит вам остановить цикл, как только вы получите счетчик нуля для следующих уровней, что означает, что для этого базового размера (или любого меньшего базового размера) осталось слишком много кубиков

Вот пример (использование lru_cache для запоминания):

from functools import lru_cache
@lru_cache(None)
def stairCount(N,base=None):
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    count = 0
    while True:
        nextLevels = stairCount(N-base,base-1)
        if nextLevels == 0: break
        count += nextLevels
        base   = base - 1
    return count

С этими оптимизациями функция будет реагировать менее чем за секунду до 600 блоков (в зависимости от скорости вашего компьютера).

При использовании списка Python вы могли бы написать эту функцию более кратко (хотя она потеряла бы убывающую оптимизацию базового порядка ≈ 10%):

@lru_cache(None)
def stairCount(N,base=None):
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    return sum(stairCount(N-b,b-1) for b in range(2,base+1))

РЕДАКТИРОВАТЬ Вот версия с «ручным» запоминанием (т.е. без использования functools):

def stairCount(N,base=None,memo=dict()):
    memoKey = (N,base)
    if memoKey in memo: return memo[memoKey]
    base = min(base or N-1,N)
    if N > base*(base+1)//2: return 0
    if N < 3: return 1
    count = 0
    while True:
        nextLevels = stairCount(N-base,base-1,memo)
        if nextLevels == 0: break
        count += nextLevels
        base   = base - 1
    memo[memoKey] = count
    return count