Шпаргалка по структурам данных в 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)
    

    Это реализация быстрой сортировки Хоара, нестабильная. Но для участков длины < 12 используется сортировка кучей, в качестве оптимизации.

    func Stable(data Interface)
    

    Внутри это сортирова слиянием, но, в целях эффективности, при достижении рекурсивным алгоритмом блоков меньше 20 элементов используется сортировка вставками.

    Это классические алгоритмы, работающие за O(n log n).

    Если вы дочитали — поздравляю. Знание конкретных API помгает при решении тестовых задач. (Eсли вы работали с чем-то и знаете лучшие альтернативы — пишите в комментариях.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 10

      0
      Но отдельной реализации очереди в стандартной библиотеке нет.

      Каналы (буферизированные) вполне себе очереди. Особенно когда речь идет о взаимодействии двух горутин.
        +1

        Да. Но каналы имеют фиксированный размер. Если в очередь пишет и читает 1 goрутина, как в алгоритме обхода дерева в ширину, например, то появляется возможность deadlock'а. Так что простые очереди тоже нужны.

          +2
          Из канала можно читать и без блокирования + еще можно легко реализовать таймаут через time.After().

          Но согласен — использовать каналы в одной горутине — довольно бессмысленно и порой опасно.

          Однако мой коммент был не про универсальность каналов для всех применений, он был о том, что не стоит так категорично заявлять что очередей нет. Такое вот прочитает новичок и начнет все эти навороты пользовать там где канала — за глаза и за уши хватает.
        +5
        Разработчики, знакомые с Java collections framework не могут смотреть на эти поделки в Go без слез…
          +1
          Тут как на кухне: есть несколько ножей, каждый для своих задач.
          Небольшим ножом для тонкой разделки овощей, большие куски говядины же порционно на стейки нарезать же не будешь? Не будешь.
          • НЛО прилетело и опубликовало эту надпись здесь
              +9
              Справедливости ради, впервые collections framework появился в jdk 1.2 — конец 1998 года, когда джаве было почти три года. В красивом виде, с дженериками и concurrency-коллекциями — в J2SE 5.0, 2004 год (джаве — 8 лет). Go вышел в 2012 — ему 7 лет. Почему бы немного не посравнивать?
                +2
                Неужели концепция языка изменится, и язык вместе со стандартной библиотекой станут дружелюбными к разработчику?
                  +1
                  По сути, сейчас не получится написать типобезопасные обобщенные структуры данных из-за отсутствия в языке дженериков. Когда они в языке появятся, тогда, я думаю, нас ждут интересные времена :)
              +1

              Довольно забавно сравнивать одну только стандартную библиотеку с++ с кучей разрозненных репозиториев на github. Давайте тогда ещё boost и abseil в сравнение включим

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое