Hlavní navigace

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

28. 6. 2022
Doba čtení: 32 minut

Sdílet

 Autor: Go lang
Na předchozí článek o knihovně Go18DS dnes navážeme. Popíšeme si další dva velmi důležité kontejnery, konkrétně stromy (několika typů) a binární haldu. Ovšem nezapomeneme ani na benchmarky.

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ů):

Kontejner Překlad
List seznam
Set množina
Stack zásobník
Tree strom
BinaryHeap binární halda
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
Tree RedBlackTree AVLTree BTree BinaryHeap
Map HashMap TreeMap LinkedHashMap HashBidiMap TreeBidiMap

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:

# Datový typ Jméno struktury Popis struktury
1 BTree B-strom https://cs.wikipedia.org/wiki/B-strom
2 RedBlackTree červeno-černý strom https://cs.wikipedia.org/wi­ki/%C4%8Cerveno-%C4%8Dern%C3%BD_strom
3 AVLTree AVL strom https://cs.wikipedia.org/wiki/AVL-strom
       
4 BinaryHeap binární halda https://cs.wikipedia.org/wi­ki/Bin%C3%A1rn%C3%AD_halda

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
}
Poznámka: kromě toho je zajištěn přístup ke zvolenému prvku metodou Get.

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
Poznámka: povšimněte si, že AVL-strom je více vyvážený, zejména v páté variantě se sedmi prvky.

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.

Poznámka: halda jakožto datová struktura musí splňovat takzvanou vlastnost haldy: pokud je B potomek A, pak platí x(A) >= x(B). To znamená, že v kořenu stromu je vždy umístěn prvek s nejvyšším klíčem.

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:

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.

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
Poznámka: všechny operace prozatím trvají řádově stejnou dobu a mezi jednotlivými implementacemi seznamů tak nejsou podstatné rozdíly.

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
Poznámka: zde se již začíná ukazovat relativní složitost některých operací, ovšem počet prvků je stále velmi malý na to, aby bylo možné rozhodnout, kdy jaké typy seznamů použít.

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
Poznámka: podle očekávání je vkládání a odebírání prvků ze seznamu založeného na poli pomalejší, než u dalších dvou typů seznamů. Na druhou stranu přístup k prvku na základě jeho indexu je u tohoto typu seznamu prakticky konstantní.

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
Poznámka: zde se projevilo „zahřívání“ kódu, takže jsme prozatím nezjistili nic zajímavého.

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
Poznámka: nejzajímavější je v tomto kontextu sledování vlivu řádu (order) B-stromu na časovou složitost jednotlivých operací – prozatím vyhrávají „široké“ stromy s velký rozvětvením a malou hloubkou.

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
Poznámka: zde kupodivu vyhrávají AVL-stromy a červeno-černé stromy nad hlubokými B-stromy, a to v obou operacích.

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

skolení ELK

$ 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
Poznámka: důležité je, že časová složitost operací se prakticky nezměnila, i když pracujeme s desetkrát větším množstvím prvků. Zde stromy libovolného typu jasně vyhrávají nad lineárními datovými strukturami typu seznam.

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:

# 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
       
46 avl-tree01.go přidání prvků do stromu, výpis struktury stromu (AVL-stromy) https://github.com/tisnik/go-root/blob/master/article93/avl-tree01.go
47 avl-tree02.go iterace přes všechny prvky stromu (AVL-stromy) https://github.com/tisnik/go-root/blob/master/article93/avl-tree02.go
48 avl-tree03.go přečtení všech prvků uložených ve stromu (AVL-stromy) https://github.com/tisnik/go-root/blob/master/article93/avl-tree03.go
49 avl-tree04.go získání obsahů prvků (AVL-stromy) https://github.com/tisnik/go-root/blob/master/article93/avl-tree04.go
50 rb-tree01.go přidání prvků do stromu, výpis struktury stromu (RB-stromy) https://github.com/tisnik/go-root/blob/master/article93/rb-tree01.go
51 rb-tree02.go iterace přes všechny prvky stromu (RB-stromy) https://github.com/tisnik/go-root/blob/master/article93/rb-tree02.go
52 rb-tree03.go přečtení všech prvků uložených ve stromu (RB-stromy) https://github.com/tisnik/go-root/blob/master/article93/rb-tree03.go
53 rb-tree04.go získání obsahů prvků (RB-stromy) https://github.com/tisnik/go-root/blob/master/article93/rb-tree04.go
54 btree01.go konstrukce B-stromu řádu 3 https://github.com/tisnik/go-root/blob/master/article93/btre­e01.go
55 btree02.go konstrukce B-stromu řádu 4 https://github.com/tisnik/go-root/blob/master/article93/btre­e02.go
56 btree03.go konstrukce B-stromu řádu 20 https://github.com/tisnik/go-root/blob/master/article93/btre­e03.go
57 btree04.go iterace přes všechny prvky stromu (B-stromy) https://github.com/tisnik/go-root/blob/master/article93/btre­e04.go
58 btree05.go přečtení všech prvků uložených ve stromu (B-stromy) https://github.com/tisnik/go-root/blob/master/article93/btre­e05.go
59 btree06.go získání obsahů prvků (B-stromy) https://github.com/tisnik/go-root/blob/master/article93/btre­e06.go
60 binary_heap01.go konstrukce binární haldy https://github.com/tisnik/go-root/blob/master/article93/bi­nary_heap01.go
61 binary_heap02.go přidání prvků do binární haldy https://github.com/tisnik/go-root/blob/master/article93/bi­nary_heap02.go
62 binary_heap03.go iterace přes všechny prvky binární haldy https://github.com/tisnik/go-root/blob/master/article93/bi­nary_heap03.go
       
63 lists_test.go benchmark – operace se seznamy https://github.com/tisnik/go-root/blob/master/article93/lis­ts_test.go
64 tree_test.go benchmark – operace se stromy https://github.com/tisnik/go-root/blob/master/article93/tre­e_test.go

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

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.