Хабрахабр

Шпаргалка по структурам данных в 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
Позволяет складывать элементы в любом порядке, а доставать в любой момент времени самый приоритетный из оставшихся. Применяется, например, в алгоритме построения минимального покрывающего дерева, когда на очередном шаге алгоритм выбирает самое короткое ребро из всех, одним концом начинающихся в уже покрытых вершинах.

Interface) в очередь с приоритетом. В стандартной библиотеке есть адаптер, превращающий любой сортируемый контейнер (реализующий sort.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть