Knihovny s implementací generických datových typů pro programovací jazyk Go (2)

Obsah

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

2. Čtyři varianty stromů v knihovně Go18DS

3. Přidání prvků do stromu, tisk struktury stromu

4. B-stromy

5. Průchod všemi uzly stromu

6. Přečtení všech prvků stromu

7. Přečtení zvoleného prvku stromu

8. Binární halda

9. Vložení prvků na haldu v jiném pořadí

10. Průchod prvky uloženými na binární haldě

11. Časová složitost operací se seznamy

12. Benchmark – operace se seznamy

13. Výsledky benchmarku

14. Časová složitost operací se stromy

15. Benchmark – operace se stromy

16. Výsledky benchmarku

17. Obsah navazujícího článku

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

19. Odkazy na Internetu

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

Na předchozí článek o knihovně Go18DS, která do Go přináší různé generické datové typy/kontejnery, dnes navážeme. Popíšeme si další dva velmi důležité kontejnery, konkrétně stromy (několika typů) a taktéž binární haldu (binary heap). Ovšem nezapomeneme ani na benchmarky, které ověří vlastnosti jednotlivých kontejnerů (prozatím si ukážeme benchmarky seznamů a stromů):

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:

2. Čtyři varianty stromů v knihovně Go18DS

V knihovně Go18DS nalezneme celkem čtyři různé implementace stromových datových struktur, přičemž tři z těchto struktur zařazují (přidávají) prvky do stromu na základě jejich váhy tak, aby se při průchodu stromem prvky vracely seřazené (podle váhy) a navíc bylo umožněno efektivní vyhledávání prvku ve stromu, ideálně se složitostí O(log N) s různým základem logaritmu. Poněkud odlišná je binární halda (binary heap) popsaná v samostatné kapitole:

Tyto implementace splňují (satisfy) rozhraní Tree:

type Tree[T comparable] interface {
    containers.Container[T]
}

A současně splňují i nám již dobře známé rozhraní Container:

type Container[T any] interface {
    Empty() bool
    Size() int
    Clear()
    Values() []T
}

3. Přidání prvků do stromu, tisk struktury stromu

AVL-stromy a červeno-černé stromy se vytváří s využitím několika typů konstruktorů, jejichž jména určují, jak vlastně budou reprezentovány váhy jednotlivých uzlů. Poměrně typické je využití celočíselných vah. Takové stromy se vytváří konstruktorem NewWithIntComparator. Stromy jako takové jsou generickou datovou strukturou, takže musíme specifikovat i typ ukládaných hodnot (zde konkrétně se jedná o řetězce):

tree := treeImpl.NewWithIntComparator[string]()

kde treeImpl je buď balíček implementující AVL-stromy nebo červeno-černé stromy.

Základní operací, kterou podporují všechny implementace stromů v knihovně Go18DS, je přidání nového prvku či prvků do stromu. K tomuto účelu slouží metoda Put. Prvním parametrem této metody je váha uzlu, druhým parametrem pak ukládaná hodnota (či hodnoty, protože lze uložit více hodnot současně):

tree.Put(1, "G")

A konečně pro zobrazení struktury vytvořeného stromu lze použít standardní funkci fmt.Println:

fmt.Println(tree)

Podívejme se nyní na postupnou konstrukci AVL-stromu:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/avltree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
        fmt.Println(tree)
 
        tree.Put(1, "G")
        fmt.Println(tree)
 
        tree.Put(2, "a")
        tree.Put(3, "b")
        fmt.Println(tree)
 
        tree.Put(4, "a")
        tree.Put(5, "b")
        fmt.Println(tree)
 
        tree.Put(6, "a")
        tree.Put(7, "b")
        fmt.Println(tree)
 
        tree.Put(8, "a")
        tree.Put(9, "b")
        fmt.Println(tree)
}

Prakticky naprosto stejným způsobem je možné vytvořit červeno-černý strom; liší se jen jméno importovaného balíčku:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/redblacktree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
        fmt.Println(tree)
 
        tree.Put(1, "G")
        fmt.Println(tree)
 
        tree.Put(2, "a")
        tree.Put(3, "b")
        fmt.Println(tree)
 
        tree.Put(4, "a")
        tree.Put(5, "b")
        fmt.Println(tree)
 
        tree.Put(6, "a")
        tree.Put(7, "b")
        fmt.Println(tree)
 
        tree.Put(8, "a")
        tree.Put(9, "b")
        fmt.Println(tree)
}

Po spuštění prvního příkladu získáme postupné tvary AVL-stromu:

AVLTree
 
AVLTree
└── 1
 
AVLTree
│   ┌── 3
└── 2
    └── 1
 
AVLTree
│       ┌── 5
│   ┌── 4
│   │   └── 3
└── 2
    └── 1
 
AVLTree
│       ┌── 7
│   ┌── 6
│   │   └── 5
└── 4
    │   ┌── 3
    └── 2
        └── 1
 
