news.shamcode.ru | go-collections: структуры данных для Go с поддержкой дженериков

Введение

Язык программирования Go предоставляет базовые контейнеры, но часто разработчикам необходимы более специализированные структуры данных. Пакет go-collections предлагает реализации распространенных структур данных с поддержкой дженериков, что делает код более выразительным и удобным.

В этой статье мы подробно рассмотрим возможности пакета go-collections, его установку и примеры использования различных структур данных.

!В комментариях написали, что нужно упомянуть, что это моя библиотека, иначе я каким-то образом ввожу людей в заблуждение!

1. Установка

Для установки пакета используйте систему модулей Go:

go get github.com/idsulik/go-collections

После установки вы можете импортировать необходимые структуры данных в своем коде.

2. Обзор структур данных

Пакет go-collections предоставляет следующие структуры данных:

Deque (Двухсторонняя очередь)

Описание:

Deque (Double-ended queue) — это структура данных, которая позволяет добавлять и удалять элементы как с начала, так и с конца. Реализована на основе циклического буфера, что позволяет эффективно использовать память и поддерживать амортизированную константную сложность операций.

Конструктор:

func New[T any](initialCapacity int) *Deque[T]

Методы:

PushFront(item T): Добавляет элемент в начало очереди.
PushBack(item T): Добавляет элемент в конец очереди.
PopFront() (T, bool): Удаляет и возвращает элемент из начала очереди.
PopBack() (T, bool): Удаляет и возвращает элемент из конца очереди.
PeekFront() (T, bool): Возвращает элемент из начала очереди без удаления.
PeekBack() (T, bool): Возвращает элемент из конца очереди без удаления.
Len() int: Возвращает количество элементов в очереди.
IsEmpty() bool: Проверяет, пуста ли очередь.
Clear(): Очищает очередь.

Сложность:

Амортизированная сложность: O(1) для всех методов.
Наихудший случай: O(n) при необходимости расширения буфера.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/deque"
)

func main() {
    d := deque.New[int](0)
    d.PushBack(1)
    d.PushFront(2)

    front, _ := d.PopFront()
    back, _ := d.PopBack()

    fmt.Println(front) // Вывод: 2
    fmt.Println(back)  // Вывод: 1
}

Set (Множество)

Описание:

Set — это неупорядоченная структура данных, которая хранит только уникальные значения. Множества обеспечивают быстрый доступ, добавление и удаление элементов, используя хеш-таблицы для управления уникальностью.

Конструктор:

func New[T comparable]() *Set[T]

Методы:

Add(item T): Добавляет элемент в множество.
Remove(item T): Удаляет элемент из множества.
Has(item T) bool: Проверяет наличие элемента.
Clear(): Очищает множество.
Len() int: Возвращает количество элементов.
IsEmpty() bool: Проверяет, пусто ли множество.
Elements() []T: Возвращает срез всех элементов.
AddAll(items ...T): Добавляет несколько элементов.
RemoveAll(items ...T): Удаляет несколько элементов.
Diff(other *Set[T]) *Set[T]: Разница множеств.
Intersect(other *Set[T]) *Set[T]: Пересечение множеств.
Union(other *Set[T]) *Set[T]: Объединение множеств.
IsSubset(other *Set[T]) bool: Проверяет, является ли подмножеством.
IsSuperset(other *Set[T]) bool: Проверяет, является ли надмножеством.
Equal(other *Set[T]) bool: Проверяет равенство множеств.

Сложность:

Сложность для Add, Remove, Has, Len, IsEmpty, AddAll, RemoveAll: O(1) в среднем случае, благодаря хеш-таблицам.
Сложность для Elements: O(n), где n — количество элементов в множестве.
Сложность для операций Diff, Intersect, Union, IsSubset, IsSuperset, Equal: O(n), где n — количество элементов в наибольшем множестве.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/set"
)

func main() {
    s := set.New[int]()
    s.Add(1)
    s.Add(2)
    s.Add(2) // Дубликат не добавится

    fmt.Println(s.Elements()) // Вывод: [1 2]
}

LinkedList (Односвязный список)

Описание:

Односвязный список — это линейная структура данных, в которой элементы связаны последовательно, где каждый элемент (узел) содержит значение и ссылку на следующий элемент. Односвязные списки позволяют добавлять и удалять элементы с начала и конца списка.

