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

K

Kate

Administrator
Команда форума
Введение

Язык программирования 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 и богатому функционалу, этот пакет становится незаменимым инструментом для разработчиков.

habr.com

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

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