Шпаргалка по структурам данных в Go
Некоторые компании проводят собеседования с online написанием кода. Требуется решить олимпиадную задачку на скорость. В таких условиях нет времени посмотреть подробности реализации структур данных — нужно сразу реализовать идею. Но курсы по алгоритмам и структурам данных дают примеры или на псевдокоде, или на С++. Ещё эталонные решения задач написаны зачастую на С++. Готовясь к собеседованию, составил шпаргалку библиотек — аналогов контейнеров STL, что бы не тратить драгоценное время на поиск.
Начнём с очевидного.
Динамический непрерывный массив
Аналог std::vector.
Поддерживает обращение к элементу по индексу за константное время в несколько тактов процессора. Можно увеличить или уменьшить вместительность. Это встроеный slice:
vector := []int{}
Удобно, что базовые концепции встроены в язык.
Cтек
Аналог std::stack.
Упорядоченный набор, в которой добавление новых элементов и удаление существующих производится с одного конца. Первым из стека удаляется элемент, который был помещен туда последним (last-in, first-out — LIFO). Это опять встоенный slice. Из проекта в проект копируются сниппеты:
// Push
stack = append(stack, value)
// Pop
// Проверка, что len(stack) > 0
stack, value = a[:len(stack)-1], a[len(stack)-1]
Oперация среза не аллоцирует новую память.
Очередь
Аналог std::queue и std::deque.
Очереди реализуют операции извлечения и добавления для начала и конца за константное время. Первым из очереди удаляется элемент, который был первым помещен (first-in, first-out — FIFO). Буферизованный канал является очередью на кольцевом буфере, можно использовать его, когда читатель и писатель — разные горутины. Но отдельной реализации очереди в стандартной библиотеке нет. Список awesome-go советует библиотеку https://github.com/gammazero/deque.
import "github.com/gammazero/deque"
Реализуемые операции:
func (q *Deque) PushBack(elem interface{})
func (q *Deque) PushFront(elem interface{})
func (q *Deque) PopBack() interface{}
func (q *Deque) PopFront() interface{}
func (q *Deque) Back() interface{}
func (q *Deque) Front() interface{}
func (q *Deque) At(i int) interface{}
Двусвязный список
Аналог std::list.
Состоит из элементов, содержащих помимо собственных данных ссылки на следующий и предыдущий элемент списка. Он есть в стандартной библиотеке:
import "container/list"
Как и ожидается, поддерживает операции вставки (в начало, в конец, до и после элемента, указатель на который передан) и удаления.
func (l *List) PushBack(v interface{}) *Element
func (l *List) PushFront(v interface{}) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) Remove(e *Element) interface{}
Gо не предоставляет специфического синтаксиса для итераторов. Потому следующий/предыдущий элемент можно получить из указателя на любой узел. Эти методы не протухают после добавления/удаления элемента в список, без неожиданностей.
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
Очередь с приоритетом
Аналог std::priority_queue
Позволяет складывать элементы в любом порядке, а доставать в любой момент времени самый приоритетный из оставшихся. Применяется, например, в алгоритме построения минимального покрывающего дерева, когда на очередном шаге алгоритм выбирает самое короткое ребро из всех, одним концом начинающихся в уже покрытых вершинах.
В стандартной библиотеке есть адаптер, превращающий любой сортируемый контейнер (реализующий sort.Interface) в очередь с приоритетом.
import "container/heap"
Это классическая Двоичная куча. Реализует вставку и удаление за O (log n).
func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}
Хеш таблица
Она же словарь и ассоциативный массив.
Aналог std::unordered_map.
Позволяет добавлять ключ-значение, удалять значение по ключу и проверять наличие элемента за O (1) в среднем. Очевидно, map встроена в язык:
unorderedMap := make(map[string]int)
Результат make (map) является указателем, и способ работы немного отличается от стандартных контейнеров:
// Проверка вхождения:
_, ok := unorderedMap["route"]
// Удаление элемента:
delete(unorderedMap, "route")
// Нахождение длины:
n := len(unorderedMap)
«runtime/map», в отличии от std: unordered_map заботится о программисте — удалять значения во время итерации по ним безопасно.
Множество
Аналог std::unordered_set.
Почти то же самое, что и хеш-таблица, но без сохранения значения.
Если нам нужно только быстрая проверка вхождения, то можно снова использовать встроенный map. Нужно лишь указать пустое значение, что бы указать, что важен только ключ.
var m = make(map[string]struct{})
m["!"] = struct{}{}
_, ok := m["!"] // true
Но эта реализация не поддерживает сложных операторов. Для объединения, пересечения, разности из коробки, понадобятся сторонние библиотеки. Самая используемая, судя по количеству звёзд: https://github.com/deckarep/golang-set
import "github.com/deckarep/golang-set"
Самая нужная часть API:
Add(i interface{}) bool
Remove(i interface{})
Cardinality() int // len()
Contains(i ...interface{}) bool
IsSubset(other Set) bool
Intersect(other Set) Set
Union(other Set) Set
Difference(other Set) Set
SymmetricDifference(other Set) Set
Множество int
В экспериментальной части стандарной библиотеки есть оптимизированное множесво int, экономящее каждый бит.
import "golang.org/x/tools/container/intsets"
Оно также поддерживает объединение, пересечение, разность множеств.
Двоичные деревья поиска
Aналоги std::set и std::map.
Могут показаться новичку плохими аналогами хеш-таблиц:
также поддерживают добавление, удаление и проверку вхождения, но за O (log n).
Но деревья хранят узлы отсортированными по ключу.
В стандартной библиотеке go деревьев нет, широко используется репозиторий, содержащий AVL, Красно-Чёрные и B-деревья.
import "github.com/emirpasic/gods/trees/avltree"
Наиболее употребимые методы API:
func (tree *Tree) Get(key interface{}) (value interface{}, found bool)
func (tree *Tree) Put(key interface{}, value interface{})
func (tree *Tree) Remove(key interface{})
func (tree *Tree) Size() int
func (tree *Tree) Keys() []interface{}
func (tree *Tree) Values() []interface{}
func (tree *Tree) Left() *Node
func (tree *Tree) Right() *Node
Есть два особо важных метода деревев:
func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
возвращает наименьший существующий элемент больще ключа.
func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
возвращает наибольший существующий элемент меньше ключа.
Задачи на это относительно часто попадаются в собеседованиях. В реальной жизни используется в индексах баз данных:
select x from table where x <= $1 limit 1;
При наличии индекса отработает за O (log n), за 1 поиск границы в B-дереве.
Фильтр Блума
А вот этой структуры данных в stl нет.
Как и хеш-таблица, позволяет проверять принадлежность элемента к множеству. Но фильтр не хранит ключи при добавлении, и занимает константное количество памяти. Есть возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное. Используется как фильтр, что бы быстро отсекать почти все не существующие ключи, экономя более дорогую проверку, например читающую с диска или делающую запрос в базу данных.
Есть сторонняя библиотека: https://github.com/willf/bloom
import "github.com/willf/bloom"
Не так часто используется, API можно и подсмотреть.
HyperLogLog
В стандартной библиотеке С++ такого нет.
Вероятностная структура данных. С небольшой ошибкой (≈ 0.4%) считает количество уникальных элементов, не храня сами ключи. Даёт огромную экономию памяти. Если стоит задача быстро посчитать количество посетителей или запросов — HyperLogLog подходит идеально.
Самая популярная библиотека для этого сейчас.
https://github.com/axiomhq/hyperloglog
import "github.com/axiomhq/hyperloglog"
Сортировки
Аналоги std::sort и std::stable_sort.
С потребительской точки зрения есть только 2 принципиально разных типа:
Стабильные (не меняют порядок равных элементов [[4, 0], [1, 2], [1, 1], [5, 6]] --> [[1, 2], [1, 1], [4, 0],[5, 6]])
и не стабильные, не дающие гарантии на последовательность остальных полей.
И то и другое есть в стандартной библиотеке:
func Sort(data Interface)
Это реализация быстрой сортировки Хоара, нестабильная. Но для участков длины
func Stable(data Interface)
Внутри это сортирова слиянием, но, в целях эффективности, при достижении рекурсивным алгоритмом блоков меньше 20 элементов используется сортировка вставками.
Это классические алгоритмы, работающие за O (n log n).
Если вы дочитали — поздравляю. Знание конкретных API помгает при решении тестовых задач. (Eсли вы работали с чем-то и знаете лучшие альтернативы — пишите в комментариях.)