Конструктор:

func New[T any]() *LinkedList[T]

Методы:

AddFront(value T): Добавляет элемент в начало списка.
AddBack(value T): Добавляет элемент в конец списка.
RemoveFront() (T, bool): Удаляет и возвращает элемент из начала списка.
RemoveBack() (T, bool): Удаляет и возвращает элемент из конца списка.
Iterate(fn func(T) bool): Итерация по элементам списка.
Size() int: Возвращает размер списка.

Сложность:

Сложность для AddFront, AddBack, RemoveFront, Size: O(1) — операции выполняются за постоянное время, так как не требуют обхода списка.
Сложность для RemoveBack: O(n), где n — количество элементов в списке, поскольку требуется пройти весь список до предпоследнего элемента.
Сложность для Iterate: O(n), где n — количество элементов в списке, так как выполняется обход всех элементов.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/linkedlist"
)

func main() {
    list := linkedlist.New[int]()
    list.AddFront(1)
    list.AddBack(2)

    list.Iterate(func(value int) bool {
        fmt.Println(value)
        return true
    })
    // Вывод:
    // 1
    // 2
}

Queue (Очередь)

Описание:

Очередь — это структура данных типа FIFO (First-In, First-Out), в которой элементы добавляются в конец и удаляются из начала. Очередь обеспечивает базовые операции для управления элементами в порядке их поступления.

Конструктор:

func New[T any](initialCapacity int) *Queue[T]

Методы:

Enqueue(item T): Добавляет элемент в конец очереди.
Dequeue() (T, bool): Удаляет и возвращает элемент из начала очереди.
Peek() (T, bool): Возвращает первый элемент без удаления.
Len() int: Возвращает количество элементов.
IsEmpty() bool: Проверяет, пуста ли очередь.
Clear(): Очищает очередь.

Сложность:

Сложность всех методов: O(1) амортизированная — благодаря использованию двусторонней очереди (Deque), операции выполняются за постоянное время.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/queue"
)

func main() {
    q := queue.New[int](0)
    q.Enqueue(1)
    q.Enqueue(2)

    item, _ := q.Dequeue()
    fmt.Println(item) // Вывод: 1
}

Stack (Стек)

Описание:

Стек — это структура данных типа LIFO (Last-In, First-Out), в которой последний добавленный элемент является первым, который будет удален. Стек поддерживает стандартные операции добавления и удаления элементов с верхушки.

Конструктор:

func New[T any](initialCapacity int) *Stack[T]

Методы:

Push(item T): Добавляет элемент на вершину стека.
Pop() (T, bool): Удаляет и возвращает элемент с вершины стека.
Peek() (T, bool): Возвращает элемент с вершины без удаления.
Len() int: Возвращает количество элементов.
IsEmpty() bool: Проверяет, пуст ли стек.
Clear(): Очищает стек.

Сложность:

Сложность для Push, Pop, Peek, Len, IsEmpty: O(1) — операции выполняются за постоянное время.
Сложность для Clear: O(n), где n — количество элементов в стеке, из-за необходимости обнуления всех ссылок в срезе.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/stack"
)

func main() {
    s := stack.New[int](0)
    s.Push(1)
    s.Push(2)

    item, _ := s.Pop()
    fmt.Println(item) // Вывод: 2
}

Trie (Префиксное дерево)

Описание:

Trie — это префиксное дерево, структура данных, которая поддерживает эффективную вставку и поиск слов и префиксов. Каждый узел дерева представляет символ, и пути в дереве образуют слова.

Конструктор:

func New() *Trie

Методы:

Insert(word string): Добавляет слово в Trie.
Search(word string) bool: Проверяет наличие слова.
StartsWith(prefix string) bool: Проверяет наличие слов с заданным префиксом.

Сложность:

Сложность всех методов: O(m), где m — длина слова или префикса. Операции зависят от длины входной строки, так как необходимо пройти по символам строки.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/trie"
)

func main() {
    t := trie.New()
    t.Insert("hello")
    t.Insert("helium")

    fmt.Println(t.Search("hello"))    // Вывод: true
    fmt.Println(t.StartsWith("he"))   // Вывод: true
    fmt.Println(t.Search("helix"))    // Вывод: false
}

