Algorithms & Data Structures — Laravel Demo

Учебный проект на Laravel 12, демонстрирующий алгоритмы сортировки, поиска, структуры данных, алгоритмы кэширования и работу с очередями RabbitMQ / Kafka. Всё завёрнуто в Docker.

Содержание

Стек технологий
Структура проекта
Быстрый старт
API — Сортировки
API — Поиск
API — Структуры данных
API — Кэширование
API — Очереди

Стек технологий

Компонент	Версия / Образ	Порт
PHP	8.3 FPM Alpine	—
Laravel	12	—
Nginx	1.25 Alpine	8080
PostgreSQL	16 Alpine	5432
Redis	7 Alpine	6379
RabbitMQ	3.13 Management Alpine	5672, 15672 (UI)
Kafka	Confluent 7.6	9092
Kafka UI	provectuslabs/kafka-ui	8090

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

.
├── docker-compose.yml
├── docker/
│   ├── php/
│   │   ├── Dockerfile        # PHP 8.3 + расширения (pgsql, redis, rdkafka, amqp)
│   │   ├── entrypoint.sh     # composer install → key:generate → migrate → php-fpm
│   │   └── php.ini
│   ├── nginx/
│   │   └── default.conf
│   └── postgres/
│       └── init.sql          # Тестовые данные
├── app/
│   ├── Cache/                # LRUCache, LFUCache, FIFOCache, TTLCache, LRUCacheNode
│   ├── DataStructures/       # BSTNode, BinarySearchTree, Graph, TrieNode, Trie
│   ├── Services/
│   │   ├── Sorting/          # SortingService
│   │   ├── Search/           # SearchService
│   │   ├── DataStructures/   # DataStructuresService
│   │   ├── Cache/            # CacheAlgorithmsService
│   │   └── Messaging/        # RabbitMQService, KafkaService
│   └── Http/Controllers/Api/
└── routes/
    └── api.php               # 29 маршрутов

Быстрый старт

1. Клонировать репозиторий

git clone <repo-url>
cd algorithms_and_data_structures.

2. Запустить Docker

docker-compose up --build

Первый запуск занимает несколько минут — собирается образ с PHP расширениями. entrypoint.sh автоматически выполнит composer install, key:generate и migrate.

3. Проверить что всё запустилось

# Laravel healthcheck
curl http://localhost:8080/up

# Первый API запрос
curl http://localhost:8080/api/sorting/demo

4. Веб-интерфейсы

Сервис	URL	Логин / Пароль
RabbitMQ UI	http://localhost:15672	`rabbit_user` / `rabbit_pass`
Kafka UI	http://localhost:8090	—

Полезные команды

# Войти в контейнер приложения
docker exec -it algo_app sh

# Запустить миграции вручную
docker exec -it algo_app php artisan migrate

# Посмотреть логи
docker-compose logs -f app

# Остановить всё
docker-compose down

# Остановить и удалить volumes (сброс БД)
docker-compose down -v

API — Сортировки

Базовый URL: http://localhost:8080/api/sorting

Демо всех алгоритмов

GET /api/sorting/demo
GET /api/sorting/demo?size=200          # случайный массив из 200 элементов
GET /api/sorting/demo?array[]=5&array[]=3&array[]=8

Возвращает результаты и время выполнения для всех алгоритмов: quicksort, bubble_sort, merge_sort, insertion_sort, selection_sort, heap_sort, counting_sort, radix_sort, php_sort

Quicksort

GET /api/sorting/quicksort
GET /api/sorting/quicksort?array[]=64&array[]=34&array[]=25&array[]=12

Возвращает отсортированный массив + описание сложности и принципа работы.

Usort — пользовательская сортировка

# Сортировка массива объектов по полю
GET /api/sorting/usort?field=age&direction=asc
GET /api/sorting/usort?field=name&direction=desc

Бенчмарк

GET /api/sorting/benchmark?size=500     # сравнение скоростей на 500 элементах
GET /api/sorting/benchmark?size=5000

API — Поиск

Базовый URL: http://localhost:8080/api/search

Сравнение всех алгоритмов

GET /api/search/demo?target=42
GET /api/search/demo?target=999&size=10000   # массив из 10000 элементов

