Hlavní navigace

Knihovny s implementací generických datových typů pro jazyk Go

23. 6. 2022
Doba čtení: 29 minut

Sdílet

 Autor: Go lang
Doposud nejvýznamnější novou vlastností jazyka Go je zavedení podpory pro generické datové typy v Go 1.18. Právě existence generických datových typů umožnila vznik nových knihoven.

Obsah

1. Knihovny s implementací generických datových typů pro programovací jazyk Go

2. Externí knihovna GoDS (Go Data Structures) v původní podobě

3. Ukázka využití původní knihovny GoDS

4. Rozšíření s podporou generických datových typů – Go18DS

5. Generické rozhraní Container a generická funkce Comparator

6. Datová struktura arraylist, jednosměrně a obousměrně vázané seznamy

7. Rozdíly mezi jednotlivými implementacemi seznamů

8. Konstrukce seznamů, přidání prvků do seznamů

9. Typově bezpečné kontejnery

10. Vymazání seznamu, test na existenci prvku, přečtení prvku ze seznamu

11. Vymazání prvku či prvků ze seznamu

12. Operace Swap a Sort

13. Jednosměrně a obousměrně vázané seznamy, iterátor nad seznamy

14. Zásobníky

15. Základní operace nad zásobníky

16. Praktické použití zásobníku – převod aritmetického výrazu do postfixové notace

17. Množiny

18. Eratosthenovo síto

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Knihovny s implementací generických datových typů pro programovací jazyk Go

Pravděpodobně doposud nejvýznamnější novou vlastností programovacího jazyka Go je zavedení podpory pro generické datové typy v Go 1.18, což je vlastnost, kterou jsme se explicitně zabývali v článcích [1], [2] a nepřímo též v [3]. Právě existence generických datových typů umožnila vznik nových knihoven popř. úpravu již existujících knihoven, v nichž jsou implementovány různé datové typy popř. algoritmy pro práci s těmito datovými typy. Právě díky generickým datovým typům je možné obejít poněkud nešikovnou manipulaci s prázdnými rozhraními (interface{}), což je sice užitečný koncept, který ovšem zcela obchází striktní typový systém jazyka Go a nutí programátory k tomu, že aby datovými typy zabývali nikoli v čase překladu (compile time), ale až v čase běhu (runtime time).

Jedná se například o následující knihovny:

  1. Genfuncs
    https://github.com/nwillc/genfuncs
  2. Go18DS
    https://github.com/daichi-m/go18ds
  3. TreeMap v2
    https://github.com/igrmk/treemap
  4. Fp-go
    https://github.com/repeale/fp-go

V dnešním článku i v navazujících článcích si jednotlivé výše zmíněné knihovny postupně popíšeme.

2. Externí knihovna GoDS (Go Data Structures) v původní podobě

Kontejnery (kolekce) nabízené samotným jazykem Go popř. jeho standardní knihovnou nám v praxi většinou nebudou postačovat, takže bude nutné sáhnout po externí knihovně. Těch existuje větší množství, ovšem pravděpodobně nejúplnější sadu kontejnerů nalezneme v knihovně pojmenované GoDS neboli plným jménem Go Data Structures. Tato knihovna vznikla v době, kdy jazyk Go nepodporoval generické datové typy, s čímž souvisí i určité problémy s jejím používáním.

Tato knihovna, jenž je dostupná na adrese https://github.com/emirpasic/gods, přidává do programovacího jazyka Go implementaci mnoha užitečných datových struktur – většinou kontejnerů. Jedná se tedy o takové struktury, jejichž úkolem je uchovat prvky určitých typů a dostupných pod určitým klíčem (celočíselným či obecným):

Kontejner Překlad
List seznam
Set množina
Stack zásobník
Queue fronta
Tree strom
Map mapa

Ovšem vzhledem k tomu, že neexistuje taková implementace těchto datových struktur v podobě, v níž by všechny algoritmy byly realizovány s optimální složitostí, je každá výše zmíněná datová struktura realizována (implementována) hned několikrát, přičemž u každé implementace jsou některé operace optimální a jiné nikoli. Liší se i paměťová náročnost:

Rozhraní Implementace
List ArrayList SinglyLinkedList DoublyLinkedList
Set HashSet TreeSet LinkedHashSet
Stack LinkedListStack ArrayStack
Queue LinkedListQueue ArrayQueue CircularBuffer PriorityQueue
Tree RedBlackTree AVLTree BTree BinaryHeap
Map HashMap TreeMap LinkedHashMap HashBidiMap TreeBidiMap

3. Ukázka využití původní knihovny GoDS

Podívejme se nyní na způsob využití původní knihovny GoDS. Konkrétně se jedná o implementaci jednoduché RPN (Reverse Polish Notation) kalkulačky. Pro realizaci zásobníku je přitom využit kontejner nazvaný arraystack, což je implementace zásobníku realizovaná nad polem (které se v případě potřeby realokuje, což ovšem při použití v jednoduché kalkulačce v naprosté většině případů nebude nutné). Povšimněte si triku u příkazu import, v níž se na arraystack budeme odkazovat přes obecnější alias stack:

package main
 
import (
        "fmt"
        stack "github.com/emirpasic/gods/stacks/arraystack"
        "strconv"
        "strings"
)
 
func printStack(s *stack.Stack) {
        it := s.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3d ", value)
        }
        println()
}
 
