iron.algorithms

Архитектура алгоритмического модуля

Модуль iron.algorithms представляет собой набор структурированных реализаций классических и прикладных алгоритмов, объединённых единым стилем API и предсказуемыми контрактами входных и выходных данных. В основе лежит идея минимизации побочных эффектов и максимальной переиспользуемости алгоритмических компонентов в различных слоях приложения.

Каждый алгоритм в библиотеке оформлен как чистая функция или как метод объекта-утилиты, что позволяет использовать их как в функциональном стиле, так и в составе объектно-ориентированных решений.

Ключевые принципы реализации:

  • детерминированность поведения
  • отсутствие скрытых мутаций входных данных
  • явная работа со структурами данных
  • унифицированная обработка ошибок
  • предсказуемая сложность операций

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

В iron.algorithms реализован набор базовых и оптимизированных методов сортировки, адаптированных под разные типы данных и размеры массивов.

quickSort

Реализация быстрой сортировки основана на классическом подходе разбиения массива относительно опорного элемента.

Основная идея:

  • выбор pivot (опорного элемента)
  • разделение массива на элементы меньше и больше pivot
  • рекурсивная обработка подмассивов

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

import { quickSort } from "iron.algorithms";

const result = quickSort([5, 3, 8, 4, 2]);

Сложность:

  • средняя: O(n log n)
  • худшая: O(n²) при неудачном выборе pivot

Оптимизации:

  • медиана из трёх
  • гибрид с insertion sort для малых массивов

mergeSort

Сортировка слиянием реализована через стратегию “разделяй и властвуй”. Основной акцент сделан на стабильности сортировки.

Ключевые этапы:

  • рекурсивное деление массива
  • слияние отсортированных частей
  • сохранение относительного порядка равных элементов
import { mergeSort } from "iron.algorithms";

const sorted = mergeSort([10, 7, 2, 9]);

Сложность:

  • всегда O(n log n)
  • дополнительная память O(n)

heapSort

Алгоритм основан на структуре бинарной кучи. Используется встроенная реализация heap внутри модуля.

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

  • сортировка на месте
  • отсутствие дополнительной памяти O(n)
  • нестабильность результата

Алгоритмы поиска

binarySearch

Бинарный поиск применяется только к отсортированным структурам данных.

import { binarySearch } from "iron.algorithms";

const index = binarySearch([1, 3, 5, 7, 9], 7);

Поведение:

  • возвращает индекс найденного элемента
  • при отсутствии — -1
  • работает за O(log n)

Особенность реализации в iron.algorithms — поддержка кастомных компараторов.

linearSearch

Последовательный поиск используется для неотсортированных данных.

Сложность: O(n)

Дополнительно поддерживается:

  • ранний выход по предикату
  • поиск по сложным объектам

Графовые алгоритмы

Модуль содержит реализацию базовых алгоритмов работы с графами, представленных через список смежности.

BFS (обход в ширину)

Используется для поиска кратчайших путей в невзвешенных графах.

import { bfs } from "iron.algorithms";

const result = bfs(graph, startNode);

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

  • использование очереди
  • гарантия минимального количества рёбер в пути

DFS (обход в глубину)

Реализован в рекурсивной и итеративной форме.

Применяется для:

  • топологической сортировки
  • поиска компонент связности
  • обнаружения циклов

Dijkstra

Алгоритм кратчайшего пути в взвешенном графе без отрицательных рёбер.

Внутри используется приоритетная очередь.

import { dijkstra } from "iron.algorithms";

const distances = dijkstra(graph, start);

Сложность:

  • O((V + E) log V)

Алгоритмы динамического программирования

Модуль включает набор оптимизированных DP-решений с мемоизацией и табуляцией.

fibonacci

Несколько реализаций:

  • рекурсивная с мемоизацией
  • итеративная
  • матричная экспонентация
import { fibonacci } from "iron.algorithms";

const value = fibonacci(50);

knapsack (задача рюкзака)

Реализация 0/1 knapsack:

  • двумерная таблица состояния
  • оптимизация памяти до O(n)

longestCommonSubsequence

Используется для сравнения строк и последовательностей.

import { lcs } from "iron.algorithms";

const result = lcs("ABCBDAB", "BDCAB");

Структуры данных, используемые внутри алгоритмов

Heap (куча)

Используется в Dijkstra и heapSort.

Поддерживает:

  • min-heap
  • max-heap
  • пользовательские компараторы

Deque

Двусторонняя очередь применяется в BFS-оптимизациях и sliding window алгоритмах.

Union-Find (DSU)

Структура для работы с компонентами связности.

Поддерживаемые операции:

  • find
  • union
  • path compression
  • union by rank

Функциональные утилиты

composeAlgorithms

Позволяет комбинировать несколько алгоритмов в цепочку обработки данных.

import { composeAlgorithms } from "iron.algorithms";

const pipeline = composeAlgorithms([
  normalize,
  filterNegative,
  quickSort
]);

memoize

Универсальная мемоизация функций, используемая в DP-алгоритмах.

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

  • поддержка сложных ключей
  • TTL-кэширование
  • контроль памяти

Работа с асимптотикой

Каждый алгоритм в iron.algorithms сопровождается встроенной аннотацией сложности, доступной через метаданные:

quickSort.meta.timeComplexity; // "O(n log n)"
quickSort.meta.spaceComplexity; // "O(log n)"

Это позволяет использовать библиотеку в образовательных и аналитических системах, где важна оценка производительности.

Внутренние соглашения API

  • Все функции принимают данные по значению
  • Результаты всегда возвращаются новыми структурами
  • Не допускается скрытая мутация входных массивов
  • Ошибки приводят к явным исключениям с кодами состояния
  • Поддерживается строгая типизация через JSDoc или TypeScript декларации
Оглавление