AVLTree
│           ┌── 9
│       ┌── 8
│       │   └── 7
│   ┌── 6
│   │   └── 5
└── 4
    │   ┌── 3
    └── 2
        └── 1

Porovnejme tyto výsledky s červeno-černým stromem, jenž je budován odlišně:

RedBlackTree
 
RedBlackTree
└── 1
 
RedBlackTree
│   ┌── 3
└── 2
    └── 1
 
RedBlackTree
│       ┌── 5
│   ┌── 4
│   │   └── 3
└── 2
    └── 1
 
RedBlackTree
│           ┌── 7
│       ┌── 6
│       │   └── 5
│   ┌── 4
│   │   └── 3
└── 2
    └── 1
 
RedBlackTree
│           ┌── 9
│       ┌── 8
│       │   └── 7
│   ┌── 6
│   │   └── 5
└── 4
    │   ┌── 3
    └── 2
        └── 1

4. B-stromy

V knihovně Go18DS nalezneme i podporu pro známou datovou strukturu B-strom. Při konstrukci tohoto typu stromu je nutné specifikovat jeho řád (order), což znamená, že se konstruktor B-stromu odlišuje od konstruktoru AVL-stromů i červeno-černých stromů:

tree := treeImpl.NewWithIntComparator[string](3)

I strukturu B-stromu lze vypsat na terminál, ovšem ne v tak názorné podobě, jako je tomu u dalších dvou typů stromů:

fmt.Println(tree)

V následujícím demonstračním příkladu je zkonstruován B-strom řádu 3:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](3)
        fmt.Println(tree)
 
        tree.Put(1, "G")
        fmt.Println(tree)
 
        tree.Put(2, "a")
        tree.Put(3, "b")
        fmt.Println(tree)
 
        tree.Put(4, "a")
        tree.Put(5, "b")
        fmt.Println(tree)
 
        tree.Put(6, "a")
        tree.Put(7, "b")
        fmt.Println(tree)
 
        tree.Put(8, "a")
        tree.Put(9, "b")
        fmt.Println(tree)
}

S výsledky:

BTree
 
BTree
1
 
BTree
    1
2
    3
 
BTree
    1
2
    3
4
    5
 
BTree
        1
    2
        3
4
        5
    6
        7
 
BTree
        1
    2
        3
4
        5
    6
        7
    8
        9

Nyní se pokusíme zkonstruovat B-strom řádu 4:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](4)
        fmt.Println(tree)
 
        tree.Put(1, "G")
        fmt.Println(tree)
 
        tree.Put(2, "a")
        tree.Put(3, "b")
        fmt.Println(tree)
 
        tree.Put(4, "a")
        tree.Put(5, "b")
        fmt.Println(tree)
 
        tree.Put(6, "a")
        tree.Put(7, "b")
        fmt.Println(tree)
 
        tree.Put(8, "a")
        tree.Put(9, "b")
        fmt.Println(tree)
}

Výsledkem bude mnohem plošší strom:

BTree
 
BTree
1
 
BTree
1
2
3
 
BTree
    1
2
    3
    4
    5
 
BTree
    1
2
    3
4
    5
    6
    7
 
BTree
    1
2
    3
4
    5
6
    7
    8
    9

A konečně se pokusme zkonstruovat B-strom řádu 20:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](20)
        fmt.Println(tree)
 
        tree.Put(1, "G")
        fmt.Println(tree)
 
        tree.Put(2, "a")
        tree.Put(3, "b")
        fmt.Println(tree)
 
        tree.Put(4, "a")
        tree.Put(5, "b")
        fmt.Println(tree)
 
        tree.Put(6, "a")
        tree.Put(7, "b")
        fmt.Println(tree)
 
        tree.Put(8, "a")
        tree.Put(9, "b")
        fmt.Println(tree)
}

B-strom je v tomto případě de facto zploštěn do podoby seznamu:

BTree
 
BTree
1
 
BTree
1
2
3
 
BTree
1
2
3
4
5
 
BTree
1
2
3
4
5
6
7
 
BTree
1
2
3
4
5
6
7
8
9

5. Průchod všemi uzly stromu

Všechny implementace stromů podporují průchod prvky stromu s využitím iterátoru, což nám umožňuje velmi snadno realizovat průchod založený na následující programové smyčce:

it := tree.Iterator()
for it.Next() {
        value := it.Value()
        fmt.Printf("%3s \t %T\n", value, value)
}

Podívejme se na použití této smyčky v případě AVL-stromů

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/avltree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree)
 
        it := tree.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3s \t %T\n", value, value)
        }
}

Výsledek:

AVLTree
│           ┌── 9
│       ┌── 8
│       │   └── 7
│   ┌── 6
│   │   │   ┌── 5
│   │   └── 4
└── 3
    └── 2
        └── 1
 
  a      string
  b      string
  c      string
  d      string
  e      string
  f      string
  g      string
  h      string
  i      string

Naprosto stejným způsobem můžeme realizovat průchod červeno-černým stromem:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/redblacktree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree)
 
        it := tree.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3s \t %T\n", value, value)
        }
 
}