func main() {
        expression := "1 2 + 2 3 * 8 + *"
        terms := strings.Split(expression, " ")
        stack := stack.New()
 
        for _, term := range terms {
                switch term {
                case "+":
                        operand1, _ := stack.Pop()
                        operand2, _ := stack.Pop()
                        stack.Push(operand1.(int) + operand2.(int))
                        print("+ :\t")
                        printStack(stack)
                case "-":
                        operand1, _ := stack.Pop()
                        operand2, _ := stack.Pop()
                        stack.Push(operand2.(int) - operand1.(int))
                        print("- :\t")
                        printStack(stack)
                case "*":
                        operand1, _ := stack.Pop()
                        operand2, _ := stack.Pop()
                        stack.Push(operand1.(int) * operand2.(int))
                        print("* :\t")
                        printStack(stack)
                case "/":
                        operand1, _ := stack.Pop()
                        operand2, _ := stack.Pop()
                        stack.Push(operand2.(int) / operand1.(int))
                        print("/ :\t")
                        printStack(stack)
                default:
                        number, err := strconv.Atoi(term)
                        if err == nil {
                                stack.Push(number)
                        }
                        fmt.Printf("%-2d:\t", number)
                        printStack(stack)
                }
        }
        print("Result: ")
        printStack(stack)
}

Při spuštění tohoto příkladu se bude postupně vypisovat obsah zásobníku operandů:

1 :       1
2 :       2   1
+ :       3
2 :       2   3
3 :       3   2   3
* :       6   3
8 :       8   6   3
+ :      14   3
* :      42
Result:  42

Program je sice relativně dobře čitelný, ovšem nepříjemný je zejména fakt, že je nutné explicitně kontrolovat typy prvků vyzvedávaných ze zásobníku operací Pop resp. Peek. Původní knihovna GoDS totiž nepodporuje generické datové typy a proto jsou všechny prvky typu „prázdné rozhraní“ neboli interface{}:

Rozhraní pro všechny implementace seznamů:

type List interface {
        Get(index int) (interface{}, bool)
        Remove(index int)
        Add(values ...interface{})
        Contains(values ...interface{}) bool
        Sort(comparator utils.Comparator)
        Swap(index1, index2 int)
        Insert(index int, values ...interface{})
        Set(index int, value interface{})
 
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
}

Rozhraní pro všechny implementace množin:

type Set interface {
        Add(elements ...interface{})
        Remove(elements ...interface{})
        Contains(elements ...interface{}) bool
        Intersection(another *Set) *Set
        Union(another *Set) *Set
        Difference(another *Set) *Set
 
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
}

Rozhraní pro obě implementace zásobníků:

type Stack interface {
        Push(value interface{})
        Pop() (value interface{}, ok bool)
        Peek() (value interface{}, ok bool)
 
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
        containers.Container
}

Rozhraní pro všechny implementace map:

type Map interface {
        Put(key interface{}, value interface{})
        Get(key interface{}) (value interface{}, found bool)
        Remove(key interface{})
        Keys() []interface{}
 
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
        containers.Container
}

Rozhraní pro všechny implementace stromů:

type Tree interface {
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
        containers.Container
}

Rozhraní pro všechny implementace front:

type Queue interface {
        Enqueue(value interface{})
        Dequeue() (value interface{}, ok bool)
        Peek() (value interface{}, ok bool)
 
        containers.Container
        Empty() bool
        Size() int
        Clear()
        Values() []interface{}
        String() string
        containers.Container
}

4. Rozšíření s podporou generických datových typů – Go18DS

Na základě výše zmíněné knihovny GoDS byla vytvořena knihovna nazvaná Go18DS, tedy „generické datové struktury pro Go 1.18 a novější“. Pro její instalaci postačuje vytvoření souboru go.mod a přidání jednoho řádku do tohoto souboru:

module x
 
go 1.18
 
require github.com/daichi-m/go18ds v1.12.1 // indirect

V souboru go.sum se po překladu vytvoří tyto informace o závislostech:

github.com/daichi-m/go18ds v1.12.1 h1:Pjc3IApmN4qtDiovGP9MvMpIzgZle3SHUcNaA5j46bg=
github.com/daichi-m/go18ds v1.12.1/go.mod h1:wc2dURUr8aMxxC4Mn5ObJGVM7uIKU8JagY4nhtonXq8=

A poté se nainstalují následující balíčky (tedy z pohledu programátorů jmenné prostory):

github.com/daichi-m/go18ds/containers
github.com/daichi-m/go18ds/examples/arraylist
github.com/daichi-m/go18ds/examples/arraystack
github.com/daichi-m/go18ds/examples/avltree
github.com/daichi-m/go18ds/examples/binaryheap
github.com/daichi-m/go18ds/examples/btree
github.com/daichi-m/go18ds/examples/customcomparator
github.com/daichi-m/go18ds/examples/doublylinkedlist
github.com/daichi-m/go18ds/examples/enumerablewithindex
github.com/daichi-m/go18ds/examples/enumerablewithkey
github.com/daichi-m/go18ds/examples/godsort
github.com/daichi-m/go18ds/examples/hashbidimap
github.com/daichi-m/go18ds/examples/hashmap
github.com/daichi-m/go18ds/examples/hashset
github.com/daichi-m/go18ds/examples/iteratorwithindex
github.com/daichi-m/go18ds/examples/iteratorwithkey
github.com/daichi-m/go18ds/examples/linkedhashmap
github.com/daichi-m/go18ds/examples/linkedhashset
github.com/daichi-m/go18ds/examples/linkedliststack
github.com/daichi-m/go18ds/examples/redblacktree
github.com/daichi-m/go18ds/examples/redblacktreeextended
github.com/daichi-m/go18ds/examples/serialization
github.com/daichi-m/go18ds/examples/singlylinkedlist
github.com/daichi-m/go18ds/examples/treebidimap
github.com/daichi-m/go18ds/examples/treemap
github.com/daichi-m/go18ds/examples/treeset
github.com/daichi-m/go18ds/lists
github.com/daichi-m/go18ds/lists/arraylist
github.com/daichi-m/go18ds/lists/doublylinkedlist
github.com/daichi-m/go18ds/lists/singlylinkedlist
github.com/daichi-m/go18ds/maps
github.com/daichi-m/go18ds/maps/hashbidimap
github.com/daichi-m/go18ds/maps/hashmap
github.com/daichi-m/go18ds/maps/linkedhashmap
github.com/daichi-m/go18ds/maps/treebidimap
github.com/daichi-m/go18ds/maps/treemap
github.com/daichi-m/go18ds/sets
github.com/daichi-m/go18ds/sets/hashset
github.com/daichi-m/go18ds/sets/linkedhashset
github.com/daichi-m/go18ds/sets/treeset
github.com/daichi-m/go18ds/stacks
github.com/daichi-m/go18ds/stacks/arraystack
github.com/daichi-m/go18ds/stacks/linkedliststack
github.com/daichi-m/go18ds/trees
github.com/daichi-m/go18ds/trees/avltree
github.com/daichi-m/go18ds/trees/binaryheap
github.com/daichi-m/go18ds/trees/btree
github.com/daichi-m/go18ds/trees/redblacktree
github.com/daichi-m/go18ds/utils

5. Generické rozhraní Container a generická funkce Comparator

Všechny datové struktury definované v knihovně Go18DS jsou založeny na rozhraní nazvaném Container, které (přesněji řečeno jeho veřejná část) vypadá následovně:

type Container[T any] interface {
    Empty() bool
    Size() int
    Clear()
    Values() []T
}
Poznámka: vidíte tedy, že lze zjistit, zda je libovolný kontejner prázdný, jakou má velikost (kolik obsahuje prvků), odstranit všechny prvky a získat všechny prvky ve formě řezu (slice).

Dalším důležitým typem definovaným v knihovně Go18DS je typ Comparator s předpisem funkce určené pro porovnání dvou hodnot. Konkrétní implementace komparátoru se používá například při řazení prvků atd.:

type Comparator func[T comparable](a, b T) int

V knihovně Go18DS taktéž nalezneme tři konkrétní implementace komparátorů, jejichž význam je patrný z hlaviček jejich funkcí:

func StringComparator(a, b string) int
 
func NumberComparator[T Number](a, b T) int
 
func TimeComparator(a, b interface{}) int

6. Datová struktura arraylist, jednosměrně a obousměrně vázané seznamy

Prvním kontejnerem, jímž se budeme v dnešním článku zabývat, je seznam neboli list. Všechny dostupné implementace seznamů splňují (satisfy) generické rozhraní nazvané jednoduše List, které vypadá takto:

type List[T comparable] interface {
    Get(index int) (T, bool)
    Remove(index int)
    Add(values ...T)
    Contains(values ...T) bool
    Sort(comparator utils.Comparator[T])
    Swap(index1, index2 int)
    Insert(index int, values ...T)
    Set(index int, value T)
}
Poznámka: současně všechny seznamy splňují i výše zmíněné rozhraní Container.

Seznamy popsané rozhraním nazvaným List existují v knihovně Go18DS ve třech implementacích:

  1. ArrayList: seznam postavený nad polem, které se může realokovat, pokud počet prvků překročí kapacitu pole
  2. SinglyLinkedList: lineárně jednosměrně vázaný seznam
  3. DoublyLinkedList: obousměrně vázaný seznam

U všech seznamů máme k dispozici iterátor (List.Iterator), který se používá takto:

iterator := list.Iterator()
for iterator.Next() {
        index, value := iterator.Index(), iterator.Value()
        fmt.Printf("item #%d == %s\n", index, value)
}
Poznámka: samozřejmě pokud nepotřebujeme znát index (pořadí) prvku, můžeme vynechat volání iterator.Index().

7. Rozdíly mezi jednotlivými implementacemi seznamů

Jednotlivé implementace seznamů se od sebe pochopitelně liší jak svoji vnitřní strukturou, tak i odlišnou časovou složitostí některých operací. Rozdíly v časové složitosti jsou naznačeny v následující tabulce:

Implementace Přístup k prvku Insert Append Iterace vpřed Iterace vzad
ArrayList O(1) O(n) O(1)-O(n) O(1) O(1)
SinglyLinkedList O(n) O(1) O(n) O(1) O(n)
DoublyLinkedList O(n) O(1) O(1) O(1) O(1)
Poznámka: operace pro smazání prvku budou mít podobné složitosti jako operace typu Insert a Append.

8. Konstrukce seznamů, přidání prvků do seznamů

Podívejme se nyní na způsob vytvoření nového seznamu s vložením prvků do seznamu přímo v konstruktoru:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]("a", "b", "c")
        fmt.Println(l)
}

Výsledek:

ArrayList
a, b, c
Poznámka: seznam se tedy vypíše na dva řádky – nejprve jeho typ a posléze i hodnoty jeho prvků.

Na konec seznamu lze nové prvky vkládat metodou Add. Povšimněte si, že je možné jediným zavoláním Add do seznamu vložit i větší množství prvků (díky deklaraci s …):

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]("a", "b", "c")
        fmt.Println(l)
 
        l.Add("a")
        fmt.Println(l)
 
        l.Add("b", "c")
        fmt.Println(l)
}

Tentokrát s výsledkem:

ArrayList
a, b, c
ArrayList
a, b, c, a
ArrayList
a, b, c, a, b, c

9. Typově bezpečné kontejnery

Díky tomu, že všechny kontejnery v knihovně Go18DS jsou vytvořeny na základě generických datových typů, jedná se o typově zabezpečené kontejnery, které například nedovolí, aby se do seznamu určeného pro uchovávání řetězců vložila celá čísla:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string](1, 2, 3)
        fmt.Println(l)
}

Tato chyba je detekována již při pokusu o překlad programu:

$ go run arraylist03.go
 
# command-line-arguments
./arraylist03.go:10:29: cannot use 1 (untyped int constant) as string value in argument to arraylist.New[string]
./arraylist03.go:10:32: cannot use 2 (untyped int constant) as string value in argument to arraylist.New[string]
./arraylist03.go:10:35: cannot use 3 (untyped int constant) as string value in argument to arraylist.New[string]

Totéž platí i při pokusu o přidání nových prvků do již zkonstruovaného seznamu:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]("a", "b", "c")
        fmt.Println(l)
 
        l.Add(1)
        fmt.Println(l)
 
        l.Add(2, 3)
        fmt.Println(l)
}

S výsledkem:

$ go run arraylist04.go
 
# command-line-arguments
./arraylist04.go:13:8: cannot use 1 (untyped int constant) as string value in argument to l.Add
./arraylist04.go:16:8: cannot use 2 (untyped int constant) as string value in argument to l.Add
./arraylist04.go:16:11: cannot use 3 (untyped int constant) as string value in argument to l.Add

10. Vymazání seznamu, test na existenci prvku, přečtení prvku ze seznamu

Jak je již z pohledu na metody předepsané v rozhraních Container a List patrné, je možné se seznamy (resp. přesněji řečeno s jejich prvky) provádět i další operace. Pro vymazání všech prvků se používá metoda Clear:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]()
        fmt.Println(l)
 
        l.Add("a")
        fmt.Println(l)
 
        l.Add("b", "c")
        fmt.Println(l)
 
        l.Clear()
        fmt.Println(l)
}

Výsledky:

ArrayList
 
ArrayList
a
ArrayList
a, b, c
ArrayList
 

Test, zda seznam obsahuje prvek s určitou hodnotou, je implementován v metodě Contains, což si opět vyzkoušíme:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func testContains(l *arraylist.List[string]) {
        fmt.Println("List:", l)
        for _, c := range []string{"a", "b", "c", "x"} {
                fmt.Printf("Contains '%s': %t\n", c, l.Contains(c))
        }
        fmt.Println()
}
 
func main() {
        l := arraylist.New[string]()
        testContains(l)
 
        l.Add("a")
        testContains(l)
 
        l.Add("b", "c")
        testContains(l)
 
        l.Clear()
        testContains(l)
}

Výsledky:

List: ArrayList
 
Contains 'a': false
Contains 'b': false
Contains 'c': false
Contains 'x': false
 
List: ArrayList
a
Contains 'a': true
Contains 'b': false
Contains 'c': false
Contains 'x': false
 
List: ArrayList
a, b, c
Contains 'a': true
Contains 'b': true
Contains 'c': true
Contains 'x': false
 
List: ArrayList
 
Contains 'a': false
Contains 'b': false
Contains 'c': false
Contains 'x': false

Naproti tomu slouží metoda pojmenovaná Get pro přečtení prvku s daným indexem ze seznamu. Navíc se vrací i příznak, zda byl prvek nalezen či nikoli (lze tedy bez pádu překročit meze dané počtem prvků v seznamech):

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func testGet(l *arraylist.List[string]) {
        fmt.Println("List:", l)
 
        for i := -1; i < l.Size()+1; i++ {
                value, found := l.Get(i)
                if found {
                        fmt.Printf("Item %d = '%s'\n", i, value)
                } else {
                        fmt.Printf("Item %d not found\n", i)
                }
        }
        fmt.Println()
}
 
func main() {
        l := arraylist.New[string]()
        testGet(l)
 
        l.Add("a")
        testGet(l)
 
        l.Add("b", "c")
        testGet(l)
 
        l.Clear()
        testGet(l)
}

S výsledky:

List: ArrayList
 
Item -1 not found
Item 0 not found
 
List: ArrayList
a
Item -1 not found
Item 0 = 'a'
Item 1 not found
 
List: ArrayList
a, b, c
Item -1 not found
Item 0 = 'a'
Item 1 = 'b'
Item 2 = 'c'
Item 3 not found
 
List: ArrayList
 
Item -1 not found
Item 0 not found

11. Vymazání prvku či prvků ze seznamu

Vymazání prvku ze seznamu zajišťuje metoda nazvaná Remove. Zajímavé je, že je možné se pokusit o vymazání neexistujících prvků, a to bez vyvolání chyby. Ostatně to je ukázáno i v následujícím příkladu, kde evidentně voláme Remove s nekorektními indexy:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]()
        fmt.Println(l)
 
        l.Add("a")
        fmt.Println(l)
 
        l.Add("b", "c")
        fmt.Println(l)
 
        for i := 0; i < 5; i++ {
                l.Remove(0)
                fmt.Println(l)
        }
}

S výsledky:

ArrayList
 
ArrayList
a
ArrayList
a, b, c
ArrayList
b, c
ArrayList
c
ArrayList
 
ArrayList
 
ArrayList
 

12. Operace Swap a Sort

Mezi další zajímavé operace prováděné nad seznamy patří zejména operace Swap zajišťující prohození dvou prvků seznamu. Jedná se obecně o velmi efektivní operaci, která je navíc interně použita i operací nazvanou Sort určenou pro seřazení prvků v seznamu na základě zadaného kritéria – to je reprezentováno komparátorem, tedy funkcí, která porovná dva prvky a vrátí informaci o tom, který z prvků je „větší“ a zda si nejsou oba prvky rovny.

Opět platí, že operaci Swap lze zavolat i s neexistujícím indexem prvku:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
)
 
func main() {
        l := arraylist.New[string]("foo", "bar", "baz")
        fmt.Println(l)
        fmt.Println()
 
        l.Swap(0, 1)
        fmt.Println(l)
        fmt.Println()
 
        l.Swap(1, 2)
        fmt.Println(l)
        fmt.Println()
 
        l.Swap(2, 3)
        fmt.Println(l)
        fmt.Println()
}

S výsledky:

ArrayList
foo, bar, baz
 
ArrayList
bar, foo, baz
 
ArrayList
bar, baz, foo
 
ArrayList
bar, baz, foo

V dalším demonstračním příkladu je ukázáno, jak lze seřadit prvky – řetězce v seznamu (správného typu). Použijeme přitom standardně dodávaný StringComparator:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/arraylist"
        "github.com/daichi-m/go18ds/utils"
)
 
func main() {
        l := arraylist.New[string]("zoo", "aleph", "foo", "bar", "baz")
        fmt.Println(l)
        fmt.Println()
 
        l.Sort(utils.StringComparator)
        fmt.Println(l)
}

Původní i seřazený seznam vypadá takto:

ArrayList
zoo, aleph, foo, bar, baz
 
ArrayList
aleph, bar, baz, foo, zoo

13. Jednosměrně a obousměrně vázané seznamy, iterátor nad seznamy

Všechny operace, které byly popsány v předchozích kapitolách, je možné využít i pro jednosměrně popř. obousměrně vázané seznamy, které se od sebe odlišují, jak již víme, interním způsobem uložení prvků a taktéž odlišnými časovými složitostmi některých operací. Ukázky práce se seznamy různých typů naleznete v demonstračních příkladech zmíněných v devatenácté kapitole.

Podívejme se nyní na způsob procházení všemi prvky seznamu s využitím iterátoru. Pro jednoduchost budeme pracovat se seznamem, do kterého se ukládají řetězce, ovšem naprosto stejný způsob bude možné použít i pro seznamy s prvky jiných typů:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/lists/singlylinkedlist"
)
 
func main() {
        l := singlylinkedlist.New[string]("zoo", "aleph", "foo", "bar", "baz")
 
        it := l.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3s \t %T\n", value, value)
        }

}

Tento příklad po svém spuštění vypíše všechny prvky získané ze seznamu, včetně jejich typů:

zoo      string
aleph    string
foo      string
bar      string
baz      string

14. Zásobníky

Dalším užitečným typem kontejneru, s nímž se v knihovně Go18DS setkáme, jsou seznamy neboli stack(s). Všechny dostupné implementace seznamu jsou založeny na rozhraní se jménem Stack:

type Stack[T comparable] interface {
    Push(value T)
    Pop() (value T, ok bool)
    Peek() (value T, ok bool)
}

Existují přitom dvě konkrétní implementace zásobníků – LinkedListStack a ArrayStack, které se od sebe odlišují tím, jakým způsobem jsou jednotlivé prvky na zásobníku uloženy a jak může zásobník růst nebo se naopak zmenšovat – což je v případě interního použití jednosměrně vázaného seznamu rychlejší operace, kterou je však možné v případě využití polí poměrně dobře amortizovat.

15. Základní operace nad zásobníky

V této kapitole si na několika příkladech ukážeme provedení základních operací nad zásobníky. Základem je operace push určená pro vložení nového prvku na vrchol zásobníku (TOS=Top Of Stack):

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/stacks/arraystack"
)
 
func main() {
        stack := arraystack.New[string]()
        fmt.Println(stack)
 
        stack.Push("foo")
        fmt.Println(stack)
 
        stack.Push("bar")
        fmt.Println(stack)
 
        stack.Push("baz")
        fmt.Println(stack)
}

Výsledky získané po spuštění tohoto programu:

ArrayStack
 
ArrayStack
foo
ArrayStack
foo, bar
ArrayStack
foo, bar, baz

Pro přečtení prvku z vrcholu zásobníku společně s odstraněním tohoto prvku ze zásobníku slouží operace Pop. Ta současně vrací příznak, zda není zásobník prázdný:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/stacks/arraystack"
)
 
func main() {
        stack := arraystack.New[string]()
        stack.Push("foo")
        stack.Push("bar")
        stack.Push("baz")
 
        for {
                value, exists := stack.Pop()
                if exists {
                        fmt.Println(value)
                } else {
                        break
                }
        }
}

Výsledky získané po spuštění tohoto programu:

baz
bar
foo
Poznámka: prvky jsou tedy vypsané v opačném pořadí, než v jakém byly na zásobník uloženy.

Naproti tomu operace Peek pouze přečte obsah prvku na vrcholu zásobníku bez odstranění tohoto prvku. Současně tato metoda vrací příznak, zda není zásobník prázdný:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/stacks/arraystack"
)
 
func main() {
        stack := arraystack.New[string]()
        stack.Push("foo")
        stack.Push("bar")
        stack.Push("baz")
 
        for i := 0; i < 10; i++ {
                value, exists := stack.Peek()
                fmt.Println(i, value, exists)
                stack.Pop()
        }
}

Výsledky získané po spuštění tohoto programu:

0 baz true
1 bar true
2 foo true
3  false
4  false
5  false
6  false
7  false
8  false
9  false

Použít můžeme i metody Size() a Empty() pro zjištění počtu prvků uložených na zásobníku a pro zjištění, zda je zásobník prázdný či nikoli:

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/stacks/arraystack"
)
 
