Лабораторная работа №3

Тема: Алгоритмический мини-пакет (структуры данных и сортировки)

Описание

Реализация набора алгоритмов и структур данных для работы с сортировкой и базовыми структурами данных. Все алгоритмы реализованы без использования встроенных функций list.sort() и sorted().

Структура проекта

lab3/
├── src/
│   ├── __init__.py              # Экспорт основных функций
│   ├── factorial_fibonacci.py  # Факториал и Фибоначчи
│   ├── sorts.py                 # Алгоритмы сортировки
│   ├── stack.py                 # Реализация стека
│   ├── generators.py            # Генераторы тест-кейсов
│   └── benchmark.py             # Функции бенчмаркинга
├── tests/                           # Модульные тесты
├── pyproject.toml                   # Конфигурация проекта
├── example.py                       # Пример использования
└── README.md

Общий алгоритм работы

Обработка ошибок

Все структуры данных и функции выбрасывают соответствующие исключения при некорректных операциях:

• ValueError: При недопустимых входных данных (отрицательные числа для факториала/Фибоначчи, некорректные параметры генераторов)
• IndexError: При попытке доступа к элементам пустых структур данных (pop, peek)

Стратегия реализации

1. Сортировки: Все алгоритмы возвращают новую копию массива, не изменяя исходный
2. Структуры данных: Реализован Stack на связном списке с поддержкой O(1) min()
3. Генераторы: Поддерживают seed для воспроизводимости результатов
4. Бенчмаркинг: Бенчмарки для сортировок, факториала и Фибоначчи

Компоненты

1. Факториал и Фибоначчи

Реализованы итеративные и рекурсивные версии:

from lab3 import factorial, factorial_recursive, fibo, fibo_recursive

# Факториал
factorial(5)          # 120
factorial_recursive(5)  # 120

# Фибоначчи
fibo(10)              # 55
fibo_recursive(10)   # 55

Особенности:

• Валидация входных данных (отрицательные числа вызывают ValueError)
• Рекурсивная версия Фибоначчи имеет экспоненциальную сложность (для демонстрации)

2. Алгоритмы сортировки

Все сортировки поддерживают опциональные параметры key и cmp:

from lab3 import bubble_sort, quick_sort, counting_sort, radix_sort, bucket_sort, heap_sort

arr = [64, 34, 25, 12, 22, 11, 90]

# Базовое использование
sorted_arr = bubble_sort(arr)
sorted_arr = quick_sort(arr)
sorted_arr = counting_sort(arr)
sorted_arr = radix_sort(arr)
sorted_arr = heap_sort(arr)

# Bucket sort для float
float_arr = [0.897, 0.565, 0.656, 0.1234]
sorted_float = bucket_sort(float_arr)

# С функцией key
sorted_by_abs = quick_sort([-5, 3, -2, 0, 1], key=lambda x: abs(x))

# С компаратором
sorted_reverse = quick_sort([5, 2, 8], cmp=lambda a, b: -1 if a > b else (1 if a < b else 0))

Реализованные алгоритмы:

1. Bubble Sort - Пузырьковая сортировка (O(n²))
2. Quick Sort - Быстрая сортировка (O(n log n) в среднем)
3. Counting Sort - Сортировка подсчетом (O(n + k))
4. Radix Sort - Поразрядная сортировка (O(d × n))
5. Bucket Sort - Блочная сортировка для float (O(n + k))
6. Heap Sort - Пирамидальная сортировка (O(n log n))

Особенности реализации:

• Bucket Sort: По умолчанию работает с числами в диапазоне [0, 1), автоматически нормализует другие диапазоны
• Radix Sort: Поддерживает отрицательные числа, разделяя их на положительные и отрицательные
• Counting Sort: Работает только с целыми числами, key и cmp игнорируются
• Все алгоритмы не изменяют исходный массив

3. Структура данных: Стек (Stack)

Реализация стека на связном списке:

from lab3 import Stack

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

stack.peek()    # 3
stack.pop()     # 3
stack.min()     # 1 (O(1))
len(stack)      # 2
stack.is_empty()  # False

Особенности:

• Реализация на связном списке
• min() работает за O(1) благодаря дополнительному стеку минимумов
• Все операции выбрасывают IndexError при работе с пустым стеком

Примечание: Также есть альтернативная реализация StackList на основе list, но она не экспортируется в основном модуле.

4. Генераторы тест-кейсов

from lab3 import (
    rand_int_array,
    nearly_sorted,
    many_duplicates,
    reverse_sorted,
    rand_float_array,
)

# Случайный массив целых чисел
arr = rand_int_array(100, 0, 1000, seed=42)

# С уникальными элементами
arr = rand_int_array(50, 0, 100, distinct=True, seed=42)

# Почти отсортированный массив
arr = nearly_sorted(100, swaps=10, seed=42)

# Много дубликатов
arr = many_duplicates(100, k_unique=5, seed=42)

# Обратно отсортированный
arr = reverse_sorted(100)

# Случайные float
arr = rand_float_array(100, 0.0, 1.0, seed=42)

Особенности:

