Тема: Структуры Данных

Статья

Неизменяемость: как работать с данными, ничего не меняя

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

#функциональное программирование#неизменяемость#структуры данных

Статья

Массивы, динамические массивы и строки

От адресной арифметики и кэш-линий до амортизированного append, Go-слайсов, UTF-8 и графемных кластеров — как устроена самая используемая структура данных и где на ней …

#структуры данных#массивы#строки

Статья

Кучи и приоритетные очереди

Как из обычного массива получается структура, которая всегда знает свой минимум: инвариант кучи, sift-up и sift-down, построение за O(n), heapsort, d-арные и Фибоначчиевы …

#структуры данных#кучи#приоритетные очереди

Статья

Как хранят данные: обзор структур данных и зачем их так много

Память — это плоский пронумерованный массив байтов; структуры данных — это способы разложить в нём данные так, чтобы нужные операции были быстрыми. Обзор главных …

#computer science#структуры данных#big-o

Статья

Деревья и бинарные деревья поиска

От определения дерева до продакшн-BST: обходы, инвариант порядка, поиск/вставка/удаление, порядковые запросы, вырождение и почему в реальных библиотеках лежит не BST.

#структуры данных#деревья#бинарные деревья поиска

Статья

Дерево отрезков и дерево Фенвика

Как отвечать на запросы к произвольным отрезкам массива за O(log n), когда массив всё время меняется: биты дерева Фенвика, каноническое разбиение дерева отрезков, …

#структуры данных#деревья#массивы

Статья

Графы: представления, свойства и выбор структуры

Как хранить граф в памяти: список рёбер, матрица и списки смежности, CSR; чем они различаются по времени, памяти и локальности, как извлекать базовые свойства графа и как …

#структуры данных#графы#производительность

Статья

Внутри Git: объекты, blob, tree, commit, ссылки и DAG истории

Git — это не набор команд, а маленькая контентно-адресуемая база данных из четырёх типов объектов и направленный ациклический граф поверх неё; разбираем её по байтам, …

#git#внутреннее устройство#структуры данных

Статья

Вероятностные структуры: Bloom filter, HyperLogLog, Count-Min Sketch

Как обменять точность на память: устройство и математика фильтра Блума, HyperLogLog и Count-Min Sketch, их гарантии ошибок, рабочий код, границы применимости и место в …

#структуры данных#вероятностные структуры#потоковая обработка

Статья

Асимптотика, амортизация и модель памяти: как на самом деле считать стоимость

Строгий разбор O-нотации, трёх методов амортизированного анализа и модели памяти — почему O(1) бывает в сто раз медленнее O(log n) и как считать стоимость структуры …

#структуры данных#асимптотика#амортизация