func main() {
        stack := arraystack.New[string]()
        stack.Push("foo")
        stack.Push("bar")
        stack.Push("baz")
 
        for {
                value, exists := stack.Pop()
                if exists {
                        fmt.Println(value, stack.Size(), stack.Empty())
                } else {
                        break
                }
        }
}

Výsledky získané po spuštění tohoto programu:

baz 2 false
bar 1 false
foo 0 true

16. Praktické použití zásobníku – převod aritmetického výrazu do postfixové notace

Podívejme se nyní, jakým způsobem je možné převést aritmetický výraz odpovídající syntaxi programovacího jazyka Go do postfixové notace. Samotný algoritmus převodu mezi běžnou infixovou notací a notací postfixovou navrhl E. Dijkstra a nazývá se algoritmus shunting-yard (česky snad seřaďovací nádraží, konkrétně by se jednalo o nádraží vybavené úvratí). Tento algoritmus je založen na postupném načítání tokenů reprezentujících jak aritmetické/logické operace, tak i jejich operandy a popř. i volání funkcí a závorky ovlivňující prioritu prováděných operací. Tyto tokeny jsou v případě operandů posílány přímo na výstup, ovšem tokeny reprezentující operandy, závorky a funkce jsou zpracovávány odlišně – buď jsou odloženy na zásobník (jehož reálnou obdobou je právě úvrať na seřaďovacím nádraží) nebo naopak zajistí postupné vyzvedávání starších operandů z tohoto zásobníku a jejich poslání na výstup. Úplný popis tohoto algoritmu, který naleznete například zde, obsahuje i rozlišení operátorů asociativních zleva a zprava.

Poznámka: důležitá je zde zmínka o tom, že tento algoritmus pracuje nad sekvencí tokenů. Není tedy nutné vůbec konstruovat AST a dokonce se tokeny ze sekvence vždy pouze načítají, nikdy nevrací (naopak některé jiné algoritmy mohou vyžadovat vrácení posledního tokenu do vstupní sekvence).

Výše popsaný algoritmus shunting-yard můžeme zjednodušit v případě, že není nutné rozlišit mezi použitím operátorů asociativních zleva a zprava. Příkladem je opět programovací jazyk Go, který v sadě základních aritmetických operátorů má pouze operátory asociativní zleva (není zde například operátor pro umocnění atd.). Navíc může algoritmus pracovat přímo nad tokeny získanými již v tomto seriálu popsanou tokenizací – tedy výsledkem práce balíčku nazvaného go/scanner (a jak již víme: bez vracení tokenů). Jedna z možných implementací algoritmu shunting-yard tedy může vypadat následovně. Všechny části jsou poměrně dopodrobna okomentovány:

package main
 
import (
        "fmt"
 
        "go/scanner"
        "go/token"
 
        "github.com/daichi-m/go18ds/stacks/arraystack"
)
 
// výraz, který se má převést na RPN
const source = `
1 + 2 * (3 + x) + y * (z - 1)
`
 
func printStack(s *arraystack.Stack[token.Token]) {
        it := s.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%s ", value)
        }
        fmt.Println()
}
 
func toRPN(s scanner.Scanner) {
        var operators = map[token.Token]int{
                token.MUL: 2,
                token.QUO: 2,
                token.REM: 2,
                token.ADD: 1,
                token.SUB: 1,
        }
 
        stack := arraystack.New[token.Token]()
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, lit := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo vypsat
                        fallthrough
                case token.FLOAT:
                        // číslo s plovoucí čárkou přímo vypsat
                        fallthrough
                case token.IDENT:
                        // identifikátor taktéž přímo vypsat
                        fmt.Printf("%v ", lit)
                case token.LPAREN:
                        // levá závorka se uloží na zásobník (bez výpisu)
                        stack.Push(tok)
                case token.RPAREN:
                        // pravá závorka zahájí zpracování zásobníku až do první nalezené levé závorky
                        var tok token.Token
                        for {
                                // přečtení prvku ze zásobníku - operace POP
                                tok, _ = stack.Pop()
                                if tok == token.LPAREN {
                                        // odstranění levé závorky
                                        break
                                }
                                // ostatní tokeny získané ze zásobníku se vypíšou
                                fmt.Printf("%v ", tok)
                        }
                case token.EOF:
                        // speciální token reprezentující konec tokenizace
                        break loop
                default:
                        priority1, isOperator := operators[tok]
                        if isOperator {
                                // průchod prvky na zásobníku
                                for !stack.Empty() {
                                        // operace TOP
                                        tok, _ := stack.Peek()
                                        // získat prioritu operátoru přečteného ze zásobníku
                                        priority2 := operators[tok]
 
                                        if priority1 > priority2 {
                                                // větší priorita nového operátoru -> konec
                                                // (pouze ho později uložíme na zásobník)
                                                break
                                        }
 
                                        // menší či stejná priorita nového operátoru ->
                                        // vypsat předchozí operátor nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack.Pop()
                                        fmt.Printf("%s ", tok)
                                }
 
                                // uložit nově načtený operátor na zásobník
                                stack.Push(tok)
                        }
                }
        }
        // tisk obsahu zásobníku
        printStack(stack)
}
 
func main() {
        // objekt představující scanner
        var s scanner.Scanner
 
        // struktura reprezentující množinu zdrojových kódů
        fset := token.NewFileSet()
 
        // přidání informace o zdrojovém kódu
        file := fset.AddFile("", fset.Base(), len(source))
 
        // inicializace scanneru
        s.Init(file, []byte(source), nil, scanner.ScanComments)
 
        // převod výrazu do RPN
        toRPN(s)
}