Сравнивает: linear, binary, binary_recursive, jump, interpolation, exponential Показывает количество сравнений и время для каждого алгоритма.

Пример ответа:

{
  "array_size": 1000,
  "target": 42,
  "algorithms": {
    "linear":  { "found": true, "index": 41, "comparisons": 42,  "time_ms": 0.08 },
    "binary":  { "found": true, "index": 41, "comparisons": 10,  "time_ms": 0.003 },
    "jump":    { "found": true, "index": 41, "comparisons": 10,  "time_ms": 0.005 }
  }
}

Линейный поиск

GET /api/search/linear?target=5
GET /api/search/linear?target=99&array[]=10&array[]=99&array[]=30

Бинарный поиск

GET /api/search/binary?target=42

Возвращает результаты итеративного и рекурсивного вариантов.

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

Базовый URL: http://localhost:8080/api/data-structures

Шпаргалка по всем структурам

GET /api/data-structures/all

PHP Arrays как упорядоченные карты

GET /api/data-structures/arrays

Демонстрирует: порядок вставки, смешанные ключи, ловушки с числовыми ключами. PHP array = HashTable + DoublyLinkedList (O(1) доступ + сохранение порядка).

SPL структуры

GET /api/data-structures/spl

Демонстрирует все SPL структуры с примерами операций:

Класс	Тип	get/set
`SplStack`	LIFO стек	O(1)
`SplQueue`	FIFO очередь	O(1)
`SplMinHeap`	Мин-куча	O(log n)
`SplMaxHeap`	Макс-куча	O(log n)
`SplPriorityQueue`	Приоритетная очередь	O(log n)
`SplDoublyLinkedList`	Двусвязный список	O(1) на концах
`SplFixedArray`	Фикс. массив	O(1), -37% памяти

Хэш-таблицы

GET /api/data-structures/hash-table

Демонстрирует: PHP array как хэш-таблица, WeakMap, хранение свойств объектов.

Бинарное дерево поиска (BST)

GET /api/data-structures/tree

Вставка, поиск, три обхода: inorder (отсортированный), preorder, postorder. Высота дерева.

Граф — BFS и DFS

GET /api/data-structures/graph

Граф A-B-C-D-E. Сравнение BFS (обход в ширину, Queue) и DFS (обход в глубину, Stack).

Trie (префиксное дерево)

GET /api/data-structures/trie

Поиск по словарю [apple, app, application, apply, banana]. Автодополнение по префиксу.

API — Кэширование

Базовый URL: http://localhost:8080/api/cache

Сравнение алгоритмов

GET /api/cache/compare

LRU — Least Recently Used

GET /api/cache/lru

Пошаговая трассировка: видно какой элемент вытесняется и почему.

SET a=1 → cache: a
SET b=2 → cache: a,b
SET c=3 → cache: a,b,c
GET a   → HIT    | cache: b,c,a   ← 'a' переместился в конец (самый свежий)
SET d=4 → cache: c,a,d            ← 'b' вытеснен (давно не использовался)
GET b   → MISS

LFU — Least Frequently Used

GET /api/cache/lfu

Трассировка с частотами: { "a": 3, "b": 2, "c": 1 } → вытесняется c.

FIFO — First In, First Out

GET /api/cache/fifo

TTL — Time To Live

GET /api/cache/ttl

⚠️ Этот эндпоинт делает sleep(3) для демонстрации истечения TTL. Ответ придёт через ~3 секунды.

API — Очереди

Базовый URL: http://localhost:8080/api/messaging

Требуется: запущенные контейнеры rabbitmq и kafka.

Сравнение RabbitMQ vs Kafka

GET /api/messaging/compare

Подробное сравнение: модель, throughput, replay, маршрутизация, use cases.

RabbitMQ

Direct Exchange — точная маршрутизация

POST /api/messaging/rabbitmq/direct
Content-Type: application/json

{
  "routing_key": "error",
  "payload": { "message": "Database connection failed", "service": "db" }
}

Сообщение попадёт только в очередь algo.error.

Fanout Exchange — широковещательная рассылка

POST /api/messaging/rabbitmq/fanout
Content-Type: application/json