Strom je sice interně odlišný, ale prvky jsou procházeny ve stejném pořadí:

│       ┌── 9
│   ┌── 8
│   │   │   ┌── 7
│   │   └── 6
│   │       └── 5
└── 4
    │   ┌── 3
    └── 2
        └── 1
 
  a      string
  b      string
  c      string
  d      string
  e      string
  f      string
  g      string
  h      string
  i      string

A konečně se podívejme na průchod B-stromem:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](3)
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree)
 
        it := tree.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3s \t %T\n", value, value)
        }
 
}

S výsledkem se stejným pořadím prvků:

BTree
        1
    2
        3
4
        5
    6
        7
    8
        9
 
  a      string
  b      string
  c      string
  d      string
  e      string
  f      string
  g      string
  h      string
  i      string

6. Přečtení všech prvků stromu

Pro přečtení všech prvků uložených ve stromu (libovolného typu) se používá metoda Values, která je ostatně společná pro všechny kontejnery (containers).

Přečtení všech prvků uložených do AVL-stromu:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/avltree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Values())
}

Výsledkem je sekvence:

[a b c d e f g h i]

Přečtení všech prvků uložených do červeno-černého stromu:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/redblacktree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Values())
}

Výsledkem je naprosto stejná sekvence:

[a b c d e f g h i]

A konečně přečtení všech prvků z B-stromu:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](3)
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Values())
}

Výsledkem je opět naprosto stejná sekvence:

[a b c d e f g h i]

7. Přečtení zvoleného prvku stromu

Mnohdy ovšem nepotřebujeme přečíst všechny prvky uložené do stromu nebo procházet všemi těmito prvky. Některé algoritmy vyžadují získání prvku na základě jeho klíče (nebo indexu), což konkrétně v našich demonstračních příkladech znamená použití celočíselné váhy/indexu. K tomu slouží metoda Get, která navíc vrací i příznak, zda prvek existuje či nikoli (už tuto metodu známe z předchozích dvou článků).

První příklad opět využívá AVL-strom:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/avltree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Get(0))
        fmt.Println(tree.Get(1))
        fmt.Println(tree.Get(9))
}

Výsledek:

 false
a true
i true

Stejný příklad, ovšem založený na červeno-černých stromech:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/redblacktree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string]()
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Get(0))
        fmt.Println(tree.Get(1))
        fmt.Println(tree.Get(9))
}

Výsledek:

 false
a true
i true

A konečně prakticky totožný příklad, ovšem využívající B-stromy:

package main
 
import (
        "fmt"
 
        treeImpl "github.com/daichi-m/go18ds/trees/btree"
)
 
func main() {
        tree := treeImpl.NewWithIntComparator[string](3)
 
        tree.Put(1, "a")
        tree.Put(9, "i")
        tree.Put(2, "b")
        tree.Put(8, "h")
        tree.Put(3, "c")
        tree.Put(7, "g")
        tree.Put(4, "d")
        tree.Put(6, "f")
        tree.Put(5, "e")
 
        fmt.Println(tree.Get(0))
        fmt.Println(tree.Get(1))
        fmt.Println(tree.Get(9))
}

Opět získáme totožný výsledek:

 false
a true
i true

8. Binární halda

Další datovou strukturou je takzvaná binární halda neboli binary heap. Interně je binární halda, jakožto konkrétní implementace strukturovaného datového typu haldy, reprezentována speciálně uloženým binárním stromem, na nějž jsou vztažena další dvě omezení:

1. Až na poslední úroveň musí být binární strom vyvážený. Poslední úroveň může být buď kompletní (potom je pochopitelně celý binární strom vyvážený) nebo nekompletní. V případě, že je poslední úroveň nekompletní, naplňují se uzly na této úrovni zleva doprava.
2. Hodnota uložená v každém uzlu takového binárního stromu musí býtvětší nebo rovna hodnotám uloženým v potomcích uzlu. Naproti tomu tato vlastnost nijak přesněji nespecifikuje, jak (a zda vůbec) musí být potomci daného uzlu uspořádány. Pokud například oba potomky nějakého uzlu prohodíme, jedná se o zcela korektní operaci, která nijak toto pravidlo (omezení) neporuší.

Samozřejmě platí, že podmínka větší nebo rovna je volitelná, resp. přesněji řečeno si programátor sám může zvolit funkci, která tuto podmínku testuje.

Nejjednodušší způsob použití haldy je založen na její konstrukci následované operacemi Push pro vložení prvků na haldu:

package main
 
import (
        "fmt"
 
        heapImpl "github.com/daichi-m/go18ds/trees/binaryheap"
)
 
func main() {
        heap := heapImpl.NewWithIntComparator()
        fmt.Println(heap)
 
        heap.Push(1)
        fmt.Println(heap)
 
        heap.Push(2)
        heap.Push(3)
        fmt.Println(heap)
 
        heap.Push(4)
        heap.Push(5)
        fmt.Println(heap)
 
        heap.Push(6)
        heap.Push(7)
        fmt.Println(heap)
 
        heap.Push(8)
        heap.Push(9)
        fmt.Println(heap)
}

Výsledek po spuštění ukazuje způsob uložení prvků z pohledu programátora:

BinaryHeap
 
BinaryHeap
1
BinaryHeap
1, 2, 3
BinaryHeap
1, 2, 3, 4, 5
BinaryHeap
1, 2, 3, 4, 5, 6, 7
BinaryHeap
1, 2, 3, 4, 5, 6, 7, 8, 9

9. Vložení prvků na haldu v jiném pořadí

Pokusme se nyní na haldu uložit prvky v jiném pořadí. Přitom je nutné mít na paměti, že uspořádání prvků je založeno přímo na jejich hodnotě, na rozdíl od stromů, do nichž se ukládaly dvojice klíč(váha):hodnota:

package main
 
import (
        "fmt"
 
        heapImpl "github.com/daichi-m/go18ds/trees/binaryheap"
)
 
func main() {
        heap := heapImpl.NewWithIntComparator()
        fmt.Println(heap)
 
        heap.Push(9)
        heap.Push(8)
        fmt.Println(heap)
 
        heap.Push(7)
        heap.Push(6)
        fmt.Println(heap)
 
        heap.Push(5)
        heap.Push(4)
        fmt.Println(heap)
 
        heap.Push(3)
        heap.Push(2)
        fmt.Println(heap)
 
        heap.Push(1)
        fmt.Println(heap)
}

Povšimněte si, že nyní budou výsledky skutečně odlišné v porovnáním s příkladem z předchozí kapitoly:

BinaryHeap
 
BinaryHeap
8, 9
BinaryHeap
6, 7, 8, 9
BinaryHeap
4, 6, 5, 9, 7, 8
BinaryHeap
2, 3, 4, 6, 7, 8, 5, 9
BinaryHeap
1, 2, 4, 3, 7, 8, 5, 9, 6

10. Průchod prvky uloženými na binární haldě

Vzhledem k tomu, že i binární halda splňuje rozhraní Container, můžeme snadno realizovat průchod jejími prvky, a to následovně:

package main
 
import (
        "fmt"
 
        heapImpl "github.com/daichi-m/go18ds/trees/binaryheap"
)
 
func main() {
        heap := heapImpl.NewWithIntComparator()
        fmt.Println(heap)
 
        heap.Push(9)
        heap.Push(8)
        fmt.Println(heap)
 
        heap.Push(7)
        heap.Push(6)
        fmt.Println(heap)
 
        heap.Push(5)
        heap.Push(4)
        fmt.Println(heap)
 
        heap.Push(3)
        heap.Push(2)
        fmt.Println(heap)
 
        heap.Push(1)
        fmt.Println(heap)
 
        it := heap.Iterator()
        for it.Next() {
                value := it.Value()
                fmt.Printf("%3d \t %T\n", value, value)
        }
}

S těmito výsledky:

BinaryHeap
 
BinaryHeap
8, 9
BinaryHeap
6, 7, 8, 9
BinaryHeap
4, 6, 5, 9, 7, 8
BinaryHeap
2, 3, 4, 6, 7, 8, 5, 9
BinaryHeap
1, 2, 4, 3, 7, 8, 5, 9, 6
  1      int
  2      int
  4      int
  3      int
  7      int
  8      int
  5      int
  9      int
  6      int

11. Časová složitost operací se seznamy

Víme již, že 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

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

Jaké jsou skutečné nároky jednotlivých operací v reálných časových jednotkách zjistíme na základě benchmarku zmíněného v navazující kapitole.

12. Benchmark – operace se seznamy

Pro zjištění délky trvání základních operací se seznamy realizovanými různým způsobem byl vytvořen následující benchmark, který se spouští s využitím standardních nástrojů programovacího jazyka Go – go test. Přitom je možné specifikovat, kolikrát se má daná část kódu spustit; tato hodnota je dostupná přes strukturu testing.B v prvku (atributu) N (ostatně to uvidíme dále):

package main
 
import (
        "testing"
 
        "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"
)
 
func BenchmarkArrayListInsert0Operation(b *testing.B) {
        l := arraylist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(0, i)
        }
}
 
func BenchmarkSinglyLinkedListInsert0Operation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(0, i)
        }
}
 
func BenchmarkDoublyLinkedListInsert0Operation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(0, i)
        }
}
 
func BenchmarkArrayListInsertMiddleOperation(b *testing.B) {
        l := arraylist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(l.Size()/2, i)
        }
}
 
func BenchmarkSinglyLinkedListInsertMiddleOperation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(l.Size()/2, i)
        }
}
 
func BenchmarkDoublyLinkedListInsertMiddleOperation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Insert(l.Size()/2, i)
        }
}
 
func BenchmarkArrayListAppendOperation(b *testing.B) {
        l := arraylist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Add(i)
        }
}
 
func BenchmarkSinglyLinkedListAppendOperation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Add(i)
        }
}
 
func BenchmarkDoublyLinkedListAppendOperation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        for i := 0; i < b.N; i++ {
                l.Add(i)
        }
}
 
func fillInList(l lists.List[int], n int) {
        for i := 0; i < n; i++ {
                l.Add(i)
        }
}
 
func BenchmarkArrayListRemoveFirstOperation(b *testing.B) {
        l := arraylist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(0)
        }
}
 
func BenchmarkSinglyLinkedListRemoveFirstOperation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(0)
        }
}
 
func BenchmarkDoublyLinkedListRemoveFirstOperation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(0)
        }
}
 
func BenchmarkArrayListRemoveLastOperation(b *testing.B) {
        l := arraylist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(l.Size() - 1)
        }
}
 
func BenchmarkSinglyLinkedListRemoveLastOperation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(l.Size() - 1)
        }
}
 
func BenchmarkDoublyLinkedListRemoveLastOperation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                l.Remove(l.Size() - 1)
        }
}
 
func BenchmarkArrayListGetOperation(b *testing.B) {
        l := arraylist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                _, exist := l.Get(i)
                if !exist {
                        b.Fail()
                }
        }
}
 
func BenchmarkSinglyLinkedListGetOperation(b *testing.B) {
        l := singlylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                _, exist := l.Get(i)
                if !exist {
                        b.Fail()
                }
        }
}
 
func BenchmarkDoublyLinkedListGetOperation(b *testing.B) {
        l := doublylinkedlist.New[int]()
        fillInList(l, b.N)
 
        for i := 0; i < b.N; i++ {
                _, exist := l.Get(i)
                if !exist {
                        b.Fail()
                }
        }
}

Implementováno je tedy měření doby trvání těchto operací:

1. Vložení prvku na začátek seznamu
2. Vložení prvku doprostřed seznamu
3. Přidání prvku za konec seznamu
4. Odstranění prvního prvku ze seznamu
5. Odstranění posledního prvku ze seznamu
6. Postupné přečtení všech prvků ze seznamu

13. Výsledky benchmarku

Benchmark, jehož zdrojový kód byl uveden v předchozí kapitole, budeme postupně spouštět se zvyšující se hodnotou N, takže uvidíme, jak jsou operace náročné pro malé seznamy a jak se jejich časová náročnost zvětší společně se zvyšujícím se počtem prvků v seznamech.

Začneme se seznamy o maximální délce jednoho prvku:

$ go test -bench=.  -benchtime=1x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkArrayListInsert0Operation-8                           1               972.0 ns/op
BenchmarkSinglyLinkedListInsert0Operation-8                    1               666.0 ns/op
BenchmarkDoublyLinkedListInsert0Operation-8                    1               522.0 ns/op
BenchmarkArrayListInsertMiddleOperation-8                      1               664.0 ns/op
BenchmarkSinglyLinkedListInsertMiddleOperation-8               1               485.0 ns/op
BenchmarkDoublyLinkedListInsertMiddleOperation-8               1               458.0 ns/op
BenchmarkArrayListAppendOperation-8                            1               680.0 ns/op
BenchmarkSinglyLinkedListAppendOperation-8                     1               500.0 ns/op
BenchmarkDoublyLinkedListAppendOperation-8                     1               427.0 ns/op
BenchmarkArrayListRemoveFirstOperation-8                       1               772.0 ns/op
BenchmarkSinglyLinkedListRemoveFirstOperation-8                1               887.0 ns/op
BenchmarkDoublyLinkedListRemoveFirstOperation-8                1              1121 ns/op
BenchmarkArrayListRemoveLastOperation-8                        1               820.0 ns/op
BenchmarkSinglyLinkedListRemoveLastOperation-8                 1               846.0 ns/op
BenchmarkDoublyLinkedListRemoveLastOperation-8                 1              1011 ns/op
BenchmarkArrayListGetOperation-8                               1              1170 ns/op
BenchmarkSinglyLinkedListGetOperation-8                        1               911.0 ns/op
BenchmarkDoublyLinkedListGetOperation-8                        1               925.0 ns/op

Nyní zvýšíme počet operací (a tím pádem i prvků v seznamu) na tisíc:

$ go test -bench=.  -benchtime=1000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkArrayListInsert0Operation-8                        1000                50.74 ns/op
BenchmarkSinglyLinkedListInsert0Operation-8                 1000                47.76 ns/op
BenchmarkDoublyLinkedListInsert0Operation-8                 1000                49.05 ns/op
BenchmarkArrayListInsertMiddleOperation-8                   1000                38.22 ns/op
BenchmarkSinglyLinkedListInsertMiddleOperation-8            1000               301.3 ns/op
BenchmarkDoublyLinkedListInsertMiddleOperation-8            1000               314.8 ns/op
BenchmarkArrayListAppendOperation-8                         1000                15.46 ns/op
BenchmarkSinglyLinkedListAppendOperation-8                  1000                31.87 ns/op
BenchmarkDoublyLinkedListAppendOperation-8                  1000                28.25 ns/op
BenchmarkArrayListRemoveFirstOperation-8                    1000                66.13 ns/op
BenchmarkSinglyLinkedListRemoveFirstOperation-8             1000                45.42 ns/op
BenchmarkDoublyLinkedListRemoveFirstOperation-8             1000                50.19 ns/op
BenchmarkArrayListRemoveLastOperation-8                     1000                35.48 ns/op
BenchmarkSinglyLinkedListRemoveLastOperation-8              1000               568.3 ns/op
BenchmarkDoublyLinkedListRemoveLastOperation-8              1000                39.47 ns/op
BenchmarkArrayListGetOperation-8                            1000                21.56 ns/op
BenchmarkSinglyLinkedListGetOperation-8                     1000               578.4 ns/op
BenchmarkDoublyLinkedListGetOperation-8                     1000               278.6 ns/op

Zvyšme tedy počet operací na 10000:

$ go test -bench=.  -benchtime=10000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkArrayListInsert0Operation-8                       10000               574.8 ns/op
BenchmarkSinglyLinkedListInsert0Operation-8                10000                27.98 ns/op
BenchmarkDoublyLinkedListInsert0Operation-8                10000                30.98 ns/op
BenchmarkArrayListInsertMiddleOperation-8                  10000               193.3 ns/op
BenchmarkSinglyLinkedListInsertMiddleOperation-8           10000              3444 ns/op
BenchmarkDoublyLinkedListInsertMiddleOperation-8           10000              4593 ns/op
BenchmarkArrayListAppendOperation-8                        10000                10.63 ns/op
BenchmarkSinglyLinkedListAppendOperation-8                 10000                21.70 ns/op
BenchmarkDoublyLinkedListAppendOperation-8                 10000                30.95 ns/op
BenchmarkArrayListRemoveFirstOperation-8                   10000               541.4 ns/op
BenchmarkSinglyLinkedListRemoveFirstOperation-8            10000                39.63 ns/op
BenchmarkDoublyLinkedListRemoveFirstOperation-8            10000                41.80 ns/op
BenchmarkArrayListRemoveLastOperation-8                    10000                28.46 ns/op
BenchmarkSinglyLinkedListRemoveLastOperation-8             10000              5606 ns/op
BenchmarkDoublyLinkedListRemoveLastOperation-8             10000                45.79 ns/op
BenchmarkArrayListGetOperation-8                           10000                24.72 ns/op
BenchmarkSinglyLinkedListGetOperation-8                    10000              4855 ns/op
BenchmarkDoublyLinkedListGetOperation-8                    10000              2758 ns/op

Počet prvků dále zvýšíme, a to desetkrát:

$ go test -bench=.  -benchtime=100000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkArrayListInsert0Operation-8                      100000              8034 ns/op
BenchmarkSinglyLinkedListInsert0Operation-8               100000                25.11 ns/op
BenchmarkDoublyLinkedListInsert0Operation-8               100000                27.59 ns/op
BenchmarkArrayListInsertMiddleOperation-8                 100000              3475 ns/op
BenchmarkSinglyLinkedListInsertMiddleOperation-8          100000             38085 ns/op
BenchmarkDoublyLinkedListInsertMiddleOperation-8          100000             51326 ns/op
BenchmarkArrayListAppendOperation-8                       100000                 7.919 ns/op
BenchmarkSinglyLinkedListAppendOperation-8                100000                31.44 ns/op
BenchmarkDoublyLinkedListAppendOperation-8                100000                26.86 ns/op
BenchmarkArrayListRemoveFirstOperation-8                  100000              8230 ns/op
BenchmarkSinglyLinkedListRemoveFirstOperation-8           100000                39.10 ns/op
BenchmarkDoublyLinkedListRemoveFirstOperation-8           100000                44.39 ns/op
BenchmarkArrayListRemoveLastOperation-8                   100000                25.78 ns/op
BenchmarkSinglyLinkedListRemoveLastOperation-8            100000             58259 ns/op
BenchmarkDoublyLinkedListRemoveLastOperation-8            100000                41.96 ns/op
BenchmarkArrayListGetOperation-8                          100000                21.33 ns/op
BenchmarkSinglyLinkedListGetOperation-8                   100000             52119 ns/op
BenchmarkDoublyLinkedListGetOperation-8                   100000             32143 ns/op

Nyní jsou rozdíly mezi arraylistem na straně jedné a lineárně vázanými seznamy na straně druhé ještě markantnější. Ovšem povšimněte si toho, že odebrání posledního prvku je u obousměrně vázaného seznamu triviální operací, kdežto u jednosměrně vázaného seznamu se jedná o operaci pomalou (a závislou na velikosti seznamu) – což je opět očekávatelné chování.

A konečně spusťme benchmark pro N=200000:

