Шпаргалка по структурам данных в 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сли вы работали с чем-то и знаете лучшие альтернативы — пишите в комментариях.)

Let's block ads! (Why?)