• Все генераторы поддерживают seed для воспроизводимости
• rand_int_array с distinct=True проверяет возможность создания уникального массива

5. Бенчмаркинг

Бенчмаркинг сортировок

from lab3 import timeit_once, benchmark_sorts
from lab3.sorts import bubble_sort, quick_sort, heap_sort
from lab3.generators import rand_int_array

# Измерение времени одной функции
arr = rand_int_array(1000, 0, 1000, seed=42)
time = timeit_once(quick_sort, arr)
print(f"Quick sort: {time:.6f} seconds")

# Сравнение нескольких алгоритмов сортировки
arrays = {
    "small": rand_int_array(100, 0, 100, seed=42),
    "medium": rand_int_array(1000, 0, 1000, seed=42),
    "large": rand_int_array(10000, 0, 10000, seed=42),
}

algos = {
    "bubble": bubble_sort,
    "quick": quick_sort,
    "heap": heap_sort,
}

results = benchmark_sorts(arrays, algos)
for array_name, times in results.items():
    print(f"\n{array_name}:")
    for algo_name, time in times.items():
        print(f"  {algo_name}: {time:.6f}s")

Бенчмаркинг факториала и Фибоначчи

from lab3 import benchmark_factorial_fibonacci
from lab3 import factorial, factorial_recursive, fibo, fibo_recursive

n_values = [5, 10, 15, 20]
funcs = {
    "factorial": factorial,
    "factorial_recursive": factorial_recursive,
    "fibo": fibo,
    "fibo_recursive": fibo_recursive,
}

results = benchmark_factorial_fibonacci(n_values, funcs)
for func_name, times in results.items():
    print(f"\n{func_name}:")
    for n, time in times.items():
        if time >= 0:
            print(f"  n={n}: {time:.6f}s")

Установка и запуск

Установка зависимостей

pip install -e .

Запуск тестов

# Все тесты
python -m unittest discover tests

# С подробным выводом
python -m unittest discover tests -v

# Конкретный тест
python -m unittest tests.test_sorts

Пример использования

from lab3 import (
    factorial,
    factorial_recursive,
    fibo,
    fibo_recursive,
    quick_sort,
    Stack,
    rand_int_array,
    benchmark_sorts,
    benchmark_factorial_fibonacci,
)

# Факториал
print(f"5! = {factorial(5)}")

# Фибоначчи
print(f"F(10) = {fibo(10)}")

# Сортировка
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print(f"Sorted: {sorted_arr}")

# Стек
stack = Stack()
stack.push(1)
stack.push(2)
print(f"Stack top: {stack.peek()}")

# Бенчмаркинг сортировок
arrays = {"test": rand_int_array(1000, 0, 1000, seed=42)}
algos = {"quick": quick_sort}
results = benchmark_sorts(arrays, algos)
print(f"Sort benchmark results: {results}")

# Бенчмаркинг факториала и Фибоначчи
n_values = [5, 10, 15]
funcs = {"factorial": factorial, "fibo": fibo}
fib_results = benchmark_factorial_fibonacci(n_values, funcs)
print(f"Factorial/Fibonacci benchmark results: {fib_results}")

Тестирование

Проект включает комплексные модульные тесты:

• test_factorial_fibonacci.py - Тесты факториала и Фибоначчи
• test_sorts.py - Тесты всех алгоритмов сортировки
• test_stack.py - Тесты стека
• test_generators.py - Тесты генераторов тест-кейсов

Особенности реализации

Сортировки

1. Неизменяемость: Все сортировки возвращают новую копию массива
2. Поддержка ключей и компаратора: Все сортировки поддерживают key и cmp параметры
3. Обработка граничных случаев: Пустые массивы, один элемент, уже отсортированные массивы
4. Отрицательные числа: Radix sort корректно обрабатывает отрицательные числа

Структуры данных

1. Исключения: Все операции выбрасывают IndexError при некорректном использовании
2. O(1) min(): Stack поддерживает получение минимума за константное время
3. Реализация: Stack реализован на связном списке

Генераторы

1. Воспроизводимость: Все генераторы поддерживают seed
2. Валидация: Проверка корректности параметров (например, distinct массив)
3. Разнообразие: Различные типы тестовых данных для комплексного тестирования

Чему я научился?

• Алгоритмы сортировки: Реализация различных алгоритмов сортировки с пониманием их сложности
• Структуры данных: Реализация базовых структур данных различными способами
• Обработка ошибок: Правильное использование исключений для валидации входных данных
• Тестирование: Написание комплексных модульных тестов
• Архитектура: Организация кода в модульную структуру
• Оптимизация: Реализация O(1) операций (min() в стеке)
• Генераторы: Создание воспроизводимых тестовых данных

Дополнительные ресурсы

Практика LeetCode

• LeetCode 509: Fibonacci Number
• LeetCode 70: Climbing Stairs
• LeetCode 75: Sort Colors
• LeetCode 20: Valid Parentheses
• LeetCode 225: Implement Stack using Queues

HackerRank

• Counting Sort 1
• Counting Sort 2
• Counting Sort 3
• Quick Sort 1