Algorithms

Алгоритми⚑

Рекурсія [💡15/100]⚑

Рекурсія — це метод програмування, при якому функція викликає саму себе для розв’язання задачі. Зазвичай рекурсія використовується для задач, які можуть бути розділені на менші підзадачі аналогічної структури. Логіка рекурсивної функції, як правило, має дві гілки. Довга гілка викликає цю ж функцію з іншими параметрами, щоб накопичити результат. Коротка гілка встановлює критерій виходу з рекурсії.

Рекурсія, у деяких випадках, спрощує код та робить його декларативним. Рекурсія сприяє функціональному мисленню та уникненню побічних ефектів.

Рекурсія має базовий та рекурсивний випадок. Якщо рекурсивний алгоритм не матиме базового випадку, він буде виконуватися нескінченно, оскільки не буде умови, за якої потрібно повернути управління.

Як працює рекурсія

Кожен рекурсивний виклик створює нову копію функції в стеку викликів.
Рекурсія має базовий випадок (умову завершення), який запобігає нескінченним викликам.

def factorial(n):
    if n == 0:  # Base case: if n is 0, return 1
        return 1
    return n * factorial(n - 1)  # Recursive case: multiply n by factorial of (n-1)

print(factorial(5))  # Output: 120

Недоліком рекурсії є те, що вона може спричиняти надмірне споживання пам'яті. Кожен рекурсивний виклик додає новий запис до стеку викликів, що може призвести до переповнення стеку (RecursionError у Python). Також відстеження рекурсивного коду може бути складнішим через велику кількість викликів, особливо для глибоких рекурсій.

CPython-специфіка: ліміт глибини

CPython має software-ліміт глибини рекурсії за замовчуванням sys.getrecursionlimit() == 1000. При перевищенні - RecursionError: maximum recursion depth exceeded. Ліміт - захист від нескінченної рекурсії, який зупиняє Python до того, як впаде C-стек процесу (зазвичай 8 MB на Linux/macOS).

import sys

sys.getrecursionlimit()       # 1000 (default)
sys.setrecursionlimit(10000)  # Raise the cap

Підняття ліміту сильно вище 1000 без розуміння наслідків веде до segmentation fault замість контрольованого RecursionError - C-стек переповнюється і процес падає без можливості перехопити сигнал:

import sys
sys.setrecursionlimit(1_000_000)
def f(n): f(n + 1)
f(0)  # Eventually: SIGSEGV - not catchable in Python

Чому CPython не оптимізує хвостову рекурсію

Хоча хвостова рекурсія (див. наступний розділ) теоретично могла б працювати в одному кадрі без приросту стеку, Гвідо ван Россум свідомо відкинув TCO в CPython:

traceback стає нечитабельним - проміжні виклики зникають;
f.__name__ у внутрішніх кадрах стає невідповідним при виключенні;
Python - не функціональна мова, рекурсія не є основною формою циклів.

Tail Recursion Elimination (van Rossum, 2009) - оригінальна позиція. PyPy і Stackless Python зробили інші вибори.

Можливі способи оптимізації рекурсії

Мемоізація: Збереження результатів для вже обчислених підзадач.
Перехід до ітеративного підходу: Якщо можливо, можна переписати алгоритм у вигляді циклу.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_optimized(n):
    if n <= 1:
        return n
    return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)

print(fibonacci_optimized(50))  # Output: 12586269025

Хвостова рекурсія⚑

Це особливий вид рекурсії, коли функція завершується викликом самої себе без додаткових операторів. Коли ця умова виконується, компілятор розгортає рекурсію в цикл з одним стек-фреймом, просто змінюючи локальні змінні від ітерації до ітерації.

Так, класичне визначення рекурсивного факторіала return N * fact(N - 1) не підтримує хвостову рекурсію, оскільки для кожного стек-фрейму доведеться зберігати поточне значення N.

Щоб зробити рекурсію хвостовою, додають параметри-акумулятори. Завдяки їм функція знає про свій поточний стан. Нехай параметр acc за замовчуванням дорівнює 1. Тоді запис з хвостовою рекурсією виглядатиме так:

