"""
Задание 3.

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

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


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

from random import sample, choice
import string


# Функция по формированию словаря заданной длинны. Сделал, чтобы позамерять время на разной длинне словаря, наглядно.
# Разбор сложности генератора не проводился, так как он не относится к самой задаче, а просто вспомогательный.
def gen_dict(x):
    return {k: v for k in [''.join(choice(string.ascii_lowercase) for _ in range(5)) for _ in range(x)]
            for v in sample(range(1000, 99999), x)}


gen_d = gen_dict(999)


# Решение 1 - его сложность O(NlogN)
# Наиболее эффективное из приведенных
def top_income(dictionary: dict):
    a = list(dictionary.items())  # O(N)
    a.sort(key=lambda i: i[1], reverse=True)  # O(NlogN)
    for i in range(3):  # O(1) - для фиксированного цикла чилал единица
        print(f'Название компании: {a[i][0]} | Выручка компании: {a[i][1]}')  # O(1)


print(gen_d)
top_income(gen_d)


# Решение 2 - его сложность O(N^2). Специально сделал квадратическое.
# Данное решение менее эффективное, чем первое, так как сложность квадратическая и очень высокие затраты на выполнение
# Отдельный замер времени показывает многократный рост времени выполнения
def top_income_sec(dictionary: dict):
    for _ in range(3):  # O(1) - для фиксированного цикла чилал единица
        for k, v in dictionary.items():  # O(N)
            if v == max(dictionary.values()):  # O(N)
                print(f'Название компании: {k} | Выручка компании: {v}')  # O(1)
                dictionary.pop(k)  # O(1)
                break  # O(1)


print(gen_d)
top_income_sec(gen_d.copy())


# Решение 3 - его сложность O(N^3). Специально сделал кубическое и излишне сложное.
# Данное решение менее эффективное, чем первые, так как сложность кубическая и очень высокие затраты на выполнение
# Отдельный замер времени показывает катастрофический рост времени выполнения. А на больших словарях зависает
def top_income_th(dictionary: dict):
    for _ in range(len(dictionary) - 3):  # O(N)
        for k, v in dictionary.items():  # O(N)
            if v == min(dictionary.values()):  # O(N)
                dictionary.pop(k)  # O(1)
                break  # O(1)
    for k, v in dictionary.items():  # O(1) так как я знаю, что словарь тут всегда будет фиксированный из 3 элементов
        print(f'Название компании: {k} | Выручка компании: {v}')  # O(1)


print(gen_d)
top_income_th(gen_d.copy())
