Как можно оптимизировать код?

Question

[Dazai]

Приветствую. Я только начал изучение python и сейчас решаю задачи из проекта Эйлера.
Задача 14 звучит так:
Следующая повторяющаяся последовательность определена для множества натуральных чисел:

n → n/2 (n - четное)
n → 3n + 1 (n - нечетное)

Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются на 1.

Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?

Примечание: Следующие за первым элементы последовательности могут быть больше миллиона.
Решил я ее таким способом:

import math
import sys
sys.setrecursionlimit(100000)
def check(n): # проверка четное число или нет
    if n % 2 == 0:
        return True
    else:
        return False

def ifeven(n,d = 0): # если четное
    if n == 1:
        return d + 1
    if check(n) == True:
        rez = math.ceil(n/2)
        d+=1
        return ifeven(rez,d)
    else:
        return ifnoteven(n,d)
    
def ifnoteven(n,d = 0): # если не четное
    if n == 1:
        return d+1
    if check(n) == False:
        rez = (3*n) + 1
        d+=1
        return ifnoteven(rez,d)
    else:
        return ifeven(n,d)
    
def main(n,d = 0): # функция чтобы в цикле не определять четное число или нет
    if check(n) == True:
        return ifeven(n,d)
    else:
        return ifnoteven(n,d)

number = 0
product = 0
i = 1

while i < 10**6:
    if i % 10 == 0:
        i+=2
        continue
    print(i)
    c = main(i)
    if c > product:
        product = c
        number = i
    i+=2
else:
    print('Ответ:', number)

Хотел бы спросить, насколько этот код плох и как его оптимизировать, потому что ответ ищется очень долго
P.S: Извиняюсь за такое малое количество комментариев

Answer 1

[Влад Григорьев]

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

import math
from collections import defaultdict

all_els = defaultdict(int)
all_els[1] = 1
max_length = 0


def new_element(el: int):
    if not el % 2:
        return math.ceil(el / 2)
    return (3 * el) + 1


def find_length(el: int):
    first_el = el
    length = 1
    while el != 1:
        el = new_element(el)
        if el in all_els:
            length += all_els[el]
            break
        length += 1

    all_els[first_el] = length
    return length


for i in range(1, 10 ** 6):
    if max_length < (result := find_length(i)):
        max_length = result

print(max_length)

Comments

[longclaps]

return math.ceil(el / 2)

Преобразование типов (а тут оно происходит дважды) - весьма затратная операция. "Оптимизатор", незнакомый с целочисленным делением, иди доучивайся.

[Влад Григорьев]

longclaps, но таки ок с // мы выигрываем еще ~230 миллисекунд, с 1.3830578327178955 до 1.1459438800811768, что с первоначальными 24 секундами, незначительно.
И по факту это не предел, можно еще оптимизировать и оптимизировать. Это лишь один из вариантов оптимизации, в котором я не претендовал на эталонность