def fact(N, acc=1):
    if N == 1:
        return acc
    else:
        return fact(N - 1, acc * N)

Як можна оптимізувати хвостову рекурсію в Python⚑

class Recursion:
    """Can call other methods inside..."""
    def __init__(self, func):
        self.func = func

    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result

    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)


@Recursion
def sum_natural(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural.call(x - 1, result + x)

print(sum_natural(1000000))  # Now even such call doesn't throw an error RuntimeError: maximum recursion depth exceeded

Links

O-велике при оцінці складності. Як і для чого використовується [💡26/100]⚑

O-велике описує швидкість роботи алгоритму (не час).

Простий пошук⚑

O(n).

Бінарний пошук [💡16/100]⚑

Бінарний пошук – це ефективний метод пошуку елемента у відсортованому масиві даних. Він заснований на принципі розділяй та володарюй і працює за логарифмічний час - O(log n).

Беремо середній елемент і перевіряємо, чи це той елемент, який ми шукаємо. Якщо ні і він менший, ніж той, який ми шукаємо - відкидаємо половину з меншими значеннями (якщо більше, то з більшими) і повторюємо, поки не знайдемо шуканий елемент.

def binary_search(list, item):    
    low = 0  # low and high keep track of which part of the list you'll search in.
    high = len(list) - 1  
    while low <= high:  # While you haven't narrowed it down to one element ...
        mid = (low + high) // 2  # ... check the middle element
        guess = list[mid]  # Found the item.        
        if guess == item:
            return mid       
        if guess > item:   # The guess was too high.
            high = mid - 1        
        else:  # The guess was too low.
            low = mid + 1   
    return None  # Item doesn't exist

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1))  # => None  # We use None to indicate that the item wasn't found.

Фібоначчі⚑

Рекурсія

def fibonacci_recursive(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

n_terms = 10
fibonacci_terms = [fibonacci_recursive(i) for i in range(n_terms)]
print("Fibonacci sequence:", fibonacci_terms)

Цикл for

def fibonacci_loop(n):
    sequence = []
    a, b = 0, 1
    for _ in range(n):
        sequence.append(a)
        a, b = b, a + b  # Calculate the next by summing the previous two
    return sequence

fibonacci_terms = fibonacci_loop(10)
print("Fibonacci sequence:", fibonacci_terms)

Лінійна складність сортування⚑

Лінійна складність сортування вказує на те, що час виконання сортування зростає лінійно відносно розміру вхідних даних. Іншими словами, якщо ми маємо список (або масив) з n елементів і сортуємо його за допомогою алгоритму з лінійною складністю, то час сортування збільшуватиметься приблизно в n раз зі збільшенням кількості елементів у списку.

Сортування бульбашкою [💡10/100]⚑

Циклом for.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):  # Last i elements are already in place, so we don't need to check them
            if arr[j] > arr[j+1]:  # Swap if the element found is greater than the next element
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Циклом while.

def bubble_sort(arr):
    n = len(arr)
    sorted = False

    while not sorted:
        sorted = True
        i = 0
        while i < n-1:
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                sorted = False
            i += 1

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Швидке сортування⚑

На першому етапі вибирають опорний елемент. Найчастіше його беруть із середини масиву. Потім послідовно порівнюють перший елемент масиву з останнім, другий з передостаннім і т.д. Якщо елемент зліва від опорного елемента більший за правий, вони міняються місцями. Коли доходять до опорного елемента, ітерація вважається завершеною.

Далі описаний вище алгоритм застосовується до двох підмасивів. Перший - від першого елемента до опорного елемента (не включно), другий - від опорного до останнього.

Рекурсивний спуск триває, доки довжини підмасивів не стануть рівними одиниці.

Складність швидкого сортування в середньому випадку дорівнює N * log(N).

O(n * log n) (середній та найкращий випадок), O(n^2) у найгіршому. Швидкість залежить від вибору опорного елемента - у більшості випадків виконується за середній час. Базовий випадок - у масиві 0 або 1 елемент, тоді він вже впорядкований.

Алгоритм:

Вибрати опорний елемент
Розділити масив на два підмасиви - з елементами менше та більше опорного
Рекурсивно застосовувати швидке сортування до двох підмасивів

