Введение
Язык программирования 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 или же напишите в комментариях, что вам нужно и я добавлю в репозиторий
ссылка на оригинал статьи https://habr.com/ru/articles/845086/
Добавить комментарий