Priority Queue (Приоритетная очередь)

Описание:

Приоритетная очередь — это структура данных, которая позволяет эффективно извлекать и удалять элементы с наивысшим (или наинизшим) приоритетом. Она поддерживает порядок элементов с использованием кучи (heap), что обеспечивает быстрый доступ к элементу с высшим приоритетом.

Конструктор:

func New[T any](less func(a, b T) bool) *PriorityQueue[T]

Параметры:

less: Функция сравнения, определяющая приоритет элементов.

Методы:

Push(item T): Добавляет элемент в очередь.
Pop() (T, bool): Удаляет и возвращает элемент с наивысшим приоритетом.
Peek() (T, bool): Возвращает элемент с наивысшим приоритетом без удаления.
Len() int: Возвращает количество элементов.
IsEmpty() bool: Проверяет, пуста ли очередь.
Clear(): Очищает очередь.

Сложность:

Сложность для Push, Pop: O(log n) — операции выполняются за логарифмическое время благодаря поддержанию свойств кучи при добавлении и удалении элементов.
Сложность для Peek, Len, IsEmpty: O(1) — доступ к верхушке кучи и проверки выполняются за постоянное время.
Сложность для Clear: O(n) — удаление всех элементов требует линейного времени, так как освобождается вся память.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/priorityqueue"
)

func main() {
    pq := priorityqueue.New[int](func(a, b int) bool {
        return a < b // Минимальный элемент имеет наивысший приоритет
    })

    pq.Push(3)
    pq.Push(1)
    pq.Push(2)

    item, _ := pq.Pop()
    fmt.Println(item) // Вывод: 1
}

Binary Search Tree (Двоичное дерево поиска)

Описание:

Двоичное дерево поиска (BST) — это структура данных, поддерживающая элементы в отсортированном порядке, что позволяет эффективно выполнять операции вставки, удаления и поиска. Каждая нода дерева имеет максимум два потомка: левый — для значений меньше текущего, и правый — для значений больше текущего.

Конструктор:

func New[T constraints.Ordered]() *BST[T]

Параметры:

T constraints.Ordered: Тип данных, поддерживающий операции сравнения < и >.

Методы:

Insert(value T): Вставляет значение в дерево.
Remove(value T): Удаляет значение из дерева.
Contains(value T) bool: Проверяет наличие значения.
InOrderTraversal(fn func(T)): Обходит дерево в порядке возрастания.
Len() int: Возвращает количество узлов.
IsEmpty() bool: Проверяет, пусто ли дерево.
Clear(): Очищает дерево.

Сложность:

Сложность для Insert, Contains, Remove: O(h), где h — высота дерева. В худшем случае (несбалансированное дерево) сложность может быть O(n), где n — количество узлов, но в среднем случае для сбалансированных деревьев — O(log n).
Сложность для InOrderTraversal: O(n) — необходимо обойти все узлы.
Сложность для Len, IsEmpty: O(1) — получение текущего размера или проверки выполняются за постоянное время.
Сложность для Clear: O(1) — ссылки на корень и размер просто обнуляются.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/bst"
)

func main() {
    tree := bst.New[int]()
    tree.Insert(2)
    tree.Insert(1)
    tree.Insert(3)

    tree.InOrderTraversal(func(value int) {
        fmt.Println(value)
    })
    // Вывод:
    // 1
    // 2
    // 3
}

Skip List (Список с пропусками)

Описание:

Skip List — это вероятностная структура данных, которая обеспечивает быстрый поиск, вставку и удаление элементов за счет использования нескольких уровней связей, что позволяет пропускать части списка. Skip List является альтернативой сбалансированным деревьям поиска и поддерживает элементы в отсортированном порядке.

Конструктор:

func New[T constraints.Ordered](maxLevel int, p float64) *SkipList[T]

Параметры:

maxLevel: Максимальный уровень списка.
p: Вероятность, определяющая уровень новых узлов (обычно 0.5).

Методы:

Insert(value T): Вставляет значение.
Delete(value T): Удаляет значение.
Search(value T) bool: Ищет значение.
Len() int: Возвращает количество элементов.
IsEmpty() bool: Проверяет, пуст ли список.
Clear(): Очищает список.

Сложность:

Сложность для Insert, Search, Delete: O(log n) в среднем случае — за счет вероятностного распределения уровней узлов и их связей.
Сложность для Len, IsEmpty: O(1) — получение текущего размера или проверка выполняются за постоянное время.
Сложность для Clear: O(1) — обнуляются ссылки на заголовочный узел и счетчики.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/skiplist"
)

func main() {
    sl := skiplist.New[int](16, 0.5)
    sl.Insert(1)
    sl.Insert(2)
    sl.Insert(3)

    fmt.Println(sl.Search(2)) // Вывод: true
    sl.Delete(2)
    fmt.Println(sl.Search(2)) // Вывод: false
}

Graph (Граф)

Описание:

Графы представляют собой сети узлов и ребер, подходящие для различных алгоритмов, таких как поиск путей и построение остовных деревьев.

Конструктор:

func New[T comparable](directed bool) *Graph[T]

Параметры:

directed: Указывает, является ли граф ориентированным.

Методы:

AddNode(value T): Добавляет узел.
AddEdge(from, to T, weight float64): Добавляет ребро с опциональным весом.
RemoveNode(value T): Удаляет узел и связанные ребра.
RemoveEdge(from, to T): Удаляет ребро.
Neighbors(value T) []T: Возвращает соседние узлы.
HasNode(value T) bool: Проверяет наличие узла.
HasEdge(from, to T) bool: Проверяет наличие ребра.
GetEdgeWeight(from, to T) (float64, bool): Получает вес ребра.
Traverse(start T, visit func(T)): Обходит граф от начального узла (BFS).
Nodes() []T: Возвращает все узлы.
Edges() [][2]T: Возвращает все ребра.

Сложность:

Сложность для AddNode, AddEdge, RemoveNode, RemoveEdge: O(1) в среднем случае для операций с узлами и ребрами благодаря использованию хеш-таблиц.
Сложность для Neighbors, HasNode, HasEdge, GetEdgeWeight: O(1) в среднем случае при доступе к элементам через хеш-таблицы.
Сложность для Traverse: O(V + E), где V — количество узлов, E — количество ребер, так как необходимо пройти все узлы и ребра.
Сложность для Nodes, Edges: O(V) и O(E) соответственно, так как требуется собрать все узлы или ребра.

Пример использования:

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/graph"
)

func main() {
    g := graph.New[string](false)
    g.AddNode("A")
    g.AddNode("B")
    g.AddEdge("A", "B", 1.0)

    fmt.Println(g.HasEdge("A", "B")) // Вывод: true
}

3. Практические примеры

Пример 1: Использование Priority Queue для планирования задач

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/priorityqueue"
)

type Task struct {
    name     string
    priority int
}

func main() {
    pq := priorityqueue.New[Task](func(a, b Task) bool {
        return a.priority < b.priority
    })

    pq.Push(Task{"Task1", 3})
    pq.Push(Task{"Task2", 1})
    pq.Push(Task{"Task3", 2})

    for !pq.IsEmpty() {
        task, _ := pq.Pop()
        fmt.Printf("Executing %s with priority %d\n", task.name, task.priority)
    }
    // Вывод:
    // Executing Task2 with priority 1
    // Executing Task3 with priority 2
    // Executing Task1 with priority 3
}

Пример 2: Поиск слов в Trie

package main

import (
    "fmt"
    "github.com/idsulik/go-collections/trie"
)

func main() {
    dictionary := trie.New()
    words := []string{"go", "golang", "gopher", "goroutine"}

    for _, word := range words {
        dictionary.Insert(word)
    }

    fmt.Println(dictionary.Search("golang"))    // Вывод: true
    fmt.Println(dictionary.Search("python"))    // Вывод: false
    fmt.Println(dictionary.StartsWith("go"))    // Вывод: true
}

4. Заключение

Пакет go-collections предоставляет широкий набор структур данных с поддержкой дженериков, что упрощает разработку и повышает производительность приложений на Go. Благодаря понятному API и богатому функционалу, этот пакет становится незаменимым инструментом для разработчиков.

Если у вас есть вопросы или предложения, пишите в комментариях!
Просьба поставить 🌟 для репозитория, если вы думаете, что пакет полезный.

p.s. Если вам нужна какая-то другая структура данных, то можете создать pull request или же напишите в комментариях, что вам нужно и я добавлю в репозиторий