Можно долго спорить о том, нужно ли сейчас ботать алгоритмы и структуры данных. Мне кажется, что в любом случае лишним не будет.
В статье по ссылке сравниваются четыре книжки по ряду параметров: стиль изложения, как показан код, много ли математики, количество охватываемых тем и насколько глубоко эти темы рассматриваются. В конце автор приходит к двум книжкам: Introduction to Algorithms и The Algorithm Design Manual. И вот по этому случаю (да простят мне эту маленькую шалость правообладатели) лови PDF-ки к ним.

#book #algorithm #datastructure
https://porgionesanke.wordpress.com/2016/07/11/a-comparison-of-four-algorithms-textbooks/

Ещё от Виталика. Есть такая интересная структура данных: Merkle tree. В посте же речь пойдёт о Verkle tree. Схожая штука, но с гораздо более компактными доказательствами.

#datastructure #crypto #cs

Хороший разбор 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

Иногда возникает необходимость сложить много статических данных в большую read-only мапу на старте приложения. Тут вот такую задачу решали на Go, чтобы получилось эффективнее обычной мапы. Но интерес на самом деле не в самой библиотеке, а в Binary Fuse Filters, на которых это строится (отдельно ещё раз хвалю Now I Get It! сервис C:).

#datastructure #go #library