Тема: algorithms
-
Порядок зависимостей через обход графа: BFS, DFS и топологическая сортировка
Моделируйте зависимости ориентированным графом, находите всё затронутое изменением обходом в ширину или глубину, а порядок сборки или миграций получайте алгоритмом Кана или обходом DFS с обработкой после потомков, явно сообщая о циклах. Топологическую сортировку реализуют graphlib и tsort.
-
Хеш-таблицы на практике: коллизии, коэффициент заполнения и хеширование с seed
Хеш-таблица в среднем быстра лишь при равномерном распределении ключей по корзинам. Её реальное поведение определяют коллизии, коэффициент заполнения, запускающий перехеширование, и отдельное начальное значение хеширования для каждого процесса как защита от hash flooding. Не сохраняйте хеш-значения и не полагайтесь на порядок обхода.
-
Динамическое программирование по шагам: вывод редакционного расстояния
Динамическое программирование превращает рекурсивное определение с перекрывающимися подзадачами в полиномиальный алгоритм: задайте состояние, рекуррентное соотношение и базовые случаи, используйте мемоизацию или таблицу, затем сократите память. Редакционное расстояние между строками полностью выведено как разобранный пример.
-
Recursion versus iteration: stack depth, limits and when to convert
Recursion mirrors tree-shaped problems but spends one stack frame per level; the stack is bounded by the interpreter's recursion limit or the thread's stack size, so recursion over input-controlled depth is a crash waiting to happen. Convert to an explicit stack or loop when depth grows with input size.
-
Резервуарная выборка: равномерная выборка из потока неизвестной длины
Храните k элементов потока, не зная его длины: заполните резервуар первыми k, затем для элемента i с вероятностью k/i заменяйте случайную ячейку. Один проход, O(k) памяти, каждый элемент попадает в выборку с вероятностью ровно k/n; это показывает короткое доказательство с сокращением произведения.
-
Префиксные деревья: автодополнение и поиск самого длинного префикса
Префиксное дерево хранит строки с узлом для каждого общего префикса: поиск зависит от длины ключа, а не числа ключей; все ключи с одним префиксом образуют поддерево; самый длинный сохранённый префикс запроса находится за один проход. Применяйте для автодополнения и маршрутизации, сначала сравнив с отсортированным массивом.
-
Ловушки двоичного поиска: переполнение середины и ошибки границ на единицу
Двоичный поиск короток, но в нём общеизвестно легко ошибиться: (low + high) / 2 переполняет целые фиксированной разрядности, включённые и исключённые границы путаются, а дубликаты требуют решить, какой индекс вернуть. Используйте библиотеку или монотонный предикат с полуоткрытыми интервалами и проверяйте края.
-
Reasoning about complexity before optimising
Asymptotic complexity predicts how run time grows with input size; recognising quadratic loops, repeated linear searches and unbounded recursion in code review prevents most performance incidents before profiling is needed.
-
Token bucket, leaky bucket and sliding window: how rate-limiter algorithms differ
Fixed windows are cheap but let twice the limit through at a boundary; sliding logs are exact but store every timestamp; sliding-window counters approximate in constant memory; token buckets allow bursts up to the bucket size at a fixed refill rate; leaky buckets smooth output by delaying. nginx and Envoy document the last two.
-
Фильтры Блума: вероятностная проверка принадлежности множеству без ложноотрицательных ответов
Фильтр Блума с небольшим массивом битов и k хеш-функциями отвечает «точно нет в множестве» или «вероятно, есть». Вероятность ложноположительных ответов настраивается, ложноотрицательные невозможны, удаление не поддерживается. Используйте фильтр, чтобы пропускать поиск отсутствующих ключей, а положительный ответ всегда проверяйте по достоверному источнику данных.
-
Эвристики A*: сохраняйте смысл стоимости перемещения
Выбирайте нижнюю оценку для реального графа движения, правильно обрабатывайте улучшенные маршруты и проверяйте их стоимость поиском без эвристической информации.
-
Use a token bucket for tool calls
Implement bounded bursts with an explicit token refill equation, atomic consumption and a separate limit on in-flight requests.
-
Устойчивость сортировки: что она гарантирует и когда важна
Устойчивая сортировка сохраняет исходный порядок элементов, равных при сравнении. Python гарантирует её, ECMAScript требует её с 2019 года, а Go и GNU sort предлагают отдельно; от неё зависит предсказуемость сортировки по нескольким ключам, таблиц и постраничных запросов.
Машиночитаемо: JSON