$ go test -bench=.  -benchtime=200000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkArrayListInsert0Operation-8                      200000             46394 ns/op
BenchmarkSinglyLinkedListInsert0Operation-8               200000                31.87 ns/op
BenchmarkDoublyLinkedListInsert0Operation-8               200000                42.38 ns/op
BenchmarkArrayListInsertMiddleOperation-8                 200000              9252 ns/op
BenchmarkSinglyLinkedListInsertMiddleOperation-8          200000             77002 ns/op
BenchmarkDoublyLinkedListInsertMiddleOperation-8          200000            105458 ns/op
BenchmarkArrayListAppendOperation-8                       200000                 8.773 ns/op
BenchmarkSinglyLinkedListAppendOperation-8                200000                26.50 ns/op
BenchmarkDoublyLinkedListAppendOperation-8                200000                35.79 ns/op
BenchmarkArrayListRemoveFirstOperation-8                  200000             45917 ns/op
BenchmarkSinglyLinkedListRemoveFirstOperation-8           200000               139.4 ns/op
BenchmarkDoublyLinkedListRemoveFirstOperation-8           200000               138.5 ns/op
BenchmarkArrayListRemoveLastOperation-8                   200000                53.20 ns/op
BenchmarkSinglyLinkedListRemoveLastOperation-8            200000            122137 ns/op
BenchmarkDoublyLinkedListRemoveLastOperation-8            200000                60.09 ns/op
BenchmarkArrayListGetOperation-8                          200000                23.92 ns/op
BenchmarkSinglyLinkedListGetOperation-8                   200000            108607 ns/op
BenchmarkDoublyLinkedListGetOperation-8                   200000             68191 ns/op

Nyní jsou rozdíly zcela zřetelné a říkají:

1. Arraylist je skvělý při potřebě náhodného přístupu k prvkům přes index
2. Jednosměrně vázaný seznam má rychlé operace přidání prvku na začátek seznamu a odstranění prvku ze začátku seznamu, ostatní operace mají minimálně složitost O(n)
3. Obousměrně vázané seznamy navíc dokážou velmi rychle přidávat a odebírat prvky na konec seznamu, ovšem ostatní operace jsou (o konstantu) pomalejší a větší je i náročnost na kapacitu operační paměti

14. Časová složitost operací se stromy

Stromy patří mezi datové struktury, které byly vynalezeny primárně právě z toho důvodu, aby byly některé operace s nimi prováděny s lepší než lineární časovou složitostí O(n). Typicky jsou stromy navrženy tak, aby se složitost typických operací blížila k O(log N) s různým základem logaritmu (2 či výše). V následujícím benchmarku si tedy otestujeme reálnou časovou složitost vybraných operací nad stromy, resp. přesněji řečeno nad prvky stromů.

15. Benchmark – operace se stromy

Podívejme se na následující realizaci benchmarku, v němž jsou realizovány některé operace se stromy, konkrétně:

1. Vložení prvků do stromů všech typů (B-tree je realizován s různým řádem – order)
2. Přečtení prvku ze stromů všech typů

Zdrojový kód benchmarku vypadá takto:

package main
 
import (
        "testing"
 
        "github.com/daichi-m/go18ds/trees/avltree"
        "github.com/daichi-m/go18ds/trees/btree"
        "github.com/daichi-m/go18ds/trees/redblacktree"
)
 