Po spuštění tohoto demonstračního příkladu se zobrazí informace o postupně zpracovávaném tokenu i o obsahu zásobníku operandů:

1 :       1
2 :       2   1
+ :       3
2 :       2   3
3 :       3   2   3
* :       6   3
8 :       8   6   3
+ :      14   3
* :      42
Result:  42

17. Množiny

Další často používanou generickou datovou strukturou jsou množiny představované rozhraním Set:

type Set[T comparable] interface {
    Add(elements ...T)
    Remove(elements ...T)
    Contains(elements ...T) bool
}

Pro toto rozhraní existují tři implementace:

  1. HashSet: založeno na hešovacích tabulkách
  2. TreeSet: založeno na RB-stromech
  3. LinkedHashSet: zachovává pořadí prvků

Jednoduchý příklad použití množin je ukázán v navazující kapitole.

18. Eratosthenovo síto

Jako příklad praktičtějšího použití množin jsem vybral známý algoritmus určený pro hledání prvočísel s využitím Eratosthenova síta. Samozřejmě existuje mnoho více či méně optimalizovaných implementací tohoto algoritmu; některé jsou zmíněny na stránce Rosetta Code. My si ukážeme tu nejprimitivnější implementaci spočívající v postupném odstraňování celočíselných násobků prvočísel z množiny, která původně obsahovala všechna celá čísla od 2 do 1000.

Poznámka: z hlediska paměťové složitosti by bylo lepší použít bitový vektor implementovaný například balíčkem bitarray. Zde se nám ale jedná pouze o ukázání základních operací s množinami.

Zdrojový kód implementace Eratosthenova síta postavený na množinách podporovaných knihovnou Go18DS vypadá následovně:

Linux tip

package main
 
import (
        "fmt"
 
        "github.com/daichi-m/go18ds/sets/linkedhashset"
)
 
const maxPrime = 1000
 
func printSet(set *linkedhashset.Set[int]) {
        iterator := set.Iterator()
        for iterator.Next() {
                index, value := iterator.Index(), iterator.Value()
                fmt.Printf("%3d ", value)
                if index%10 == 9 {
                        fmt.Println()
                }
        }
        fmt.Println()
}
 
func main() {
        primes := linkedhashset.New[int]()
        for n := 2; n < maxPrime; n++ {
                primes.Add(n)
        }
 
        for n := 2; n < maxPrime/2; n++ {
                if primes.Contains(n) {
                        for k := 2 * n; k < maxPrime; k += n {
                                primes.Remove(k)
                        }
                }
        }
        printSet(primes)
}

Tento příklad by měl po svém spuštění vypsat všechna prvočísla nalezená v intervalu 0 až 1000:

  2   3   5   7  11  13  17  19  23  29
 31  37  41  43  47  53  59  61  67  71
 73  79  83  89  97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997

