Obsah
1. Knihovny s implementací generických datových typů pro programovací jazyk Go
2. Externí knihovna GoDS (Go Data Structures) v původní podobě
3. Ukázka využití původní knihovny GoDS
4. Rozšíření s podporou generických datových typů – Go18DS
5. Generické rozhraní Container a generická funkce Comparator
6. Datová struktura arraylist, jednosměrně a obousměrně vázané seznamy
7. Rozdíly mezi jednotlivými implementacemi seznamů
8. Konstrukce seznamů, přidání prvků do seznamů
10. Vymazání seznamu, test na existenci prvku, přečtení prvku ze seznamu
11. Vymazání prvku či prvků ze seznamu
13. Jednosměrně a obousměrně vázané seznamy, iterátor nad seznamy
15. Základní operace nad zásobníky
16. Praktické použití zásobníku – převod aritmetického výrazu do postfixové notace
19. Repositář s demonstračními příklady
1. Knihovny s implementací generických datových typů pro programovací jazyk Go
Pravděpodobně doposud nejvýznamnější novou vlastností programovacího jazyka Go je zavedení podpory pro generické datové typy v Go 1.18, což je vlastnost, kterou jsme se explicitně zabývali v článcích [1], [2] a nepřímo též v [3]. Právě existence generických datových typů umožnila vznik nových knihoven popř. úpravu již existujících knihoven, v nichž jsou implementovány různé datové typy popř. algoritmy pro práci s těmito datovými typy. Právě díky generickým datovým typům je možné obejít poněkud nešikovnou manipulaci s prázdnými rozhraními (interface{}), což je sice užitečný koncept, který ovšem zcela obchází striktní typový systém jazyka Go a nutí programátory k tomu, že aby datovými typy zabývali nikoli v čase překladu (compile time), ale až v čase běhu (runtime time).
Jedná se například o následující knihovny:
- Genfuncs
https://github.com/nwillc/genfuncs - Go18DS
https://github.com/daichi-m/go18ds - TreeMap v2
https://github.com/igrmk/treemap - Fp-go
https://github.com/repeale/fp-go
V dnešním článku i v navazujících článcích si jednotlivé výše zmíněné knihovny postupně popíšeme.
2. Externí knihovna GoDS (Go Data Structures) v původní podobě
Kontejnery (kolekce) nabízené samotným jazykem Go popř. jeho standardní knihovnou nám v praxi většinou nebudou postačovat, takže bude nutné sáhnout po externí knihovně. Těch existuje větší množství, ovšem pravděpodobně nejúplnější sadu kontejnerů nalezneme v knihovně pojmenované GoDS neboli plným jménem Go Data Structures. Tato knihovna vznikla v době, kdy jazyk Go nepodporoval generické datové typy, s čímž souvisí i určité problémy s jejím používáním.
Tato knihovna, jenž je dostupná na adrese https://github.com/emirpasic/gods, přidává do programovacího jazyka Go implementaci mnoha užitečných datových struktur – většinou kontejnerů. Jedná se tedy o takové struktury, jejichž úkolem je uchovat prvky určitých typů a dostupných pod určitým klíčem (celočíselným či obecným):
| Kontejner | Překlad |
|---|---|
| List | seznam |
| Set | množina |
| Stack | zásobník |
| Queue | fronta |
| Tree | strom |
| Map | mapa |
Ovšem vzhledem k tomu, že neexistuje taková implementace těchto datových struktur v podobě, v níž by všechny algoritmy byly realizovány s optimální složitostí, je každá výše zmíněná datová struktura realizována (implementována) hned několikrát, přičemž u každé implementace jsou některé operace optimální a jiné nikoli. Liší se i paměťová náročnost:
| Rozhraní | Implementace |
|---|---|
| List | ArrayList SinglyLinkedList DoublyLinkedList |
| Set | HashSet TreeSet LinkedHashSet |
| Stack | LinkedListStack ArrayStack |
| Queue | LinkedListQueue ArrayQueue CircularBuffer PriorityQueue |
| Tree | RedBlackTree AVLTree BTree BinaryHeap |
| Map | HashMap TreeMap LinkedHashMap HashBidiMap TreeBidiMap |
3. Ukázka využití původní knihovny GoDS
Podívejme se nyní na způsob využití původní knihovny GoDS. Konkrétně se jedná o implementaci jednoduché RPN (Reverse Polish Notation) kalkulačky. Pro realizaci zásobníku je přitom využit kontejner nazvaný arraystack, což je implementace zásobníku realizovaná nad polem (které se v případě potřeby realokuje, což ovšem při použití v jednoduché kalkulačce v naprosté většině případů nebude nutné). Povšimněte si triku u příkazu import, v níž se na arraystack budeme odkazovat přes obecnější alias stack:
package main
import (
"fmt"
stack "github.com/emirpasic/gods/stacks/arraystack"
"strconv"
"strings"
)
func printStack(s *stack.Stack) {
it := s.Iterator()
for it.Next() {
value := it.Value()
fmt.Printf("%3d ", value)
}
println()
}
func main() {
expression := "1 2 + 2 3 * 8 + *"
terms := strings.Split(expression, " ")
stack := stack.New()
for _, term := range terms {
switch term {
case "+":
operand1, _ := stack.Pop()
operand2, _ := stack.Pop()
stack.Push(operand1.(int) + operand2.(int))
print("+ :\t")
printStack(stack)
case "-":
operand1, _ := stack.Pop()
operand2, _ := stack.Pop()
stack.Push(operand2.(int) - operand1.(int))
print("- :\t")
printStack(stack)
case "*":
operand1, _ := stack.Pop()
operand2, _ := stack.Pop()
stack.Push(operand1.(int) * operand2.(int))
print("* :\t")
printStack(stack)
case "/":
operand1, _ := stack.Pop()
operand2, _ := stack.Pop()
stack.Push(operand2.(int) / operand1.(int))
print("/ :\t")
printStack(stack)
default:
number, err := strconv.Atoi(term)
if err == nil {
stack.Push(number)
}
fmt.Printf("%-2d:\t", number)
printStack(stack)
}
}
print("Result: ")
printStack(stack)
}
Při spuštění tohoto příkladu se bude postupně vypisovat obsah zásobníku operandů:
1 : 1 2 : 2 1 + : 3 2 : 2 3 3 : 3 2 3 * : 6 3 8 : 8 6 3 + : 14 3 * : 42 Result: 42
Program je sice relativně dobře čitelný, ovšem nepříjemný je zejména fakt, že je nutné explicitně kontrolovat typy prvků vyzvedávaných ze zásobníku operací Pop resp. Peek. Původní knihovna GoDS totiž nepodporuje generické datové typy a proto jsou všechny prvky typu „prázdné rozhraní“ neboli interface{}:
Rozhraní pro všechny implementace seznamů:
type List interface {
Get(index int) (interface{}, bool)
Remove(index int)
Add(values ...interface{})
Contains(values ...interface{}) bool
Sort(comparator utils.Comparator)
Swap(index1, index2 int)
Insert(index int, values ...interface{})
Set(index int, value interface{})
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
}
Rozhraní pro všechny implementace množin:
type Set interface {
Add(elements ...interface{})
Remove(elements ...interface{})
Contains(elements ...interface{}) bool
Intersection(another *Set) *Set
Union(another *Set) *Set
Difference(another *Set) *Set
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
}
Rozhraní pro obě implementace zásobníků:
type Stack interface {
Push(value interface{})
Pop() (value interface{}, ok bool)
Peek() (value interface{}, ok bool)
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
containers.Container
}
Rozhraní pro všechny implementace map:
type Map interface {
Put(key interface{}, value interface{})
Get(key interface{}) (value interface{}, found bool)
Remove(key interface{})
Keys() []interface{}
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
containers.Container
}
Rozhraní pro všechny implementace stromů:
type Tree interface {
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
containers.Container
}
Rozhraní pro všechny implementace front:
type Queue interface {
Enqueue(value interface{})
Dequeue() (value interface{}, ok bool)
Peek() (value interface{}, ok bool)
containers.Container
Empty() bool
Size() int
Clear()
Values() []interface{}
String() string
containers.Container
}
4. Rozšíření s podporou generických datových typů – Go18DS
Na základě výše zmíněné knihovny GoDS byla vytvořena knihovna nazvaná Go18DS, tedy „generické datové struktury pro Go 1.18 a novější“. Pro její instalaci postačuje vytvoření souboru go.mod a přidání jednoho řádku do tohoto souboru:
module x go 1.18 require github.com/daichi-m/go18ds v1.12.1 // indirect
V souboru go.sum se po překladu vytvoří tyto informace o závislostech:
github.com/daichi-m/go18ds v1.12.1 h1:Pjc3IApmN4qtDiovGP9MvMpIzgZle3SHUcNaA5j46bg= github.com/daichi-m/go18ds v1.12.1/go.mod h1:wc2dURUr8aMxxC4Mn5ObJGVM7uIKU8JagY4nhtonXq8=
A poté se nainstalují následující balíčky (tedy z pohledu programátorů jmenné prostory):
github.com/daichi-m/go18ds/containers github.com/daichi-m/go18ds/examples/arraylist github.com/daichi-m/go18ds/examples/arraystack github.com/daichi-m/go18ds/examples/avltree github.com/daichi-m/go18ds/examples/binaryheap github.com/daichi-m/go18ds/examples/btree github.com/daichi-m/go18ds/examples/customcomparator github.com/daichi-m/go18ds/examples/doublylinkedlist github.com/daichi-m/go18ds/examples/enumerablewithindex github.com/daichi-m/go18ds/examples/enumerablewithkey github.com/daichi-m/go18ds/examples/godsort github.com/daichi-m/go18ds/examples/hashbidimap github.com/daichi-m/go18ds/examples/hashmap github.com/daichi-m/go18ds/examples/hashset github.com/daichi-m/go18ds/examples/iteratorwithindex github.com/daichi-m/go18ds/examples/iteratorwithkey github.com/daichi-m/go18ds/examples/linkedhashmap github.com/daichi-m/go18ds/examples/linkedhashset github.com/daichi-m/go18ds/examples/linkedliststack github.com/daichi-m/go18ds/examples/redblacktree github.com/daichi-m/go18ds/examples/redblacktreeextended github.com/daichi-m/go18ds/examples/serialization github.com/daichi-m/go18ds/examples/singlylinkedlist github.com/daichi-m/go18ds/examples/treebidimap github.com/daichi-m/go18ds/examples/treemap github.com/daichi-m/go18ds/examples/treeset github.com/daichi-m/go18ds/lists github.com/daichi-m/go18ds/lists/arraylist github.com/daichi-m/go18ds/lists/doublylinkedlist github.com/daichi-m/go18ds/lists/singlylinkedlist github.com/daichi-m/go18ds/maps github.com/daichi-m/go18ds/maps/hashbidimap github.com/daichi-m/go18ds/maps/hashmap github.com/daichi-m/go18ds/maps/linkedhashmap github.com/daichi-m/go18ds/maps/treebidimap github.com/daichi-m/go18ds/maps/treemap github.com/daichi-m/go18ds/sets github.com/daichi-m/go18ds/sets/hashset github.com/daichi-m/go18ds/sets/linkedhashset github.com/daichi-m/go18ds/sets/treeset github.com/daichi-m/go18ds/stacks github.com/daichi-m/go18ds/stacks/arraystack github.com/daichi-m/go18ds/stacks/linkedliststack github.com/daichi-m/go18ds/trees github.com/daichi-m/go18ds/trees/avltree github.com/daichi-m/go18ds/trees/binaryheap github.com/daichi-m/go18ds/trees/btree github.com/daichi-m/go18ds/trees/redblacktree github.com/daichi-m/go18ds/utils
5. Generické rozhraní Container a generická funkce Comparator
Všechny datové struktury definované v knihovně Go18DS jsou založeny na rozhraní nazvaném Container, které (přesněji řečeno jeho veřejná část) vypadá následovně:
type Container[T any] interface {
Empty() bool
Size() int
Clear()
Values() []T
}
Dalším důležitým typem definovaným v knihovně Go18DS je typ Comparator s předpisem funkce určené pro porovnání dvou hodnot. Konkrétní implementace komparátoru se používá například při řazení prvků atd.:
type Comparator func[T comparable](a, b T) int
V knihovně Go18DS taktéž nalezneme tři konkrétní implementace komparátorů, jejichž význam je patrný z hlaviček jejich funkcí:
func StringComparator(a, b string) int
func NumberComparator[T Number](a, b T) int
func TimeComparator(a, b interface{}) int
6. Datová struktura arraylist, jednosměrně a obousměrně vázané seznamy
Prvním kontejnerem, jímž se budeme v dnešním článku zabývat, je seznam neboli list. Všechny dostupné implementace seznamů splňují (satisfy) generické rozhraní nazvané jednoduše List, které vypadá takto:
type List[T comparable] interface {
Get(index int) (T, bool)
Remove(index int)
Add(values ...T)
Contains(values ...T) bool
Sort(comparator utils.Comparator[T])
Swap(index1, index2 int)
Insert(index int, values ...T)
Set(index int, value T)
}
Seznamy popsané rozhraním nazvaným List existují v knihovně Go18DS ve třech implementacích:
- ArrayList: seznam postavený nad polem, které se může realokovat, pokud počet prvků překročí kapacitu pole
- SinglyLinkedList: lineárně jednosměrně vázaný seznam
- DoublyLinkedList: obousměrně vázaný seznam
U všech seznamů máme k dispozici iterátor (List.Iterator), který se používá takto:
iterator := list.Iterator()
for iterator.Next() {
index, value := iterator.Index(), iterator.Value()
fmt.Printf("item #%d == %s\n", index, value)
}
7. Rozdíly mezi jednotlivými implementacemi seznamů
Jednotlivé implementace seznamů se od sebe pochopitelně liší jak svoji vnitřní strukturou, tak i odlišnou časovou složitostí některých operací. Rozdíly v časové složitosti jsou naznačeny v následující tabulce:
| Implementace | Přístup k prvku | Insert | Append | Iterace vpřed | Iterace vzad |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1)-O(n) | O(1) | O(1) |
| SinglyLinkedList | O(n) | O(1) | O(n) | O(1) | O(n) |
| DoublyLinkedList | O(n) | O(1) | O(1) | O(1) | O(1) |
8. Konstrukce seznamů, přidání prvků do seznamů
Podívejme se nyní na způsob vytvoření nového seznamu s vložením prvků do seznamu přímo v konstruktoru:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]("a", "b", "c")
fmt.Println(l)
}
Výsledek:
ArrayList a, b, c
Na konec seznamu lze nové prvky vkládat metodou Add. Povšimněte si, že je možné jediným zavoláním Add do seznamu vložit i větší množství prvků (díky deklaraci s …):
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]("a", "b", "c")
fmt.Println(l)
l.Add("a")
fmt.Println(l)
l.Add("b", "c")
fmt.Println(l)
}
Tentokrát s výsledkem:
ArrayList a, b, c ArrayList a, b, c, a ArrayList a, b, c, a, b, c
9. Typově bezpečné kontejnery
Díky tomu, že všechny kontejnery v knihovně Go18DS jsou vytvořeny na základě generických datových typů, jedná se o typově zabezpečené kontejnery, které například nedovolí, aby se do seznamu určeného pro uchovávání řetězců vložila celá čísla:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string](1, 2, 3)
fmt.Println(l)
}
Tato chyba je detekována již při pokusu o překlad programu:
$ go run arraylist03.go # command-line-arguments ./arraylist03.go:10:29: cannot use 1 (untyped int constant) as string value in argument to arraylist.New[string] ./arraylist03.go:10:32: cannot use 2 (untyped int constant) as string value in argument to arraylist.New[string] ./arraylist03.go:10:35: cannot use 3 (untyped int constant) as string value in argument to arraylist.New[string]
Totéž platí i při pokusu o přidání nových prvků do již zkonstruovaného seznamu:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]("a", "b", "c")
fmt.Println(l)
l.Add(1)
fmt.Println(l)
l.Add(2, 3)
fmt.Println(l)
}
S výsledkem:
$ go run arraylist04.go # command-line-arguments ./arraylist04.go:13:8: cannot use 1 (untyped int constant) as string value in argument to l.Add ./arraylist04.go:16:8: cannot use 2 (untyped int constant) as string value in argument to l.Add ./arraylist04.go:16:11: cannot use 3 (untyped int constant) as string value in argument to l.Add
10. Vymazání seznamu, test na existenci prvku, přečtení prvku ze seznamu
Jak je již z pohledu na metody předepsané v rozhraních Container a List patrné, je možné se seznamy (resp. přesněji řečeno s jejich prvky) provádět i další operace. Pro vymazání všech prvků se používá metoda Clear:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]()
fmt.Println(l)
l.Add("a")
fmt.Println(l)
l.Add("b", "c")
fmt.Println(l)
l.Clear()
fmt.Println(l)
}
Výsledky:
ArrayList ArrayList a ArrayList a, b, c ArrayList
Test, zda seznam obsahuje prvek s určitou hodnotou, je implementován v metodě Contains, což si opět vyzkoušíme:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func testContains(l *arraylist.List[string]) {
fmt.Println("List:", l)
for _, c := range []string{"a", "b", "c", "x"} {
fmt.Printf("Contains '%s': %t\n", c, l.Contains(c))
}
fmt.Println()
}
func main() {
l := arraylist.New[string]()
testContains(l)
l.Add("a")
testContains(l)
l.Add("b", "c")
testContains(l)
l.Clear()
testContains(l)
}
Výsledky:
List: ArrayList Contains 'a': false Contains 'b': false Contains 'c': false Contains 'x': false List: ArrayList a Contains 'a': true Contains 'b': false Contains 'c': false Contains 'x': false List: ArrayList a, b, c Contains 'a': true Contains 'b': true Contains 'c': true Contains 'x': false List: ArrayList Contains 'a': false Contains 'b': false Contains 'c': false Contains 'x': false
Naproti tomu slouží metoda pojmenovaná Get pro přečtení prvku s daným indexem ze seznamu. Navíc se vrací i příznak, zda byl prvek nalezen či nikoli (lze tedy bez pádu překročit meze dané počtem prvků v seznamech):
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func testGet(l *arraylist.List[string]) {
fmt.Println("List:", l)
for i := -1; i < l.Size()+1; i++ {
value, found := l.Get(i)
if found {
fmt.Printf("Item %d = '%s'\n", i, value)
} else {
fmt.Printf("Item %d not found\n", i)
}
}
fmt.Println()
}
func main() {
l := arraylist.New[string]()
testGet(l)
l.Add("a")
testGet(l)
l.Add("b", "c")
testGet(l)
l.Clear()
testGet(l)
}
S výsledky:
List: ArrayList Item -1 not found Item 0 not found List: ArrayList a Item -1 not found Item 0 = 'a' Item 1 not found List: ArrayList a, b, c Item -1 not found Item 0 = 'a' Item 1 = 'b' Item 2 = 'c' Item 3 not found List: ArrayList Item -1 not found Item 0 not found
11. Vymazání prvku či prvků ze seznamu
Vymazání prvku ze seznamu zajišťuje metoda nazvaná Remove. Zajímavé je, že je možné se pokusit o vymazání neexistujících prvků, a to bez vyvolání chyby. Ostatně to je ukázáno i v následujícím příkladu, kde evidentně voláme Remove s nekorektními indexy:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]()
fmt.Println(l)
l.Add("a")
fmt.Println(l)
l.Add("b", "c")
fmt.Println(l)
for i := 0; i < 5; i++ {
l.Remove(0)
fmt.Println(l)
}
}
S výsledky:
ArrayList ArrayList a ArrayList a, b, c ArrayList b, c ArrayList c ArrayList ArrayList ArrayList
12. Operace Swap a Sort
Mezi další zajímavé operace prováděné nad seznamy patří zejména operace Swap zajišťující prohození dvou prvků seznamu. Jedná se obecně o velmi efektivní operaci, která je navíc interně použita i operací nazvanou Sort určenou pro seřazení prvků v seznamu na základě zadaného kritéria – to je reprezentováno komparátorem, tedy funkcí, která porovná dva prvky a vrátí informaci o tom, který z prvků je „větší“ a zda si nejsou oba prvky rovny.
Opět platí, že operaci Swap lze zavolat i s neexistujícím indexem prvku:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
)
func main() {
l := arraylist.New[string]("foo", "bar", "baz")
fmt.Println(l)
fmt.Println()
l.Swap(0, 1)
fmt.Println(l)
fmt.Println()
l.Swap(1, 2)
fmt.Println(l)
fmt.Println()
l.Swap(2, 3)
fmt.Println(l)
fmt.Println()
}
S výsledky:
ArrayList foo, bar, baz ArrayList bar, foo, baz ArrayList bar, baz, foo ArrayList bar, baz, foo
V dalším demonstračním příkladu je ukázáno, jak lze seřadit prvky – řetězce v seznamu (správného typu). Použijeme přitom standardně dodávaný StringComparator:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/arraylist"
"github.com/daichi-m/go18ds/utils"
)
func main() {
l := arraylist.New[string]("zoo", "aleph", "foo", "bar", "baz")
fmt.Println(l)
fmt.Println()
l.Sort(utils.StringComparator)
fmt.Println(l)
}
Původní i seřazený seznam vypadá takto:
ArrayList zoo, aleph, foo, bar, baz ArrayList aleph, bar, baz, foo, zoo
13. Jednosměrně a obousměrně vázané seznamy, iterátor nad seznamy
Všechny operace, které byly popsány v předchozích kapitolách, je možné využít i pro jednosměrně popř. obousměrně vázané seznamy, které se od sebe odlišují, jak již víme, interním způsobem uložení prvků a taktéž odlišnými časovými složitostmi některých operací. Ukázky práce se seznamy různých typů naleznete v demonstračních příkladech zmíněných v devatenácté kapitole.
Podívejme se nyní na způsob procházení všemi prvky seznamu s využitím iterátoru. Pro jednoduchost budeme pracovat se seznamem, do kterého se ukládají řetězce, ovšem naprosto stejný způsob bude možné použít i pro seznamy s prvky jiných typů:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/lists/singlylinkedlist"
)
func main() {
l := singlylinkedlist.New[string]("zoo", "aleph", "foo", "bar", "baz")
it := l.Iterator()
for it.Next() {
value := it.Value()
fmt.Printf("%3s \t %T\n", value, value)
}
}
Tento příklad po svém spuštění vypíše všechny prvky získané ze seznamu, včetně jejich typů:
zoo string aleph string foo string bar string baz string
14. Zásobníky
Dalším užitečným typem kontejneru, s nímž se v knihovně Go18DS setkáme, jsou seznamy neboli stack(s). Všechny dostupné implementace seznamu jsou založeny na rozhraní se jménem Stack:
type Stack[T comparable] interface {
Push(value T)
Pop() (value T, ok bool)
Peek() (value T, ok bool)
}
Existují přitom dvě konkrétní implementace zásobníků – LinkedListStack a ArrayStack, které se od sebe odlišují tím, jakým způsobem jsou jednotlivé prvky na zásobníku uloženy a jak může zásobník růst nebo se naopak zmenšovat – což je v případě interního použití jednosměrně vázaného seznamu rychlejší operace, kterou je však možné v případě využití polí poměrně dobře amortizovat.
15. Základní operace nad zásobníky
V této kapitole si na několika příkladech ukážeme provedení základních operací nad zásobníky. Základem je operace push určená pro vložení nového prvku na vrchol zásobníku (TOS=Top Of Stack):
package main
import (
"fmt"
"github.com/daichi-m/go18ds/stacks/arraystack"
)
func main() {
stack := arraystack.New[string]()
fmt.Println(stack)
stack.Push("foo")
fmt.Println(stack)
stack.Push("bar")
fmt.Println(stack)
stack.Push("baz")
fmt.Println(stack)
}
Výsledky získané po spuštění tohoto programu:
ArrayStack ArrayStack foo ArrayStack foo, bar ArrayStack foo, bar, baz
Pro přečtení prvku z vrcholu zásobníku společně s odstraněním tohoto prvku ze zásobníku slouží operace Pop. Ta současně vrací příznak, zda není zásobník prázdný:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/stacks/arraystack"
)
func main() {
stack := arraystack.New[string]()
stack.Push("foo")
stack.Push("bar")
stack.Push("baz")
for {
value, exists := stack.Pop()
if exists {
fmt.Println(value)
} else {
break
}
}
}
Výsledky získané po spuštění tohoto programu:
baz bar foo
Naproti tomu operace Peek pouze přečte obsah prvku na vrcholu zásobníku bez odstranění tohoto prvku. Současně tato metoda vrací příznak, zda není zásobník prázdný:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/stacks/arraystack"
)
func main() {
stack := arraystack.New[string]()
stack.Push("foo")
stack.Push("bar")
stack.Push("baz")
for i := 0; i < 10; i++ {
value, exists := stack.Peek()
fmt.Println(i, value, exists)
stack.Pop()
}
}
Výsledky získané po spuštění tohoto programu:
0 baz true 1 bar true 2 foo true 3 false 4 false 5 false 6 false 7 false 8 false 9 false
Použít můžeme i metody Size() a Empty() pro zjištění počtu prvků uložených na zásobníku a pro zjištění, zda je zásobník prázdný či nikoli:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/stacks/arraystack"
)
func main() {
stack := arraystack.New[string]()
stack.Push("foo")
stack.Push("bar")
stack.Push("baz")
for {
value, exists := stack.Pop()
if exists {
fmt.Println(value, stack.Size(), stack.Empty())
} else {
break
}
}
}
Výsledky získané po spuštění tohoto programu:
baz 2 false bar 1 false foo 0 true
16. Praktické použití zásobníku – převod aritmetického výrazu do postfixové notace
Podívejme se nyní, jakým způsobem je možné převést aritmetický výraz odpovídající syntaxi programovacího jazyka Go do postfixové notace. Samotný algoritmus převodu mezi běžnou infixovou notací a notací postfixovou navrhl E. Dijkstra a nazývá se algoritmus shunting-yard (česky snad seřaďovací nádraží, konkrétně by se jednalo o nádraží vybavené úvratí). Tento algoritmus je založen na postupném načítání tokenů reprezentujících jak aritmetické/logické operace, tak i jejich operandy a popř. i volání funkcí a závorky ovlivňující prioritu prováděných operací. Tyto tokeny jsou v případě operandů posílány přímo na výstup, ovšem tokeny reprezentující operandy, závorky a funkce jsou zpracovávány odlišně – buď jsou odloženy na zásobník (jehož reálnou obdobou je právě úvrať na seřaďovacím nádraží) nebo naopak zajistí postupné vyzvedávání starších operandů z tohoto zásobníku a jejich poslání na výstup. Úplný popis tohoto algoritmu, který naleznete například zde, obsahuje i rozlišení operátorů asociativních zleva a zprava.
Výše popsaný algoritmus shunting-yard můžeme zjednodušit v případě, že není nutné rozlišit mezi použitím operátorů asociativních zleva a zprava. Příkladem je opět programovací jazyk Go, který v sadě základních aritmetických operátorů má pouze operátory asociativní zleva (není zde například operátor pro umocnění atd.). Navíc může algoritmus pracovat přímo nad tokeny získanými již v tomto seriálu popsanou tokenizací – tedy výsledkem práce balíčku nazvaného go/scanner (a jak již víme: bez vracení tokenů). Jedna z možných implementací algoritmu shunting-yard tedy může vypadat následovně. Všechny části jsou poměrně dopodrobna okomentovány:
package main
import (
"fmt"
"go/scanner"
"go/token"
"github.com/daichi-m/go18ds/stacks/arraystack"
)
// výraz, který se má převést na RPN
const source = `
1 + 2 * (3 + x) + y * (z - 1)
`
func printStack(s *arraystack.Stack[token.Token]) {
it := s.Iterator()
for it.Next() {
value := it.Value()
fmt.Printf("%s ", value)
}
fmt.Println()
}
func toRPN(s scanner.Scanner) {
var operators = map[token.Token]int{
token.MUL: 2,
token.QUO: 2,
token.REM: 2,
token.ADD: 1,
token.SUB: 1,
}
stack := arraystack.New[token.Token]()
// postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
for {
_, tok, lit := s.Scan()
switch tok {
case token.INT:
// celé číslo přímo vypsat
fallthrough
case token.FLOAT:
// číslo s plovoucí čárkou přímo vypsat
fallthrough
case token.IDENT:
// identifikátor taktéž přímo vypsat
fmt.Printf("%v ", lit)
case token.LPAREN:
// levá závorka se uloží na zásobník (bez výpisu)
stack.Push(tok)
case token.RPAREN:
// pravá závorka zahájí zpracování zásobníku až do první nalezené levé závorky
var tok token.Token
for {
// přečtení prvku ze zásobníku - operace POP
tok, _ = stack.Pop()
if tok == token.LPAREN {
// odstranění levé závorky
break
}
// ostatní tokeny získané ze zásobníku se vypíšou
fmt.Printf("%v ", tok)
}
case token.EOF:
// speciální token reprezentující konec tokenizace
break loop
default:
priority1, isOperator := operators[tok]
if isOperator {
// průchod prvky na zásobníku
for !stack.Empty() {
// operace TOP
tok, _ := stack.Peek()
// získat prioritu operátoru přečteného ze zásobníku
priority2 := operators[tok]
if priority1 > priority2 {
// větší priorita nového operátoru -> konec
// (pouze ho později uložíme na zásobník)
break
}
// menší či stejná priorita nového operátoru ->
// vypsat předchozí operátor nalezený na zásobníku
// a odstranit tento operátor ze zásobníku
stack.Pop()
fmt.Printf("%s ", tok)
}
// uložit nově načtený operátor na zásobník
stack.Push(tok)
}
}
}
// tisk obsahu zásobníku
printStack(stack)
}
func main() {
// objekt představující scanner
var s scanner.Scanner
// struktura reprezentující množinu zdrojových kódů
fset := token.NewFileSet()
// přidání informace o zdrojovém kódu
file := fset.AddFile("", fset.Base(), len(source))
// inicializace scanneru
s.Init(file, []byte(source), nil, scanner.ScanComments)
// převod výrazu do RPN
toRPN(s)
}
Po spuštění tohoto demonstračního příkladu se zobrazí informace o postupně zpracovávaném tokenu i o obsahu zásobníku operandů:
1 : 1 2 : 2 1 + : 3 2 : 2 3 3 : 3 2 3 * : 6 3 8 : 8 6 3 + : 14 3 * : 42 Result: 42
17. Množiny
Další často používanou generickou datovou strukturou jsou množiny představované rozhraním Set:
type Set[T comparable] interface {
Add(elements ...T)
Remove(elements ...T)
Contains(elements ...T) bool
}
Pro toto rozhraní existují tři implementace:
- HashSet: založeno na hešovacích tabulkách
- TreeSet: založeno na RB-stromech
- LinkedHashSet: zachovává pořadí prvků
Jednoduchý příklad použití množin je ukázán v navazující kapitole.
18. Eratosthenovo síto
Jako příklad praktičtějšího použití množin jsem vybral známý algoritmus určený pro hledání prvočísel s využitím Eratosthenova síta. Samozřejmě existuje mnoho více či méně optimalizovaných implementací tohoto algoritmu; některé jsou zmíněny na stránce Rosetta Code. My si ukážeme tu nejprimitivnější implementaci spočívající v postupném odstraňování celočíselných násobků prvočísel z množiny, která původně obsahovala všechna celá čísla od 2 do 1000.
Zdrojový kód implementace Eratosthenova síta postavený na množinách podporovaných knihovnou Go18DS vypadá následovně:
package main
import (
"fmt"
"github.com/daichi-m/go18ds/sets/linkedhashset"
)
const maxPrime = 1000
func printSet(set *linkedhashset.Set[int]) {
iterator := set.Iterator()
for iterator.Next() {
index, value := iterator.Index(), iterator.Value()
fmt.Printf("%3d ", value)
if index%10 == 9 {
fmt.Println()
}
}
fmt.Println()
}
func main() {
primes := linkedhashset.New[int]()
for n := 2; n < maxPrime; n++ {
primes.Add(n)
}
for n := 2; n < maxPrime/2; n++ {
if primes.Contains(n) {
for k := 2 * n; k < maxPrime; k += n {
primes.Remove(k)
}
}
}
printSet(primes)
}
Tento příklad by měl po svém spuštění vypsat všechna prvočísla nalezená v intervalu 0 až 1000:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
19. Repositář s demonstračními příklady
Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/go-root (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně stovku kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady, které naleznete v následující tabulce:
| # | Příklad/soubor | Stručný popis | Cesta |
|---|---|---|---|
| 1 | arraylist01.go | konstrukce seznamu s přidáním prvků pro seznam typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist01.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/arraylist02.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/arraylist03.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/arraylist04.go |
| 5 | arraylist05.go | vymazání všech prvků ze seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist05.go |
| 6 | arraylist06.go | test na existenci prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist06.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/arraylist07.go |
| 8 | arraylist08.go | odstranění prvků se zadaným indexem ze seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist08.go |
| 9 | arraylist09.go | operace Swap – prohození dvou prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist09.go |
| 10 | arraylist10.go | operace Sort – setřídění prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist10.go |
| 11 | arraylist11.go | implementace iterátoru nad seznamem typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist11.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/singlylinkedlist01.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/singlylinkedlist02.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/singlylinkedlist03.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/singlylinkedlist04.go |
| 16 | singlylinkedlist05.go | vymazání všech prvků ze seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist05.go |
| 17 | singlylinkedlist06.go | test na existenci prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist06.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/singlylinkedlist07.go |
| 19 | singlylinkedlist08.go | odstranění prvků se zadaným indexem ze seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist08.go |
| 20 | singlylinkedlist09.go | operace Swap – prohození dvou prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist09.go |
| 21 | singlylinkedlist10.go | operace Sort – setřídění prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist10.go |
| 22 | singlylinkedlist11.go | implementace iterátoru nad seznamem typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist11.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/doublylinkedlist01.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/doublylinkedlist02.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/doublylinkedlist03.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/doublylinkedlist04.go |
| 27 | doublylinkedlist05.go | vymazání všech prvků ze seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist05.go |
| 28 | doublylinkedlist06.go | test na existenci prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist06.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/doublylinkedlist07.go |
| 30 | doublylinkedlist08.go | odstranění prvků se zadaným indexem ze seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist08.go |
| 31 | doublylinkedlist09.go | operace Swap – prohození dvou prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist09.go |
| 32 | doublylinkedlist10.go | operace Sort – setřídění prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist10.go |
| 33 | doublylinkedlist11.go | implementace iterátoru nad seznamem typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist11.go |
| 34 | arraystack01.go | operace Push nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack01.go |
| 35 | arraystack02.go | operace Pop nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack02.go |
| 36 | arraystack03.go | operace Peek nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack03.go |
| 37 | arraystack04.go | metody Size a Empty nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack04.go |
| 38 | linkedliststack01.go | operace Push nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack01.go |
| 39 | linkedliststack02.go | operace Pop nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack02.go |
| 40 | linkedliststack03.go | operace Peek nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack03.go |
| 41 | linkedliststack04.go | metody Size a Empty nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack04.go |
| 42 | stack_rpn.go | vyhodnocení výrazu zapsaného v RPN | https://github.com/tisnik/go-root/blob/master/article92/stack_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/stack_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/erasthotenes.go |
20. Odkazy na Internetu
- Genfuncs – implements various functions utilizing Go's Generics to help avoid writing boilerplate code
https://github.com/nwillc/genfuncs - Go18DS (Go 1.18+ Data Structures)
https://github.com/daichi-m/go18ds - TreeMap v2
https://github.com/igrmk/treemap - Fp-go is a collection of Functional Programming helpers powered by Golang 1.18+ generics
https://github.com/repeale/fp-go - The Go Programming Language Specification
https://go.dev/ref/spec - Generics in Go
https://bitfieldconsulting.com/golang/generics - Tutorial: Getting started with generics
https://go.dev/doc/tutorial/generics - Type parameters in Go
https://bitfieldconsulting.com/golang/type-parameters - Go Data Structures: Binary Search Tree
https://flaviocopes.com/golang-data-structure-binary-search-tree/ - Gobs of data
https://blog.golang.org/gobs-of-data - 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 - Go 1.18 Release Notes
https://golang.org/doc/go1.18 - Go 1.17 Release Notes
https://golang.org/doc/go1.17 - Go 1.16 Release Notes
https://golang.org/doc/go1.16 - Go 1.15 Release Notes
https://golang.org/doc/go1.15 - Go 1.14 Release Notes
https://golang.org/doc/go1.14 - Go 1.13 Release Notes
https://golang.org/doc/go1.13 - Go 1.12 Release Notes
https://golang.org/doc/go1.12 - Go 1.11 Release Notes
https://golang.org/doc/go1.11 - Go 1.11 Release Notes
https://golang.org/doc/go1.11 - Go 1.10 Release Notes
https://golang.org/doc/go1.10 - Go 1.9 Release Notes
https://golang.org/doc/go1.9 - Go 1.8 Release Notes
https://golang.org/doc/go1.8 - A Proposal for Adding Generics to Go
https://go.dev/blog/generics-proposal - Proposal: Go should have generics
https://github.com/golang/proposal/blob/master/design/15292-generics.md - Know Go: Generics (Kniha)
https://bitfieldconsulting.com/books/generics - Go 1.18 Generics based slice package
https://golangexample.com/go-1–18-generics-based-slice-package/ - The missing slice package
https://github.com/ssoroka/slice - 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/ - 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/ - Generické datové typy v jazyce Go?
https://www.root.cz/clanky/genericke-datove-typy-v-jazyce-go/ - GoDS (Go Data Structures)
https://github.com/emirpasic/gods