{
  "payload": { "event": "cache.invalidate", "timestamp": "2024-01-01T10:00:00" }
}

Сообщение разойдётся во все очереди: service_a, service_b, service_c.

Topic Exchange — маршрутизация по паттернам

POST /api/messaging/rabbitmq/topic
Content-Type: application/json

{
  "routing_key": "logs.db.error",
  "payload": { "level": "error", "message": "Connection timeout" }
}

Routing key	Попадёт в `logs.#`	`logs.*.error`	`logs.db.*`
`logs.db.error`	✅	✅	✅
`logs.api.warn`	✅	❌	❌
`logs.db.info`	✅	❌	✅

Получение сообщений

GET /api/messaging/rabbitmq/consume?queue=algo.error

Dead Letter Exchange

GET /api/messaging/rabbitmq/dlx

Настраивает DLX: просроченные / отклонённые сообщения → algo.dead.letters.

Kafka

Публикация события

POST /api/messaging/kafka/publish
Content-Type: application/json

{
  "topic": "algo.orders",
  "key": "order:123",
  "payload": { "order_id": 123, "event": "order.created", "amount": 1500 }
}

Все события с одинаковым key попадают в одну партицию → гарантия порядка.

Consumer Groups

GET /api/messaging/kafka/consumer-groups

Объясняет ключевое отличие от RabbitMQ:

RabbitMQ: одно сообщение → один консьюмер
Kafka: одно событие → все Consumer Groups

Управление offset (Replay)

GET /api/messaging/kafka/offsets

Показывает как перечитать события с любой точки в прошлом.

Exactly-Once семантика

GET /api/messaging/kafka/exactly-once

Ключевые различия RabbitMQ vs Kafka

Критерий	RabbitMQ	Kafka
Модель	Брокер сообщений	Журнал событий
Push/Pull	Push → консьюмер	Pull ← консьюмер
Хранение	Удаляет после ACK	Хранит N дней
Replay	❌ Невозможен	✅ Любой offset
Маршрутизация	Гибкая (4 типа exchange)	Простая (topic + partition key)
Throughput	~50k msg/sec	~1M+ msg/sec
Когда выбрать	RPC, TTL, DLX, приоритеты	Event Sourcing, CDC, аналитика

Name		Name	Last commit message	Last commit date
Latest commit History 3 Commits
app		app
bootstrap		bootstrap
config		config
database		database
docker		docker
public		public
resources		resources
routes		routes
storage		storage
tests		tests
.editorconfig		.editorconfig
.env.example		.env.example
.gitattributes		.gitattributes
.gitignore		.gitignore
README.md		README.md
artisan		artisan
composer.json		composer.json
composer.lock		composer.lock
docker-compose.yml		docker-compose.yml
package.json		package.json
phpunit.xml		phpunit.xml
vite.config.js		vite.config.js

Folders and files

Latest commit

History

Repository files navigation

Algorithms & Data Structures — Laravel Demo

Содержание

Стек технологий

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

Быстрый старт

1. Клонировать репозиторий

2. Запустить Docker

3. Проверить что всё запустилось

4. Веб-интерфейсы

Полезные команды

API — Сортировки

Демо всех алгоритмов

Quicksort

Usort — пользовательская сортировка

Бенчмарк

API — Поиск

Сравнение всех алгоритмов

Линейный поиск

Бинарный поиск

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

Шпаргалка по всем структурам

PHP Arrays как упорядоченные карты

SPL структуры

Хэш-таблицы

Бинарное дерево поиска (BST)

Граф — BFS и DFS

Trie (префиксное дерево)

API — Кэширование

Сравнение алгоритмов

LRU — Least Recently Used

LFU — Least Frequently Used

FIFO — First In, First Out

TTL — Time To Live

API — Очереди

Сравнение RabbitMQ vs Kafka

RabbitMQ

Direct Exchange — точная маршрутизация

Fanout Exchange — широковещательная рассылка

Topic Exchange — маршрутизация по паттернам

Получение сообщений

Dead Letter Exchange

Kafka

Публикация события

Consumer Groups

Управление offset (Replay)

Exactly-Once семантика

Ключевые различия RabbitMQ vs Kafka

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

Packages