Хороший разбор bloom filters. Структура данных, которая даёт за константное время и маленькую память проверить, входит ли значение в множество. Но есть один нюанс: если ответ "не входит", то точно не входит. А вот если ответ "входит", то может быть и false positive. Коллизии, мать их.

#cs #datastructure

Приятный интерактивный разбор того, как работает одна из простых версий CRDT.

#cs #network #datastructure

Хочется закрыть ту серию постов про CRDT. Про сам алгоритм уже по сути не будет. Будет про то, как его прикрутить к игрушечному pixel art редактору, и как разными странными способами сэкономить на размере перегоняемых данных.

#cs #network #datastructure

Slices в Go. Обманчивы, собаки. Как и горутины, к слову. Поначалу кажется, что всё просто. Но это до первого раза, когда всё внезапно сломается. Нужно знать чуть больше про внутреннее устройство, чтобы безопасно использовать. Текущие абстракции, мать их. Пост про подводные камни в гошных динамических массивах.

#go #datastructure

Тут занимаются странным. Строят бинарные деревья и B-деревья в Factorio.

#game #datastructure

Здесь уже знакомый нам автор предлагает попробовать реализовать некоторые завораживающие алгоритмы и структуры данных.

#cs #algorithm #datastructure

Тут какая-то странная история. Как будто челу дали обычную задачку с LeetCode, но не совсем точно передали условия, существенно повысив сложность. А чел взял, да и решил. The problem is to deep copy a linked list where each node references a random list element in addition to usual linkage, короче.

#cs #algorithm #datastructure

Тут в Go соптимизировали мапу, чтобы было быстрее и прикольнее. В посте сначала описывают, за счёт чего оно получилось (вкратце - Swiss Tables - нашли возможность улучшить за счёт параллельных SIMD инструкций и хитрой конструкции), а потом рассказывают, какие сложности были с реализацией этого конкретно в Go (каждая мапа - это на самом деле много мап). Интересно показывает практический подход языка - растим структуру понемногу. А ещё интересно решают проблемы с модификацией мапы во время итерации.

#go #performance #datastructure

Первая часть разбора устройства persistent Clojure vector. Как так получается, что любая манипуляция создаёт новый immutable вектор, но проблем с памятью / производительностью на деле это не создаёт. Разбирается устройство базовых операций: добавить, удалить, поменять элемент по индексу.

#clojure #cs #datastructure

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

#clojure #cs #datastructure