func BenchmarkAVLTreePutOperation(b *testing.B) {
        t := avltree.NewWithIntComparator[int]()
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkRBTreePutOperation(b *testing.B) {
        t := redblacktree.NewWithIntComparator[int]()
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkBTree3PutOperation(b *testing.B) {
        t := btree.NewWithIntComparator[int](3)
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkBTree4PutOperation(b *testing.B) {
        t := btree.NewWithIntComparator[int](4)
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkBTree5PutOperation(b *testing.B) {
        t := btree.NewWithIntComparator[int](5)
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkBTree9PutOperation(b *testing.B) {
        t := btree.NewWithIntComparator[int](9)
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
func BenchmarkBTree99PutOperation(b *testing.B) {
        t := btree.NewWithIntComparator[int](99)
        for i := 0; i < b.N; i++ {
                t.Put(i, i)
        }
}
 
const MAX = 10000
 
func BenchmarkAVLTreeGet(b *testing.B) {
        t := avltree.NewWithIntComparator[int]()
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}
 
func BenchmarkRBTreeGet(b *testing.B) {
        t := redblacktree.NewWithIntComparator[int]()
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}
 
func BenchmarkBTree3Get(b *testing.B) {
        t := btree.NewWithIntComparator[int](3)
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}
 
func BenchmarkBTree4Get(b *testing.B) {
        t := btree.NewWithIntComparator[int](4)
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}
 
func BenchmarkBTree9Get(b *testing.B) {
        t := btree.NewWithIntComparator[int](9)
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}
 
func BenchmarkBTree99Get(b *testing.B) {
        t := btree.NewWithIntComparator[int](99)
        for i := 0; i < MAX; i++ {
                t.Put(i, i)
        }
 
        for i := 0; i < b.N; i++ {
                _, _ = t.Get(i % MAX)
        }
}

16. Výsledky benchmarku

Nejprve opět spustíme benchmark pouze pro jediné opakování:

$ go test --bench=. tree_test.go -benchtime=1x
 
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkAVLTreePutOperation-8                 1               554.0 ns/op
BenchmarkRBTreePutOperation-8                  1               574.0 ns/op
BenchmarkBTree3PutOperation-8                  1              1097 ns/op
BenchmarkBTree4PutOperation-8                  1               937.0 ns/op
BenchmarkBTree5PutOperation-8                  1              1082 ns/op
BenchmarkBTree9PutOperation-8                  1              1380 ns/op
BenchmarkBTree99PutOperation-8                 1               944.0 ns/op
BenchmarkAVLTreeGet-8                          1           2237783 ns/op
BenchmarkRBTreeGet-8                           1           1636171 ns/op
BenchmarkBTree3Get-8                           1           5913260 ns/op
BenchmarkBTree4Get-8                           1           5330595 ns/op
BenchmarkBTree9Get-8                           1           2149327 ns/op
BenchmarkBTree99Get-8                          1            898313 ns/op

Následuje operace se stromy majícími 1000 prvků:

$ go test --bench=. tree_test.go -benchtime=1000x
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkAVLTreePutOperation-8              1000               126.8 ns/op
BenchmarkRBTreePutOperation-8               1000               201.1 ns/op
BenchmarkBTree3PutOperation-8               1000               727.4 ns/op
BenchmarkBTree4PutOperation-8               1000               660.6 ns/op
BenchmarkBTree5PutOperation-8               1000               420.7 ns/op
BenchmarkBTree9PutOperation-8               1000               300.5 ns/op
BenchmarkBTree99PutOperation-8              1000               146.2 ns/op
BenchmarkAVLTreeGet-8                       1000              1452 ns/op
BenchmarkRBTreeGet-8                        1000              2015 ns/op
BenchmarkBTree3Get-8                        1000              6934 ns/op
BenchmarkBTree4Get-8                        1000              6724 ns/op
BenchmarkBTree9Get-8                        1000              2753 ns/op
BenchmarkBTree99Get-8                       1000              1228 ns/op

Ve třetím kroku budeme pracovat s 100000 prvky:

$ go test --bench=. tree_test.go -benchtime=100000x
 
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkAVLTreePutOperation-8            100000               166.8 ns/op
BenchmarkRBTreePutOperation-8             100000               195.3 ns/op
BenchmarkBTree3PutOperation-8             100000               698.7 ns/op
BenchmarkBTree4PutOperation-8             100000               691.4 ns/op
BenchmarkBTree5PutOperation-8             100000               412.4 ns/op
BenchmarkBTree9PutOperation-8             100000               276.0 ns/op
BenchmarkBTree99PutOperation-8            100000               118.8 ns/op
BenchmarkAVLTreeGet-8                     100000                74.61 ns/op
BenchmarkRBTreeGet-8                      100000                83.98 ns/op
BenchmarkBTree3Get-8                      100000               157.7 ns/op
BenchmarkBTree4Get-8                      100000               151.9 ns/op
BenchmarkBTree9Get-8                      100000               101.7 ns/op
BenchmarkBTree99Get-8                     100000                78.10 ns/op

A konečně se podívejme na chování při použití milionu prvků:

$ go test --bench=. tree_test.go -benchtime=1000000x
 
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkAVLTreePutOperation-8           1000000               203.1 ns/op
BenchmarkRBTreePutOperation-8            1000000               221.0 ns/op
BenchmarkBTree3PutOperation-8            1000000               777.8 ns/op
BenchmarkBTree4PutOperation-8            1000000               793.9 ns/op
BenchmarkBTree5PutOperation-8            1000000               488.3 ns/op
BenchmarkBTree9PutOperation-8            1000000               318.1 ns/op
BenchmarkBTree99PutOperation-8           1000000               136.2 ns/op
BenchmarkAVLTreeGet-8                    1000000                61.79 ns/op
BenchmarkRBTreeGet-8                     1000000                68.14 ns/op
BenchmarkBTree3Get-8                     1000000               113.9 ns/op
BenchmarkBTree4Get-8                     1000000               113.9 ns/op
BenchmarkBTree9Get-8                     1000000                88.22 ns/op
BenchmarkBTree99Get-8                    1000000                74.71 ns/op

17. Obsah navazujícího článku

V navazujícím článku popis knihovny Go18DS dokončíme. Popíšeme si zbývající datové struktury, což je několik implementací map a následně se zaměříme na popis pomocných funkcí a datových struktur – například různých variant komparátorů atd.

18. 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:

19. 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
33. Binární halda
    https://cs.wikipedia.org/wi­ki/Bin%C3%A1rn%C3%AD_halda
34. Binární strom
    https://cs.wikipedia.org/wi­ki/Bin%C3%A1rn%C3%AD_strom
35. AVL-strom
    https://cs.wikipedia.org/wiki/AVL-strom
36. Červeno-černý strom
    https://cs.wikipedia.org/wi­ki/%C4%8Cerveno-%C4%8Dern%C3%BD_strom
37. B-strom
    https://cs.wikipedia.org/wiki/B-strom