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

Подсказка:
1) возьмите 2-3 задачи, реализованные ранее, сделайте замеры на разных входных данных
2) сделайте для каждой из задач оптимизацию (придумайте что можно оптимизировать)
и также выполните замеры на уже оптимизированных алгоритмах
3) опишите результаты - где, что эффективнее и почему.

ВНИМАНИЕ: ЗАДАНИЯ, В КОТОРЫХ БУДУТ ГОЛЫЕ ЦИФРЫ ЗАМЕРОВ (БЕЗ АНАЛИТИКИ)
БУДУТ ПРИНИМАТЬСЯ С ОЦЕНКОЙ УДОВЛЕТВОРИТЕЛЬНО
"""

import timeit
import sys

"""
Анализ скорости и сложности алгоритма вычисления факторила
"""

"""
Реализация №1.
"""

print(f'\nЗамер выполнения кода через цикл')
print('Метод <<timeit>>')

STR_CODE = '''
factorial = 1
n = 1000
while n > 1:
    factorial *= n
    n -= 1
'''
LAUNCH_LST = [1, 1000, 10000, 100000]  # массив запусков программы
for i in LAUNCH_LST:
    print(f'Число запусков кода = {i}.', end='')
    print(f'Время выполнения операции = {timeit.timeit(STR_CODE, number=i)}')

"""
Реализация №2.
"""

print(f'\nЗамер выполнения кода через рекурсию')
print('Метод <<timeit>>')


def factor(numb):
    '''Рекурсия'''
    if numb <= 1:
        return 1
    return numb * factor(numb - 1)


sys.setrecursionlimit(10000)
for i in LAUNCH_LST:
    print(f'Число запусков кода = {i}. Время выполнения операции = ', end=' ')
    print(
        timeit.timeit(
            'factor(1000)',
            setup='from __main__ import factor',
            number=i))

"""
Реализация №3.
"""

print(f'\nЗамер выполнения кода через рекурсию с мемоизацией')
print('Метод <<timeit>>')


def memorize(func):
    '''Мемоизация'''
    def gen(numb, memory={}):
        pos = memory.get(numb)
        if pos is None:
            pos = func(numb)
            memory[numb] = pos
        return pos
    return gen


@memorize
def factorial(numb):
    '''Рекурсия с декоратором'''
    if numb <= 1:
        return 1
    return numb * factorial(numb - 1)


sys.setrecursionlimit(10000)
for i in LAUNCH_LST:
    print(f'Число запусков кода = {i}. Время выполнения операции = ', end=' ')
    print(
        timeit.timeit(
            'factorial(1000)',
            setup='from __main__ import factorial',
            number=i))

"""
Реализация №4.
"""

print(f'\nЗамер выполнения кода с оптимизированным алгоритмом')
print('Метод <<timeit>>')


def factorial_opt(numb, memory=[1, 1]):  # 0!=1, 1!=1
    '''Оптимизированный алгоритм'''
    if numb < len(memory):
        return memory[numb]
    rec = numb * factorial_opt(numb - 1)
    memory.append(rec)
    return rec


for i in LAUNCH_LST:
    print(f'Число запусков кода = {i}. Время выполнения операции = ', end=' ')
    print(
        timeit.timeit(
            'factorial_opt(1000)',
            setup='from __main__ import factorial_opt',
            number=i))

"""
Рассмотрел 4 варианта кода:
- решение через цикл
- решение через рекурсию
- решение через рекурсию с мемоизацией
- решение с оптимизированным алгоритмом
Для всех вариантов рассчитывается факториал 1000.

При замере времени через рекурсию пришлось увеличивать глубину рекурсивных вызовов.
Из-за стека вызовов при вычислении времени через рекурсию время выполнения
увеличивается в среднем на 12..16% (при числе запусков программы = 100 000).
Увеличение времени рассчета обусловлено рекурсией: функция многократно вызывается
для одного и того же значения.

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

Эквивалентное время выполнения кода наблюдается и с оптимизированным алгоритмом.
+ список позволяет получать доступ к значениям по индексу (без хеширования ключа)
+ не тратится время на вызов декорирующей функции
"""

'''
Результаты вычислений

Замер выполнения кода через цикл
Метод <<timeit>>
Число запусков кода = 1.Время выполнения операции = 0.0009278350000000019
Число запусков кода = 1000.Время выполнения операции = 1.135257186
Число запусков кода = 10000.Время выполнения операции = 9.012288263
Число запусков кода = 100000.Время выполнения операции = 99.78227071399999

Замер выполнения кода через рекурсию
Метод <<timeit>>
Число запусков кода = 1. Время выполнения операции =  0.0017788290000027018
Число запусков кода = 1000. Время выполнения операции =  1.2301416450000033
Число запусков кода = 10000. Время выполнения операции =  11.441751659999994
Число запусков кода = 100000. Время выполнения операции =  123.455302239

Замер выполнения кода через рекурсию с мемоизацией
Метод <<timeit>>
Число запусков кода = 1. Время выполнения операции =  0.0018306039999913537
Число запусков кода = 1000. Время выполнения операции =  0.00040063700001269353
Число запусков кода = 10000. Время выполнения операции =  0.006635786000003918
Число запусков кода = 100000. Время выполнения операции =  0.05363607999998976

Замер выполнения кода с оптимизированным алгоритмом
Метод <<timeit>>
Число запусков кода = 1. Время выполнения операции =  0.0013416210000229967
Число запусков кода = 1000. Время выполнения операции =  0.00042241500000272936
Число запусков кода = 10000. Время выполнения операции =  0.004927632999994103
Число запусков кода = 100000. Время выполнения операции =  0.04304816299998038
'''