def quicksort(array):
    if len(array) < 2:
        return array  # base case, arrays with 0 or 1 element are already "sorted"

    pivot = array[0]  # recursive case
    less = [i for i in array[1:] if i <= pivot]  # sub-array of all the elements less than the pivot
    greater = [i for i in array[1:] if i > pivot]  # sub-array of all the elements greater than the pivot
    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

Сортування злиттям і зовнішнє сортування (дані не влазять у пам'ять)⚑

Summary

Сортування злиттям (merge sort) рекурсивно ділить масив навпіл, сортує половини й зливає їх за один лінійний прохід - стабільно O(n log n) без квадратичного найгіршого випадку. Його ключова перевага над quicksort - послідовний доступ, тому воно лягає на диск: коли файл більший за RAM, його ділять на частини, що влазять у пам'ять, сортують кожну окремо й зливають відсортовані відрізки. Це зовнішнє сортування (external sort) - класична відповідь на "як обробити дані, більші за пам'ять".

Злиття двох відсортованих послідовностей. Базова операція: два вказівники на початок кожної послідовності, на кожному кроці беруть менший елемент і зсувають його вказівник. Один прохід O(n), нової пам'яті - на результат.

Зовнішнє сортування великого файлу.

Читати файл частинами, що влазять у RAM; кожну частину сортувати в пам'яті (хоч quicksort) і записувати на диск як відсортований відрізок (run).
Злити відсортовані відрізки в один. Quicksort тут не годиться - він потребує довільного доступу й перестановок на місці, а на диску це дорого; merge читає відрізки послідовно, тому працює добре.

Зливати багато відрізків потрібно деревом (попарно: 1+2, 3+4, ..., потім пари між собою), а не вливаючи все в один акумулятор. Інакше перший відрізок перечитується знову й знову, і складність зростає. Дерево дає O(n log k) на злитті k відрізків, разом усе ще O(n log n).

У Python k-way злиття вже є в стандартній бібліотеці - heapq.merge ліниво зливає кілька відсортованих джерел (читаючи їх по рядку, не тримаючи в пам'яті):

import heapq

# runs - sorted file segments on disk
with open("run1") as a, open("run2") as b, open("run3") as c:
    for line in heapq.merge(a, b, c):   # reads one line at a time from each source
        out.write(line)                 # memory - O(k), not O(n)

Застосування: підрахунок унікальних у файлі, більшому за пам'ять. Якщо тримати всі значення в set - не влазить. Але на відсортованих даних однакові значення йдуть підряд, тож достатньо одного лінійного проходу зі збереженням попереднього значення (лічильник зростає лише на зміні) - пам'ять O(1). Тому задачу зводять до зовнішнього сортування + один прохід. У shell це робить sort | uniq | wc -l: GNU sort на великих файлах сам перемикається на зовнішнє злиття зі скиданням на диск.

Зв'язок із розподіленими системами. Та сама ідея, рознесена по машинах (кожна сортує свою частину локально, потім результати зливаються), - це MapReduce (Hadoop). На практиці зовнішнє сортування й злиття вже виконують самі бази даних - колонкове сховище на кшталт ClickHouse індексує й сортує дані самостійно.

Просте число⚑

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def is_prime2(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5 + 1)):
        if n % i == 0:
            return False
    return True

def is_prime3(number):
    if number <= 1:
        return False
    if number <= 3:
        return True
    if number % 2 == 0 or number % 3 == 0:
        return False
    i = 5
    while i * i <= number: # Use optimized trial division: check divisors up to square root of the number
        if number % i == 0 or number % (i + 2) == 0:
            return False
        i += 6 # all prime numbers are of the form 6n ± 1

    return True

Пошук в ширину⚑

O(V + E), де V - кількість вершин, E - кількість ребер, працює з графами і допомагає відповісти на питання двох типів:

Чи існує шлях від вершини А до вершини Б?
Який найкоротший шлях від вершини А до вершини Б?

Алгоритм

Покласти вершину, з якої починається пошук, в початково порожню чергу.
Вилучити з початку черги вершину u та позначити її як розгорнуту.
Якщо вершина u є цільовою вершиною, то завершити пошук з результатом "успіх".
У протилежному випадку, в кінець черги додаються всі наступники вершини u, які ще не розгорнуті та не знаходяться в черзі.
Якщо черга порожня, то всі вершини зв'язаного графа були переглянуті, отже, цільову вершину неможливо досягнути з початкової; завершити пошук з результатом "невдача".
Повернутися до п. 2.

Використовується для знаходження найкоротшого шляху в незваженому графі.

Пошук в глибину⚑

Пошук у глибину - це алгоритм, що шукає по дереву (або графу) спочатку в глибину, починаючи з кореня.

Алгоритм йде по дереву, переходячи між рівнями лівими дочірніми вузлами, поки не дійде до самого низу. Завершивши прохід гілки, алгоритм повертається назад, переглядаючи праві дочірні вузли цієї гілки. Причому, якщо можливо, вибирає найлівіші з вузлів, розташованих праворуч від попереднього маршруту. Завершивши перегляд усієї гілки, алгоритм переходить до вузла, розташованого праворуч від кореня, і знову йде лівими дочірніми вузлами до самого дна. Останнім аналізується крайній правий вузол (розташований праворуч усіх своїх попередників).

Алгоритм оптимальний для пошуку по дереву, чия глибина перевищує ширину. Для роботи алгоритму використовується стек. Оскільки стек є LIFO-структурою, йому не потрібно відстежувати покажчики вузлів, тому споживається менше пам'яті, ніж у разі пошуку в ширину. Коли алгоритм не може далі йти ліворуч, він починає аналізувати стек.

Ефективність - O(|E|+ |V|), де E - кількість ребер (граней), V – кількість вершин.

Алгоритм Дейкстри⚑

Використовується для знаходження найлегшого шляху у зваженому графі. Працює на будь-якому графі (орієнтованому чи ні, зокрема з циклами) за умови невід'ємних ваг ребер. За наявності від'ємних ваг Дейкстра некоректний - тоді застосовують Беллмана-Форда.

Складається з 4 кроків:

Знайти вершину з найменшою вагою.
Оновити вагу сусідів цієї вершини.
Повторювати, доки це не буде зроблено для всіх вершин.
Обчислити кінцевий шлях.

Не працює з від'ємними вагами - для графів з від'ємними вагами існує спеціальний алгоритм, відомий як алгоритм Беллмана-Форда.

Жадібні алгоритми⚑

Використовуються, коли обчислення точного рішення займає занадто багато часу або коли висока точність не є необхідною. Ефективність наближеного алгоритму оцінюється за такими критеріями:

швидкістю виконання
близькістю отриманого рішення до оптимального

Жадні алгоритми є хорошими не тільки тим, що їх зазвичай легко формулювати, але і тим, що простота зазвичай переходить у швидкість виконання.

Жадні алгоритми прагнуть до локальної оптимізації в розрахунку на те, що в кінцевому результаті буде досягнуто глобальний оптимум.

Жадні алгоритми легко реалізовуються та швидко виконуються, тому з них часто отримуються добрі наближені алгоритми.

Як впізнати NP-повну задачу⚑

Не існує простого способу зробити це, але існує ряд ознак:

алгоритм швидко працює при малій кількості елементів, але сильно уповільнюється при збільшенні їх кількості;
формулювання ~всі комбінації х~ часто вказує на NP-повноту задачі;
доводиться обчислювати всі можливі варіанти Х, оскільки задачу неможливо розбити на менші підзадачі? Така задача може виявитися NP-повною;
якщо в задачі зустрічається певна послідовність (наприклад, послідовність міст, як у задачі комівояжера) і задача не має простого рішення, вона може бути NP-повною;
якщо в задачі зустрічається певна множина (наприклад, множина радіостанцій) і задача не має простого рішення, вона може бути NP-повною;
чи можна переформулювати задачу в умовах задачі покриття множини або задачі комівояжера? У такому випадку ваша задача точно є NP-повною.

Для NP-повних задач не існує відомих швидких рішень. Якщо є NP-повна задача, то краще скористатися наближеним алгоритмом.

Динамічне програмування⚑

Застосовується для оптимізації певної характеристики, наприклад, покласти речі в рюкзак на найбільшу суму або знайти найдовшу підстроку у двох словах і так далі.

Працює лише в ситуаціях, коли задачу можна розбити на автономні підзадачі.

У кожному рішенні з області динамічного програмування будується таблиця (!). Значення комірок таблиці зазвичай відповідає оптимізованій характеристиці (ціна речей, їх важливість, кількість повторень літер і так далі).

Не існує єдиної формули для обчислення рішень методом динамічного програмування.

Алгоритм k найближчих сусідів⚑

Застосовується для класифікації та регресії. В ньому використовується перевірка k найближчих сусідів.

Класифікація - розподіл за категоріями.

Регресія - прогнозування результату (наприклад, у вигляді числа). Витягання ознаки називається перетворенням елемента (наприклад, фрукта чи користувача) в список чисел, які можна використовувати для порівняння. Якісний вибір ознак дуже важливий. Використовується в машинному навчанні, побудові рекомендаційних систем, прогнозуванні тощо.

Для обчислення відстані до сусіда використовується формула Піфагора (sqrt((x1 - x2)^2 + (y1 - y2)^2)) або метрика близькості косинусів. Метрика близькості косинусів не вимірює відстань між двома векторами, замість цього вона порівнює кути двох векторів.

Геопросторовий пошук найближчих сусідів⚑

Summary

Задача "знайти N найближчих точок до заданої координати" при великій кількості точок (десятки-сотні мільйонів). Наївний скан O(n) на запит не годиться - потрібен просторовий індекс (рівномірна сітка, quadtree, geohash/S2/H3), а сам запит виконують як розширюване вікно навколо точки з уточненням за точною відстанню. У реляційній БД це закриває PostGIS: GiST-індекс і KNN-оператор <->.

Постановка: дано N точок на площині (наприклад, заклади на карті) і запитну координату; повернути N найближчих. N може бути великим (100M), а відповідь потрібна за десятки мілісекунд.

Наївний baseline. Пройти всі точки, порахувати відстань, тримати N найближчих у max-heap розміру N → O(n·log N) часу, O(N) пам'яті. Коректна відправна точка, але O(n) на кожен запит неприйнятно при 100M точок - звідси потреба в індексі.

Просторове розбиття.

Рівномірна сітка (grid). Точка потрапляє в клітинку за (x, y); запит дивиться свою та сусідні клітинки. Проста, але страждає від нерівномірності - у щільних центрах міст клітинка переповнюється, на околицях порожня.
Quadtree. Рекурсивно ділити квадрат на 4, доки в клітинці не залишиться більше за поріг точок → ієрархія квадратів. Запит спускається деревом, тримаючи лише квадрати, що перетинають область пошуку. Логарифмічно за рівномірного розподілу; на скошених даних вироджується до O(n).
Geohash / S2 (Google) / H3 (Uber). Кодують 2D-координату в 1D-ключ зі збереженням локальності (сусідні точки → близькі ключі) → можна індексувати у звичайній БД чи KV-сховищі й шукати за діапазоном/префіксом, без власного дерева.

Від "точок у регіоні" до "N найближчих". Почати з малого вікна навколо точки, зібрати кандидатів із клітинок, що його перетинають, уточнити за точною відстанню й обрати N. Якщо знайдено менше за N - розширити вікно й повторити (expanding search).

Квадрат vs коло як область пошуку. Перевірка перетину квадрат-квадрат (порівняння інтервалів по кожній осі) дешевша за коло-квадрат, тож фільтрують по осі-вирівняному прямокутнику. Прямокутник - над-апроксимація радіуса, тому кандидатів усе одно уточнюють за точною відстанню (box-filter → refine).

У реляційній БД. PostgreSQL + PostGIS: просторовий індекс GiST/SP-GiST і KNN-оператор <-> дають найближчі ефективно прямо запитом - власну реалізацію дерева писати зазвичай не потрібно.

-- N nearest venues to a point, using the GiST KNN operator <->
SELECT id, name
FROM venues
ORDER BY geom <-> ST_SetSRID(ST_MakePoint(:lon, :lat), 4326)
LIMIT 100;