19. Repositář s demonstračními příklady

Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/go-root (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně stovku kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady, které naleznete v následující tabulce:

# Příklad/soubor Stručný popis Cesta
1 arraylist01.go konstrukce seznamu s přidáním prvků pro seznam typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist01.go
2 arraylist02.go přidání nových prvků do seznamu metodou Add pro seznam typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist02.go
3 arraylist03.go pokus o přidání prvků odlišného datového typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist03.go
4 arraylist04.go pokus o přidání prvků odlišného datového typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist04.go
5 arraylist05.go vymazání všech prvků ze seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist05.go
6 arraylist06.go test na existenci prvků v seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist06.go
7 arraylist07.go přečtení prvků se zadaným indexem ze seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist07.go
8 arraylist08.go odstranění prvků se zadaným indexem ze seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist08.go
9 arraylist09.go operace Swap – prohození dvou prvků v seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist09.go
10 arraylist10.go operace Sort – setřídění prvků v seznamu typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist10.go
11 arraylist11.go implementace iterátoru nad seznamem typu arraylist https://github.com/tisnik/go-root/blob/master/article92/a­rraylist11.go
       
12 singlylinkedlist01.go konstrukce seznamu s přidáním prvků pro seznam typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist01.go
13 singlylinkedlist02.go přidání nových prvků do seznamu metodou Add pro seznam typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist02.go
14 singlylinkedlist03.go pokus o přidání prvků odlišného datového typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist03.go
15 singlylinkedlist04.go pokus o přidání prvků odlišného datového typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist04.go
16 singlylinkedlist05.go vymazání všech prvků ze seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist05.go
17 singlylinkedlist06.go test na existenci prvků v seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist06.go
18 singlylinkedlist07.go přečtení prvků se zadaným indexem ze seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist07.go
19 singlylinkedlist08.go odstranění prvků se zadaným indexem ze seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist08.go
20 singlylinkedlist09.go operace Swap – prohození dvou prvků v seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist09.go
21 singlylinkedlist10.go operace Sort – setřídění prvků v seznamu typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist10.go
22 singlylinkedlist11.go implementace iterátoru nad seznamem typu singlylinkedlist https://github.com/tisnik/go-root/blob/master/article92/sin­glylinkedlist11.go
       
23 doublylinkedlist01.go konstrukce seznamu s přidáním prvků pro seznam typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist01.go
24 doublylinkedlist02.go přidání nových prvků do seznamu metodou Add pro seznam typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist02.go
25 doublylinkedlist03.go pokus o přidání prvků odlišného datového typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist03.go
26 doublylinkedlist04.go pokus o přidání prvků odlišného datového typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist04.go
27 doublylinkedlist05.go vymazání všech prvků ze seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist05.go
28 doublylinkedlist06.go test na existenci prvků v seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist06.go
29 doublylinkedlist07.go přečtení prvků se zadaným indexem ze seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist07.go
30 doublylinkedlist08.go odstranění prvků se zadaným indexem ze seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist08.go
31 doublylinkedlist09.go operace Swap – prohození dvou prvků v seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist09.go
32 doublylinkedlist10.go operace Sort – setřídění prvků v seznamu typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist10.go
33 doublylinkedlist11.go implementace iterátoru nad seznamem typu doublylinkedlist https://github.com/tisnik/go-root/blob/master/article92/dou­blylinkedlist11.go
       
34 arraystack01.go operace Push nad zásobníkem typu arraystack https://github.com/tisnik/go-root/blob/master/article92/a­rraystack01.go
35 arraystack02.go operace Pop nad zásobníkem typu arraystack https://github.com/tisnik/go-root/blob/master/article92/a­rraystack02.go
36 arraystack03.go operace Peek nad zásobníkem typu arraystack https://github.com/tisnik/go-root/blob/master/article92/a­rraystack03.go
37 arraystack04.go metody Size a Empty nad zásobníkem typu arraystack https://github.com/tisnik/go-root/blob/master/article92/a­rraystack04.go
       
38 linkedliststack01.go operace Push nad zásobníkem typu linkedliststack https://github.com/tisnik/go-root/blob/master/article92/lin­kedliststack01.go
39 linkedliststack02.go operace Pop nad zásobníkem typu linkedliststack https://github.com/tisnik/go-root/blob/master/article92/lin­kedliststack02.go
40 linkedliststack03.go operace Peek nad zásobníkem typu linkedliststack https://github.com/tisnik/go-root/blob/master/article92/lin­kedliststack03.go
41 linkedliststack04.go metody Size a Empty nad zásobníkem typu linkedliststack https://github.com/tisnik/go-root/blob/master/article92/lin­kedliststack04.go
       
42 stack_rpn.go vyhodnocení výrazu zapsaného v RPN https://github.com/tisnik/go-root/blob/master/article92/stac­k_rpn.go
43 stack_rpn_B.go vyhodnocení výrazu zapsaného v RPN, použití odlišné implementace zásobníku https://github.com/tisnik/go-root/blob/master/article92/stac­k_rpn_B.go
44 rpn.go vyhodnocení aritmetického výrazu https://github.com/tisnik/go-root/blob/master/article92/rpn.go
45 erasthotenes.go implementace Eratosthenova síta https://github.com/tisnik/go-root/blob/master/article92/e­rasthotenes.go

20. Odkazy na Internetu

  1. Genfuncs – implements various functions utilizing Go's Generics to help avoid writing boilerplate code
    https://github.com/nwillc/genfuncs
  2. Go18DS (Go 1.18+ Data Structures)
    https://github.com/daichi-m/go18ds
  3. TreeMap v2
    https://github.com/igrmk/treemap
  4. Fp-go is a collection of Functional Programming helpers powered by Golang 1.18+ generics
    https://github.com/repeale/fp-go
  5. The Go Programming Language Specification
    https://go.dev/ref/spec
  6. Generics in Go
    https://bitfieldconsultin­g.com/golang/generics
  7. Tutorial: Getting started with generics
    https://go.dev/doc/tutorial/generics
  8. Type parameters in Go
    https://bitfieldconsultin­g.com/golang/type-parameters
  9. Go Data Structures: Binary Search Tree
    https://flaviocopes.com/golang-data-structure-binary-search-tree/
  10. Gobs of data
    https://blog.golang.org/gobs-of-data
  11. How the Go runtime implements maps efficiently (without generics)
    https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics
  12. Go 1.18 Release Notes
    https://golang.org/doc/go1.18
  13. Go 1.17 Release Notes
    https://golang.org/doc/go1.17
  14. Go 1.16 Release Notes
    https://golang.org/doc/go1.16
  15. Go 1.15 Release Notes
    https://golang.org/doc/go1.15
  16. Go 1.14 Release Notes
    https://golang.org/doc/go1.14
  17. Go 1.13 Release Notes
    https://golang.org/doc/go1.13
  18. Go 1.12 Release Notes
    https://golang.org/doc/go1.12
  19. Go 1.11 Release Notes
    https://golang.org/doc/go1.11
  20. Go 1.11 Release Notes
    https://golang.org/doc/go1.11
  21. Go 1.10 Release Notes
    https://golang.org/doc/go1.10
  22. Go 1.9 Release Notes
    https://golang.org/doc/go1.9
  23. Go 1.8 Release Notes
    https://golang.org/doc/go1.8
  24. A Proposal for Adding Generics to Go
    https://go.dev/blog/generics-proposal
  25. Proposal: Go should have generics
    https://github.com/golang/pro­posal/blob/master/design/15292-generics.md
  26. Know Go: Generics (Kniha)
    https://bitfieldconsultin­g.com/books/generics
  27. Go 1.18 Generics based slice package
    https://golangexample.com/go-1–18-generics-based-slice-package/
  28. The missing slice package
    https://github.com/ssoroka/slice
  29. Dlouho očekávaná novinka v Go 1.18 – generické datové typy
    https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–18-genericke-datove-typy/
  30. Dlouho očekávaná novinka v Go 1.18 – generické datové typy (dokončení)
    https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–8-genericke-datove-typy-dokonceni/
  31. Generické datové typy v jazyce Go?
    https://www.root.cz/clanky/genericke-datove-typy-v-jazyce-go/
  32. GoDS (Go Data Structures)
    https://github.com/emirpasic/gods