Какие новые библиотеки изучаешь

Ах ты ж ёпта, ну и история у нас тут, про эти ваши... как их... охуительные алгоритмы! Слушай, вот представь: сидишь ты, такой, пишешь код, всё вроде красиво, а потом — бац! — и вылезает какая-нибудь дичь, от которой мозг вскипает, как чайник у бабки в деревне. Прям как в том анекдоте про программиста и чайник, только чайник — это твой собственный код, который ты только что написал и уже ненавидишь.

Вот, например, берём мы эту классическую задачку про Фибоначчи. Все её знают, все её решали, и все, блядь, делают одну и ту же ошибку — наивную рекурсию. Выглядит она, конечно, изящно, прямо как балерина в «Лебедином озере», но по производительности — это та же балерина, только пьяная и в валенках.

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Смотри, в чём прикол: чтобы посчитать fib(5), этой функции надо вызвать себя аж 15 раз! А для fib(30) — уже больше 2.5 миллионов вызовов! Это ж пиздец какой-то, а не алгоритм. Компьютер начнёт пыхтеть, как паровоз, а ты будешь сидеть и думать: «Ну че, ёпта, я же всё правильно написал, почему оно так долго?»

А всё потому, что функция тупо пересчитывает одни и те же значения по сто хуев раз. fib(3) считается и там, и сям, и ещё разок для прикола. Эффективность — ниже плинтуса, прямо как у мартышки с гранатой.

И вот тут-то появляется наш спаситель — динамическое программирование, или, как я это называю, «запоминание, чтобы не выглядеть идиотом». Суть проще пареной репы: раз уж мы посчитали fib(3) один раз, давайте, блядь, сохраним результат и больше не будем мозг себе ебать.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Видишь? Добавили простой словарик memo. Прежде чем считать что-то с нуля, проверяем — а не считали ли мы это уже? Если считали — сразу отдаём результат, без всяких там танцев с бубном. Сложность с экспоненциальной превращается в линейную, O(n). Для fib(30) теперь нужно не миллионы вызовов, а всего лишь 59. Чувствуешь разницу? Как будто с говённого Запорожца пересел на нормальную тачку.

А можно вообще пойти дальше и сделать итеративное решение, без рекурсии. Типа «забудь про рекурсию, давай по-простому, как мужики».

def fib_iterative(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(1, n):
        a, b = b, a + b
    return b

Вот это уже вообще красота! Никаких лишних вызовов, память почти не жрёт, работает быстрее ветра. Просто берём и по порядку вычисляем числа, от первого до n-ного. Всё, ебушки-воробушки, задача решена эффективно и без лишней суеты.

Так что мораль, блядь, какая? Не всегда самое красивое и «математическое» решение — самое умное. Иногда надо просто подумать головой, а не жопу рвать рекурсией на ровном месте. Динамическое программирование — это как та самая заначка в тумбочке: когда припёрло, а у тебя уже всё готово. Главное — вовремя вспомнить, куда ты её, сука, спрятал.