Obousměrná fronta (deque) v programovacím jazyku Go

3. 11. 2022

Doba čtení: 27 minut

Líbí se vám článek?
Podpořte redakci

V jazyku Go nalezneme podporu pro několik datových kontejnerů. Jedná se o pole, řezy a o mapy. Ovšem zdaleka zde nenalezneme všechny potřebné datové kontejnery. Jedním z nich je kontejner nazvaný deque neboli obousměrná fronta.

Obsah

1. Obousměrná fronta – deque – v programovacím jazyku Go

2. Instalace balíčku deque

3. Konstruktor obousměrné fronty s uvedením typů prvků

4. Operace push back, růst počtu prvků a kapacity fronty

5. Algoritmus pro zvýšení kapacity fronty při přidávání prvků

6. Čtení prvků z čela (začátku) fronty

7. Oboustranná fronta ve funkci klasické fronty: dvojice operací push back + pop front a push front + pop back

8. Oboustranná fronta ve funkci klasického zásobníku: dvojice operací push back + pop back a push front + pop front

9. Praktické využití zásobníku – výpočet výrazu zapsaného v RPN

10. Rotace prvků v oboustranné frontě

11. Časová složitost operací prováděných s oboustrannou frontou

12. Implementace benchmarku

13. Výsledky benchmarků pro krátké obousměrné fronty

14. Výsledky benchmarků pro fronty s větším počtem prvků

15. Závěrečné zhodnocení

16. Příloha 1: CSV soubor s výsledky benchmarků

17. Příloha 2: Názvy operací s obousměrnou frontou

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

19. Odkazy na Internetu

1. Obousměrná fronta – deque – v programovacím jazyku Go

V programovacím jazyku Go nalezneme podporu pro několik datových kontejnerů. Jedná se především o pole, řezy (tedy o „pohledy“ na pole) a o mapy (nepřímo vlastně i o kanály), které jsou ve standardní knihovně doplněny o několik dalších kontejnerů. Ovšem zdaleka zde nenalezneme všechny potřebné datové kontejnery. Jedním z velmi užitečných kontejnerů je kontejner nazvaný deque, což je jedna z možných implementací obousměrné fronty (double ended queue). Jedná se tedy o kontejner, který podporuje operace připojení nového prvku k oběma koncům fronty popř. naopak k získání (a popřípadě i k odstranění) prvku z libovolného konce. Podporovány jsou ovšem i další dvě operace, které typicky u implementací „čistých“ obousměrných front nenajdeme. Jedná se o operaci určenou pro rotaci prvků uložených ve frontě a taktéž o operaci, která dokáže do fronty vložit prvek na určené místo.

Poznámka: obousměrnou frontu je možné pochopitelně použít i ve funkci zásobníku (stack), což si ostatně ukážeme v navazujících kapitolách.

Pro programovací jazyk Go vzniklo hned několik implementací obousměrné fronty. Jednu z těchto implementací nalezneme v repositáři https://github.com/gammazero/deque. Tato implementace je interně založena na ring bufferu; jedná se tedy o cyklickou frontu, jejíž kapacita je v případě potřeby zvětšována. Základní operace s obousměrnou frontou jsou optimalizovány jak na rychlost, tak i na spotřebu paměti – nedochází tedy například k realokaci a přesunu prvků. Ovšem jak uvidíme dále, netypické operace, například operace Insert, trvá velmi dlouho a je lineárně závislá na počtu prvků ve frontě.

2. Instalace balíčku deque

Samotná instalace balíčku deque je jednoduchá, protože postačuje použít příkaz:

$ go get github.com/gammazero/deque

Alternativně je možné vytvořit prázdný projekt příkazem:

$ go mod init deque-demo

A následně do nově vzniklého projektu vložit následující zdrojový kód, který balíček deque importuje a následně i používá:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        fmt.Println(q))
}

Při překladu (resp. přesněji řečeno při prvním překladu) si systém modulů programovacího jazyka Go automaticky vyžádá instalaci balíčku:

$ go get -v github.com/gammazero/deque
 
go: downloading github.com/gammazero/deque v0.2.1
go: added github.com/gammazero/deque v0.2.1

Po úspěšné instalaci by měl automaticky vygenerovaný soubor go.sum obsahovat následující dvojici řádků:

github.com/gammazero/deque v0.2.1 h1:qSdsbG6pgp6nL7A0+K/B7s12mcCY/5l5SIUpMOl+dC0=
github.com/gammazero/deque v0.2.1/go.mod h1:LFroj8x4cMYCukHJDbxFCkT+r9AndaJnFMuZDV34tuU=

Poznámka: povšimněte si, že tento balíček závisí pouze na standardní knihovně jazyka Go, takže se nevyžadují žádné tranzitivní závislosti. To je v ekosystému Go dnes již rarita :-)

3. Konstruktor obousměrné fronty s uvedením typů prvků

Balíček gammazero/deque využívá generické datové typy přidané do Go 1.18, takže již v definici proměnné, která reprezentuje obousměrnou frontu, je možné specifikovat typy prvků, které budou ve frontě uloženy:

var q deque.Deque[int]

Fronta má určitou délku, což je počet prvků, které jsou v ní uloženy, a taktéž kapacitu, tj. celkový počet prvků, které je možné do fronty uložit, aniž by se musela alokovat nová paměť. Tyto dvě důležité informace o frontě získáme metodami Deque.Len() a Deque.Cap():

fmt.Println("Deque length:  ", q.Len())
fmt.Println("Deque capacity:", q.Cap())

Dokonce je možné si nechat vypsat všechny informace o frontě pouhým výpisem hodnoty příslušné proměnné:

fmt.Println("Deque value:   ", q)

Všechny tři výše zmíněné informace o prázdné frontě s výchozí kapacitou jsou vypsány tímto příkladem:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        fmt.Println("Deque length:  ", q.Len())
        fmt.Println("Deque capacity:", q.Cap())
        fmt.Println("Deque value:   ", q)
}

Po překladu a spuštění se zobrazí následující údaje:

Deque length:   0
Deque capacity: 0
Deque value:    {[] 0 0 0 0}

Poznámka: význam všech čtyřech nul, z nichž každá nese odlišný typ informace, bude popsán dále.

4. Operace push back, růst počtu prvků a kapacity fronty

Jednou ze základních operací s obousměrnou frontou jsou operace pro přidání prvku na začátek fronty nebo na její konec. Pro přidání prvku na konec fronty slouží operace nazvaná push back, která je představována metodou Deque.PushBack(). Této metodě se pouze předá prvek, jenž se má do fronty přidat. Současně budeme sledovat délku fronty i její kapacitu:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
                fmt.Println("Deque length:  ", q.Len())
                fmt.Println("Deque capacity:", q.Cap())
                fmt.Println("Deque value:   ", q)
                fmt.Println()
        }
}

Povšimněte si, jak se kapacita již po vložení prvního prvku ustálila na hodnotě 16 (mocnina dvou). Zajímavá je taktéž poslední čtveřice číslic, která určuje index prvního prvku, index posledního prvku, délku fronty (počet prvků) i její kapacitu. V demonstračním příkladu z předchozí kapitoly byly všechny čtyři hodnoty nulové, nyní se již mění:

Deque length:   1
Deque capacity: 16
Deque value:    {[101 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 1 1 16}
 
Deque length:   2
Deque capacity: 16
Deque value:    {[101 102 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 2 2 16}
 
Deque length:   3
Deque capacity: 16
Deque value:    {[101 102 103 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 3 3 16}
 
Deque length:   4
Deque capacity: 16
Deque value:    {[101 102 103 104 0 0 0 0 0 0 0 0 0 0 0 0] 0 4 4 16}
 
Deque length:   5
Deque capacity: 16
Deque value:    {[101 102 103 104 105 0 0 0 0 0 0 0 0 0 0 0] 0 5 5 16}
 
Deque length:   6
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 0 0 0 0 0 0 0 0 0 0] 0 6 6 16}
 
Deque length:   7
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 0 0 0 0 0 0 0 0 0] 0 7 7 16}
 
Deque length:   8
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 0 0 0 0 0 0 0 0] 0 8 8 16}
 
Deque length:   9
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 0 0 0 0 0 0 0] 0 9 9 16}
 
Deque length:   10
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 0 10 10 16}

5. Algoritmus pro zvýšení kapacity fronty při přidávání prvků

Pojďme si nyní vyzkoušet, jak se vlastně počítá nová kapacita fronty ve chvíli, kdy již není možné do stávající fronty přidat další prvek. Pro tento účel použijeme demonstrační příklad, v němž postupně do fronty vložíme 1000 prvků a (opět postupně) budeme vypisovat její délku a kapacitu:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        fmt.Println("Length Capacity")
        for i := 1; i <= 1000; i++ {
                q.PushBack(i)
                fmt.Printf("%5d %5d\n", q.Len(), q.Cap())
        }
}

Následující výpis je zkrácen a jsou ukázány jen ta místa, v nichž se mění kapacita:

Length Capacity
    1    16
    2    16
    3    16
...
...
...
   15    16
   16    16
   17    32
   18    32
...
...
...
   31    32
   32    32
   33    64
   34    64
...
...
...
  511   512
  512   512
  513  1024
  514  1024
...
...
...

Poznámka: samotný algoritmus pro zvětšení kapacity fronty je implementován následujícím relativně jednoduchým způsobem:

// growIfFull resizes up if the buffer is full.
func (q *Deque[T]) growIfFull() {
        if q.count != len(q.buf) {
                return
        }
        if len(q.buf) == 0 {
                if q.minCap == 0 {
                        q.minCap = minCapacity
                }
                q.buf = make([]T, q.minCap)
                return
        }
        q.resize()
}
 
// resize resizes the deque to fit exactly twice its current contents. This is
// used to grow the queue when it is full, and also to shrink it when it is
// only a quarter full.
func (q *Deque[T]) resize() {
        newBuf := make([]T, q.count>>1)
        if q.tail > q.head {
                copy(newBuf, q.buf[q.head:q.tail])
        } else {
                n := copy(newBuf, q.buf[q.head:])
                copy(newBuf[n:], q.buf[:q.tail])
        }

        q.head = 0
        q.tail = q.count
        q.buf = newBuf
}

6. Čtení prvků z čela (začátku) fronty

V následujícím demonstračním příkladu je ukázáno, jakým způsobem se nejdříve fronta naplní (a to od konce, tedy operací push back) a následně se z ní postupně přečtou (a odstraní) všechny prvky, a to v tomto případě od začátku, tedy operací pop front. Povšimněte si, že čtení je prováděno v nekonečné smyčce, abychom zjistili, co se stane ve chvíli, kdy je již fronta prázdná:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
                fmt.Println("Deque length:  ", q.Len())
                fmt.Println("Deque capacity:", q.Cap())
                fmt.Println("Deque value:   ", q)
                fmt.Println()
        }
 
        fmt.Println()
 
        for true {
                fmt.Println("Pop value:     ", q.PopFront())
                fmt.Println("Deque length:  ", q.Len())
                fmt.Println("Deque capacity:", q.Cap())
                fmt.Println("Deque value:   ", q)
                fmt.Println()
        }
}

Příklad po svém spuštění nejdříve začne s naplňováním fronty:

Deque length:   1
Deque capacity: 16
Deque value:    {[101 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 1 1 16}
 
Deque length:   2
Deque capacity: 16
Deque value:    {[101 102 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 2 2 16}
 
Deque length:   3
Deque capacity: 16
Deque value:    {[101 102 103 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 3 3 16}
 
Deque length:   4
Deque capacity: 16
Deque value:    {[101 102 103 104 0 0 0 0 0 0 0 0 0 0 0 0] 0 4 4 16}
 
Deque length:   5
Deque capacity: 16
Deque value:    {[101 102 103 104 105 0 0 0 0 0 0 0 0 0 0 0] 0 5 5 16}
 
Deque length:   6
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 0 0 0 0 0 0 0 0 0 0] 0 6 6 16}
 
Deque length:   7
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 0 0 0 0 0 0 0 0 0] 0 7 7 16}
 
Deque length:   8
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 0 0 0 0 0 0 0 0] 0 8 8 16}
 
Deque length:   9
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 0 0 0 0 0 0 0] 0 9 9 16}
 
Deque length:   10
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 0 10 10 16}

Posléze se naopak začnou prvky z fronty číst a současně i odstraňovat – mimochodem se právě v tomto okamžiku bude měnit první index ze čtveřice hodnot popisujících stav fronty:

Pop value:      101
Deque length:   9
Deque capacity: 16
Deque value:    {[0 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 1 10 9 16}
 
Pop value:      102
Deque length:   8
Deque capacity: 16
Deque value:    {[0 0 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 2 10 8 16}
 
Pop value:      103
Deque length:   7
Deque capacity: 16
Deque value:    {[0 0 0 104 105 106 107 108 109 110 0 0 0 0 0 0] 3 10 7 16}
 
Pop value:      104
Deque length:   6
Deque capacity: 16
Deque value:    {[0 0 0 0 105 106 107 108 109 110 0 0 0 0 0 0] 4 10 6 16}
 
Pop value:      105
Deque length:   5
Deque capacity: 16
Deque value:    {[0 0 0 0 0 106 107 108 109 110 0 0 0 0 0 0] 5 10 5 16}
 
Pop value:      106
Deque length:   4
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 107 108 109 110 0 0 0 0 0 0] 6 10 4 16}
 
Pop value:      107
Deque length:   3
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 108 109 110 0 0 0 0 0 0] 7 10 3 16}
 
Pop value:      108
Deque length:   2
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 109 110 0 0 0 0 0 0] 8 10 2 16}
 
Pop value:      109
Deque length:   1
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 0 110 0 0 0 0 0 0] 9 10 1 16}
 
Pop value:      110
Deque length:   0
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 10 10 0 16}

Jakmile je fronta prázdná, dojde k pádu aplikace – vyvolá se panic:

panic: deque: PopFront() called on empty queue
 
goroutine 1 [running]:
github.com/gammazero/deque.(*Deque[...]).PopFront(0xc00000e018?)
        /home/ptisnovs/go/pkg/mod/github.com/gammazero/deque@v0.2.1/deque.go:110 +0x91
main.main()
        /home/ptisnovs/src/go-root/article_96/04_popfront_panic.go:23 +0x287
exit status 2

Korektní způsob detekce prázdné fronty spočívá ve využití nám již dobře známé metody Deque.Len(). Ta je použita ve druhé programové smyčce:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
                fmt.Println("Deque length:  ", q.Len())
                fmt.Println("Deque capacity:", q.Cap())
                fmt.Println("Deque value:   ", q)
                fmt.Println()
        }
 
        fmt.Println()
 
        for q.Len() > 0 {
                fmt.Println("Pop value:     ", q.PopFront())
                fmt.Println("Deque length:  ", q.Len())
                fmt.Println("Deque capacity:", q.Cap())
                fmt.Println("Deque value:   ", q)
                fmt.Println()
        }
}

Výsledek získaný po spuštění tohoto demonstračního příkladu vypadá následovně:

Deque length:   1
Deque capacity: 16
Deque value:    {[101 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 1 1 16}
 
Deque length:   2
Deque capacity: 16
Deque value:    {[101 102 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 2 2 16}
 
Deque length:   3
Deque capacity: 16
Deque value:    {[101 102 103 0 0 0 0 0 0 0 0 0 0 0 0 0] 0 3 3 16}
 
Deque length:   4
Deque capacity: 16
Deque value:    {[101 102 103 104 0 0 0 0 0 0 0 0 0 0 0 0] 0 4 4 16}
 
Deque length:   5
Deque capacity: 16
Deque value:    {[101 102 103 104 105 0 0 0 0 0 0 0 0 0 0 0] 0 5 5 16}
 
Deque length:   6
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 0 0 0 0 0 0 0 0 0 0] 0 6 6 16}
 
Deque length:   7
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 0 0 0 0 0 0 0 0 0] 0 7 7 16}
 
Deque length:   8
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 0 0 0 0 0 0 0 0] 0 8 8 16}
 
Deque length:   9
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 0 0 0 0 0 0 0] 0 9 9 16}
 
Deque length:   10
Deque capacity: 16
Deque value:    {[101 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 0 10 10 16}
 
 
 
Pop value:      101
Deque length:   9
Deque capacity: 16
Deque value:    {[0 102 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 1 10 9 16}
 
Pop value:      102
Deque length:   8
Deque capacity: 16
Deque value:    {[0 0 103 104 105 106 107 108 109 110 0 0 0 0 0 0] 2 10 8 16}
 
Pop value:      103
Deque length:   7
Deque capacity: 16
Deque value:    {[0 0 0 104 105 106 107 108 109 110 0 0 0 0 0 0] 3 10 7 16}
 
Pop value:      104
Deque length:   6
Deque capacity: 16
Deque value:    {[0 0 0 0 105 106 107 108 109 110 0 0 0 0 0 0] 4 10 6 16}
 
Pop value:      105
Deque length:   5
Deque capacity: 16
Deque value:    {[0 0 0 0 0 106 107 108 109 110 0 0 0 0 0 0] 5 10 5 16}
 
Pop value:      106
Deque length:   4
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 107 108 109 110 0 0 0 0 0 0] 6 10 4 16}
 
Pop value:      107
Deque length:   3
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 108 109 110 0 0 0 0 0 0] 7 10 3 16}
 
Pop value:      108
Deque length:   2
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 109 110 0 0 0 0 0 0] 8 10 2 16}
 
Pop value:      109
Deque length:   1
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 0 110 0 0 0 0 0 0] 9 10 1 16}
 
Pop value:      110
Deque length:   0
Deque capacity: 16
Deque value:    {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 10 10 0 16}

Poznámka: že je fronta prázdná zjistíme mj. i ze čtveřice indexů popisujících frontu 10 10 0 16. Důležité je, že oba první indexy jsou shodné (a délka je tím pádem nulová).

7. Oboustranná fronta ve funkci klasické fronty: dvojice operací push back + pop front a push front + pop back

Kontejner deque je možné využívat mnoha různými způsoby. V případě, že budeme prvky číst z opačného konce fronty, než k jakému jsou připojovány nové prvky, budeme tímto způsobem realizovat klasickou frontu, neboli queue. Jedna z možných realizací je založena na dvojici operací push back + pop front, tedy připojování prvků na konec fronty a čtení prvků (s jejich odstraněním) ze začátku fronty. Tyto dvě operace jsou v balíčku deque realizovány metodami Deque.PushBack() a Deque.PopFront():

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i*2)
                q.PushBack(101 + i*2)
                fmt.Println(q.PopFront())
        }
 
        for q.Len() > 0 {
                fmt.Println(q.PopFront())
        }
}

V demonstračním příkladu vložíme do fronty vždy dva prvky a jeden přečteme (s jeho odstraněním). Ve druhé smyčce odstraníme zbylé prvky z fronty. Povšimněte si, že nezávisle na tom, jak jsou metody PushBack a PopFront promíchány, je vždy zachováno pořadí čtených prvků:

Deque nabízí symetrické operace a tudíž je možné běžnou frontu realizovat jak již zmíněnou dvojicí operací push back + pop front, tak i operacemi push front + pop back. Z hlediska uživatele je výsledný efekt naprosto stejný a současně jsou obě alternativy i stejně rychlé (to ovšem nemusí platit vždy – záleží na konkrétní implementaci obousměrně vázané fronty):

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushFront(100 + i*2)
                q.PushFront(101 + i*2)
                fmt.Println(q.PopBack())
        }
 
        for q.Len() > 0 {
                fmt.Println(q.PopBack())
        }
}

Výsledek, tedy výpis prvků ukládaných do fronty, bude totožný s předchozím demonstračním příkladem:

8. Oboustranná fronta ve funkci klasického zásobníku: dvojice operací push back + pop back a push front + pop front

Oboustrannou frontu je pochopitelně možné využít i ve funkci zásobníku. V tomto případě je nutné prvky ukládat i číst z jednoho (libovolného) konce fronty. Můžeme tedy použít dvojici operací push back + pop back, kdy bude vrchol zásobníku umístěn vždy na konci fronty. Nebo lze naopak použít operace push front + pop front; v tomto případě bude vrchol zásobníku na začátku fronty.

Nejprve si ukažme kombinaci operací push front + pop front:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushFront(100 + i)
        }
 
        for q.Len() > 0 {
                fmt.Println(q.PopFront())
        }
}

Z výpisu je patrné, že se deque v tomto případě skutečně chová jako klasický zásobník:

Kombinace operací push back + pop back pro implementaci zásobníku:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
        }
 
        for q.Len() > 0 {
                fmt.Println(q.PopBack())
        }
}

Výsledek získaný po překladu a spuštění tohoto demonstračního příkladu bude totožný:

9. Praktické využití zásobníku – výpočet výrazu zapsaného v RPN

V tomto článku jsme se kromě dalších věcí seznámili i s tím, jakým způsobem je možné převést aritmetický či logický výraz zapsaný v klasické infixové notaci na totožný výraz, ovšem nyní zapsaný v notaci postfixové (označované taktéž zkratkou RPN). Tím se, kromě dalších věcí, odstraňuje nutnost použití závorek, které určují prioritu, protože v RPN je priorita určena způsobem řazení operandů a operátorů. Dále je v RPN zcela přesně určeno, ve kterém okamžiku se operace vykoná – konkrétně ihned poté, co je přijat její token. Z praktického pohledu je ovšem neméně důležité, že aritmetické i logické výrazy zapsané s využitím RPN se velmi snadno programově vyhodnocují, takže RPN může být použita i jako mezistupeň v interpretrech nebo například v SW kalkulačkách. A právě výpočtem výrazů zapsaných v postfixové notaci se budeme zabývat v navazujícím textu a velmi jednoduché implementaci vyhodnocovače výrazů.

O tom, jak bude realizován výpočet postfixově zapsaného aritmetického nebo logického výrazu, jsme si taktéž řekli. Celý algoritmus je založen na použití zásobníku operandů (mimochodem – na zásobníku je založen i převod z infixové notace do notace postfixové, což je zvláštní shoda). Operandy (tj. numerické hodnoty popř. hodnoty proměnných) jsou totiž nejdříve odkládány na tento zásobník a teprve poté, co je přijat operátor, jsou operandy (popř. jeden operand) získány ze zásobníku operandů, a to operací typu pop, která tyto hodnoty ze zásobníku současně i odstraní. Celý výpočet by mohl probíhat následovně:

Je načten token obsahující hodnotu symbolu z výrazu reprezentovaného v postfixové notaci (RPN). Jedná se buď o numerickou hodnotu, jméno proměnné nebo symbol operátoru (+, -, *, / a řekněme %).
V případě, že se jedná o číselnou hodnotu, je tato hodnota uložena na zásobník (nazývaný, jak již víme, zásobník operandů, protože obsahuje operandy prováděných operací).
Pokud se jedná o proměnnou, je její jméno uloženo na zásobník (při skutečném vyhodnocování výrazů lze v tomto okamžiku nahradit jméno proměnné jejím obsahem buď nyní, nebo až v dalším kroku).
V případě, že se jedná o binární operátor, jsou ze zásobníku (přesněji řečeno ze zásobníku operandů) vyzvednuty oba operandy, operace se provede a výsledek se opět uloží na zásobník. U unárního operátoru (změna znaménka atd.) se pochopitelně pracuje pouze s jediným operandem.
Na konci bude na zásobníku uložena jediná hodnota, kterou je výsledek.

Podívejme se na velmi jednoduchou implementaci tohoto algoritmu, která dokáže s využitím struktury Deque vyhodnotit výrazy s konstantami (nikoli s proměnnými). Využíváme zde Deque jako striktní zásobník:

package main
 
import (
        "fmt"
 
        "strconv"
        "strings"
 
        "github.com/gammazero/deque"
)
 
func printStack(s *deque.Deque[int]) {
        for i := 0; i < s.Len(); i++ {
                fmt.Println(s.At(i))
        }
        fmt.Println()
}
 
func main() {
        expression := "1 2 + 2 3 * 8 + *"
        terms := strings.Split(expression, " ")
        var stack deque.Deque[int]
 
        for _, term := range terms {
                switch term {
                case "+":
                        operand1 := stack.PopFront()
                        operand2 := stack.PopFront()
                        stack.PushFront(operand1 + operand2)
                        print("+ :\t")
                        printStack(&stack)
                case "-":
                        operand1 := stack.PopFront()
                        operand2 := stack.PopFront()
                        stack.PushFront(operand2 - operand1)
                        print("- :\t")
                        printStack(&stack)
                case "*":
                        operand1 := stack.PopFront()
                        operand2 := stack.PopFront()
                        stack.PushFront(operand1 * operand2)
                        print("* :\t")
                        printStack(&stack)
                case "/":
                        operand1 := stack.PopFront()
                        operand2 := stack.PopFront()
                        stack.PushFront(operand2 / operand1)
                        print("/ :\t")
                        printStack(&stack)
                default:
                        number, err := strconv.Atoi(term)
                        if err == nil {
                                stack.PushFront(number)
                        }
                        fmt.Printf("%-2d:\t", number)
                        printStack(&stack)
                }
        }
        print("Result: ")
        printStack(&stack)
}

Po spuštění tohoto demonstračního příkladu se výraz zapsaný v RPN bude postupně vyhodnocovat (a v průběhu vyhodnocování se bude vypisovat i obsah zásobníku operandů). Na konci vyhodnocení by měl zásobník obsahovat pouze jediný prvek – a to výsledek vyhodnocení výrazu:

10. Rotace prvků v oboustranné frontě

Zajímavou operací je rotace prvků v oboustranné frontě. Ve skutečnosti je totiž tato datová struktura v popisovaném balíčku implementována jako kruhový buffer (viz úvodní kapitolu), takže rotace prvků je provedena velmi efektivně – pouhým posunem indexů prvního a posledního prvku. Díky tomu se rotace obejde bez nutnosti přesunu dat v operační paměti. Ukažme si nejprve rotaci o kladné číslo (offset):

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
        }
 
        q.Rotate(3)
 
        for q.Len() > 0 {
                fmt.Println(q.PopFront())
        }
}

Ze zobrazených výsledků je patrné, že se prvky čtou nikoli od prvku s hodnotou 101 do prvku s hodnotou 110, ale tak, že jsou skutečně posunuty o tři prvky (původní poslední prvek ve frontě je zvýrazněn):

Možná je ovšem i rotace opačným směrem, kterou realizujeme předáním záporného offsetu do metody Deque.Rotate(). Opět si to pochopitelně otestujeme:

package main
 
import (
        "fmt"
 
        "github.com/gammazero/deque"
)
 
func main() {
        var q deque.Deque[int]
 
        for i := 1; i <= 10; i++ {
                q.PushBack(100 + i)
        }
 
        q.Rotate(-3)
 
        for q.Len() > 0 {
                fmt.Println(q.PopFront())
        }
}

Výsledek je (podle očekávání) odlišný, protože obsah obousměrné fronty byl otočen opačným směrem:

11. Časová složitost operací prováděných s oboustrannou frontou

Z pohledu uživatele je oboustranná fronta relativně složitým kontejnerem, protože umožňuje přidávat i ubírat prvky z obou konců. Navíc je možné prvky pouze přečíst, a to bez jejich odebrání. Podporována je i výše uvedená rotace prvků ve frontě, To však není vše, protože v tomto článku popisovaná varianta Deque navíc podporuje i vložení prvku do libovolného místa ve frontě i přečtení prvku z libovolného místa. Všechny tyto operace není možné provádět s konstantní složitostí – naopak se při návrhu vnitřní struktury oboustranné fronty musí programátor rozhodnout, které operace budou rychlé a které naopak (mnohdy velmi) pomalé. Samozřejmě se můžeme podívat do zdrojových kódů s implementací Deque, ovšem celý problém lze vyřešit i naopak – budeme se na Deque dívat jako na black box s několika metodami, přičemž pouze tyto metody jsou rozhraním k vnitřnímu stavu fronty. A dobu trvání těchto metod již dokážeme velmi snadno otestovat (za předpokladu, že jsou všechny operace synchronní, což v této konkrétní implementaci platí).

12. Implementace benchmarku

Implementace benchmarku v jazyce Go je prakticky triviální, protože pro tento účel je možné využít podporu pro benchmarky nabízenou standardním balíčkem testing. V implementovaném benchmarku jsou testovány následující metody pro práci s frontou:

Deque.PushFront
Deque.PushBack
Deque.PopFront (pro zaplněnou frontu)
Deque.PopBack (pro zaplněnou frontu)
Deque.Front (pouze čtení prvku)
Deque.Back (pouze čtení prvku)
Deque.Rotate
Deque.At
Deque.Insert (vložení prvku do středu fronty)
Deque.Remove (odstranění prvku ze středu fronty)

Samotný zdrojový kód benchmarku vypadá následovně:

package main
 
import (
        "testing"
 
        "github.com/gammazero/deque"
)
 
func BenchmarkPushFrontInt(b *testing.B) {
        var q deque.Deque[int]
 
        for i := 0; i < b.N; i++ {
                q.PushFront(i)
        }
}
 
func BenchmarkPushBackInt(b *testing.B) {
        var q deque.Deque[int]
 
        for i := 0; i < b.N; i++ {
                q.PushBack(i)
        }
}
 
func fillInDequeFromBack(b *testing.B) deque.Deque[int] {
        var q deque.Deque[int]
 
        b.StopTimer()
 
        for i := 0; i < b.N; i++ {
                q.PushBack(i)
        }
 
        b.StartTimer()
        return q
}
 
func fillInDequeFromFront(b *testing.B) deque.Deque[int] {
        var q deque.Deque[int]
 
        b.StopTimer()
 
        for i := 0; i < b.N; i++ {
                q.PushFront(i)
        }
 
        b.StartTimer()
        return q
}
 
func BenchmarkPopFrontInt(b *testing.B) {
        q := fillInDequeFromBack(b)
 
        for i := 0; i < b.N; i++ {
                val := q.PopFront()
                if val != i {
                        b.Fail()
                }
        }
}
 
func BenchmarkPopBackInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                val := q.PopBack()
                if val != i {
                        b.Fail()
                }
        }
}
 
func BenchmarkFrontInt(b *testing.B) {
        q := fillInDequeFromBack(b)
 
        b.StopTimer()
        for i := 0; i < b.N; i++ {
                q.PushBack(i)
        }
 
        b.StartTimer()
        for i := 0; i < b.N; i++ {
                val := q.Front()
                if val != 0 {
                        b.Fail()
                }
        }
}
 
func BenchmarkBackInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                val := q.Back()
                if val != 0 {
                        b.Fail()
                }
        }
}
 
func BenchmarkRotateInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                q.Rotate(1)
        }
}
 
func BenchmarkAtInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                // at from the middle
                val := q.At(q.Len() / 2)
                if val < 0 || val > b.N {
                        b.Fail()
                }
        }
}
 
func BenchmarkInsertInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                // insert into the middle
                q.Insert(q.Len()/2, i)
        }
}
 
func BenchmarkRemoveInt(b *testing.B) {
        q := fillInDequeFromFront(b)
 
        for i := 0; i < b.N; i++ {
                // remove from the middle
                q.Remove(q.Len() / 2)
        }
}

13. Výsledky benchmarků pro krátké obousměrné fronty

Podívejme se nyní na výsledky benchmarků v situaci, kdy je počet operací s frontou (a u většiny benchmarků současně i maximální délka fronty) nastaven na hodnoty 10, 100, 1000 a 10000:

$ go test -bench=. -benchtime=10x
$ go test -bench=. -benchtime=100x
$ go test -bench=. -benchtime=1000x
$ go test -bench=. -benchtime=10000x

I u takto krátkých front je však možné odhalit ty operace, které nemají konstantní složitost, ale například složitost lineární či (což zde nenastává) kvadratickou:

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8               10                92.70 ns/op
BenchmarkPushBackInt-8                10                81.10 ns/op
BenchmarkPopFrontInt-8                10                43.20 ns/op
BenchmarkPopBackInt-8                 10                53.50 ns/op
BenchmarkFrontInt-8                   10                40.10 ns/op
BenchmarkBackInt-8                    10                31.10 ns/op
BenchmarkRotateInt-8                  10                51.60 ns/op
BenchmarkAtInt-8                      10                46.40 ns/op
BenchmarkInsertInt-8                  10                87.30 ns/op
BenchmarkRemoveInt-8                  10                65.80 ns/op
PASS
ok      deque-demos     0.005s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8              100                66.15 ns/op
BenchmarkPushBackInt-8               100                43.84 ns/op
BenchmarkPopFrontInt-8               100                14.24 ns/op
BenchmarkPopBackInt-8                100                20.21 ns/op
BenchmarkFrontInt-8                  100                 5.85 ns/op
BenchmarkBackInt-8                   100                 5.13 ns/op
BenchmarkRotateInt-8                 100                21.99 ns/op
BenchmarkAtInt-8                     100                 6.80 ns/op
BenchmarkInsertInt-8                 100               147.80 ns/op
BenchmarkRemoveInt-8                 100                66.56 ns/op
PASS
ok      deque-demos     0.006s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8             1000                16.40 ns/op
BenchmarkPushBackInt-8              1000                12.02 ns/op
BenchmarkPopFrontInt-8              1000                11.80 ns/op
BenchmarkPopBackInt-8               1000                 7.21 ns/op
BenchmarkFrontInt-8                 1000                 1.78 ns/op
BenchmarkBackInt-8                  1000                 1.44 ns/op
BenchmarkRotateInt-8                1000                13.70 ns/op
BenchmarkAtInt-8                    1000                 2.89 ns/op
BenchmarkInsertInt-8                1000               877.20 ns/op
BenchmarkRemoveInt-8                1000               308.60 ns/op
PASS
ok      deque-demos     0.007s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8            10000                10.06 ns/op
BenchmarkPushBackInt-8             10000                10.92 ns/op
BenchmarkPopFrontInt-8             10000                 9.03 ns/op
BenchmarkPopBackInt-8              10000                 5.84 ns/op
BenchmarkFrontInt-8                10000                 1.25 ns/op
BenchmarkBackInt-8                 10000                 0.99 ns/op
BenchmarkRotateInt-8               10000                12.16 ns/op
BenchmarkAtInt-8                   10000                 4.35 ns/op
BenchmarkInsertInt-8               10000              7958.00 ns/op
BenchmarkRemoveInt-8               10000              2610.00 ns/op
PASS
ok      deque-demos     0.113s

Obrázek 1: Povšimněte si, že až na úvodní „spiky“ (než se kód zahřeje) má všech osm operací konstantní složitost.

Poznámka: můžeme vidět, že prvních osm měřených operací má pravděpodobně konstantní složitost, kdežto u dalších dvou operací Insert a Remove je situace složitější.

14. Výsledky benchmarků pro fronty s větším počtem prvků

Nyní si vyzkoušejme délku trvání operací, zejména operací Insert a Remove, u front s délkou 100000, 200000, 300000, 400000 a 500000 prvků. Sledovat budeme především operace Insert a Remove, které budou mít (pravděpodobně) lineární časovou složitost závislou na počtu prvků již vložených do fronty:

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8           100000                 7.84 ns/op
BenchmarkPushBackInt-8            100000                12.54 ns/op
BenchmarkPopFrontInt-8            100000                 5.33 ns/op
BenchmarkPopBackInt-8             100000                 6.80 ns/op
BenchmarkFrontInt-8               100000                 0.72 ns/op
BenchmarkBackInt-8                100000                 0.95 ns/op
BenchmarkRotateInt-8              100000                12.68 ns/op
BenchmarkAtInt-8                  100000                 2.39 ns/op
BenchmarkInsertInt-8              100000             88824.00 ns/op
BenchmarkRemoveInt-8              100000             29699.00 ns/op
PASS
ok      deque-demos     11.871s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8           200000                11.74 ns/op
BenchmarkPushBackInt-8            200000                11.13 ns/op
BenchmarkPopFrontInt-8            200000                 6.59 ns/op
BenchmarkPopBackInt-8             200000                 7.98 ns/op
BenchmarkFrontInt-8               200000                 0.75 ns/op
BenchmarkBackInt-8                200000                 0.95 ns/op
BenchmarkRotateInt-8              200000                14.86 ns/op
BenchmarkAtInt-8                  200000                 2.75 ns/op
BenchmarkInsertInt-8              200000            189081.00 ns/op
BenchmarkRemoveInt-8              200000             67279.00 ns/op
PASS
ok      deque-demos     51.330s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8           300000                10.45 ns/op
BenchmarkPushBackInt-8            300000                11.11 ns/op
BenchmarkPopFrontInt-8            300000                 6.45 ns/op
BenchmarkPopBackInt-8             300000                 6.12 ns/op
BenchmarkFrontInt-8               300000                 0.71 ns/op
BenchmarkBackInt-8                300000                 1.02 ns/op
BenchmarkRotateInt-8              300000                12.27 ns/op
BenchmarkAtInt-8                  300000                 2.44 ns/op
BenchmarkInsertInt-8              300000            309848.00 ns/op
BenchmarkRemoveInt-8              300000            103180.00 ns/op
PASS
ok      deque-demos     123.962s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8           400000                 9.02 ns/op
BenchmarkPushBackInt-8            400000                 9.71 ns/op
BenchmarkPopFrontInt-8            400000                 5.60 ns/op
BenchmarkPopBackInt-8             400000                 5.58 ns/op
BenchmarkFrontInt-8               400000                 0.71 ns/op
BenchmarkBackInt-8                400000                 0.95 ns/op
BenchmarkRotateInt-8              400000                12.24 ns/op
BenchmarkAtInt-8                  400000                 2.40 ns/op
BenchmarkInsertInt-8              400000            406410.00 ns/op
BenchmarkRemoveInt-8              400000            140504.00 ns/op
PASS
ok      deque-demos     218.827s

goos: linux
goarch: amd64
pkg: deque-demos
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkPushFrontInt-8           500000                 8.22 ns/op
BenchmarkPushBackInt-8            500000                 8.33 ns/op
BenchmarkPopFrontInt-8            500000                 5.26 ns/op
BenchmarkPopBackInt-8             500000                 5.20 ns/op
BenchmarkFrontInt-8               500000                 0.81 ns/op
BenchmarkBackInt-8                500000                 0.95 ns/op
BenchmarkRotateInt-8              500000                12.34 ns/op
BenchmarkAtInt-8                  500000                 2.39 ns/op
BenchmarkInsertInt-8              500000            502974.00 ns/op
BenchmarkRemoveInt-8              500000            174666.00 ns/op
PASS
ok      deque-demos     338.897s

V tomto případě je nejlepší, když si časovou složitost necháme vykreslit do grafu:

Obrázek 2: Časová složitost operací Insert a Remove v závislosti na počtu prvků ve frontě.

15. Závěrečné zhodnocení

Dnes zmíněná implementace obousměrně vázané fronty je implementována poměrně efektivním způsobem, a to s důrazem na malé nároky na CPU při provádění základních operací (kromě Insert a Remove, což jsou ovšem operace, které s frontou vlastně nesouvisí). Taktéž je výhodné, že jsou plně podporovány generické datové typy a operace s frontou jsou tedy (po stránce použitých typů) plně hlídány překladačem jazyka Go a pro každý typ je generován nový (efektivní) strojový kód. A navíc se jedná o balíček, jenž nezávisí na dalších balíčcích, což je v ekosystému jazyka Go dnes již poměrně velká výhoda (hlídání balíčků s potenciálním CVE je v těchto případech mnohem snazší atd.).

16. Příloha 1: CSV soubor s výsledky benchmarků

Pro úplnost si uveďme CSV soubor, jenž obsahuje výsledky všech provedených benchmarků. Uvedené hodnoty reprezentují čas v nanosekundách:

Benchmark,    10x,  100x,  1000x,  10000x, 100000x,  200000x,  300000x,  400000x,  500000x
PushFrontInt, 92.70, 66.15, 16.40,  10.06,    7.84,    11.74,    10.45,     9.02,     8.22
PushBackInt,  81.10, 43.84, 12.02,  10.92,   12.54,    11.13,    11.11,     9.71,     8.33
PopFrontInt,  43.20, 14.24, 11.80,   9.03,    5.33,     6.59,     6.45,     5.60,     5.26
PopBackInt,   53.50, 20.21,  7.21,   5.84,    6.80,     7.98,     6.12,     5.58,     5.20
FrontInt,     40.10,  5.85,  1.78,   1.25,    0.72,     0.75,     0.71,     0.71,     0.81
BackInt,      31.10,  5.13,  1.43,   0.99,    0.95,     0.95,     1.02,     0.95,     0.95
RotateInt,    51.60, 21.99, 13.70,  12.16,   12.68,    14.86,    12.27,    12.24,    12.34
AtInt,        46.40,  6.80,  2.88,   4.35,    2.39,     2.75,     2.44,     2.40,     2.39
InsertInt,    87.30,147.80,877.20,7958.00,88824.00,189081.00,309848.00,406410.00,502974.00
RemoveInt,    65.80, 66.56,308.60,2610.00,29699.00, 67279.00,103180.00,140504.00,174666.00

17. Příloha 2: Názvy operací s obousměrnou frontou

Názvy operací prováděných s obousměrnou frontou nejsou zcela standardizovány, takže se můžeme setkat s různým pojmenováním příslušných funkcí nebo metod. Následující tabulka byla převzata z Wikipedie a upravena pro účely dnešního článku:

Go	Ada	C++	Java	Perl	PHP	Python	Ruby	Rust	JavaScript
PushBack	Append	push_back	offerLast	push	array_push	append	push	push_back	push
PushFront	Prepend	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	push_front	unshift
PopBack	Delete_Last	pop_back	pollLast	pop	array_pop	pop	pop	pop_back	pop
PopFront	Delete_First	pop_front	pollFirst	shift	array_shift	popleft	shift	pop_front	shift
Back	Last_Element	back	peekLast	$array[-1]	end	seznam[-1]	last	back	objekt.at(-1)
Front	First_Element	front	peekFirst	$array[0]	reset	seznam[0]	first	front	objekt[0]

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	01_empty_deque.go	vytvoření prázdné (plně funkční) obousměrné fronty	https://github.com/tisnik/go-root/blob/master/article₉₆/01_empty_deque.go
2	02_pushback.go	obousměrná fronta a operace typu push back	https://github.com/tisnik/go-root/blob/master/article₉₆/02_pushback.go
3	03_length_capacity.go	závislost délky a kapacity obousměrné fronty při přidávání prvků	https://github.com/tisnik/go-root/blob/master/article₉₆/03_length_capacity.go
4	04_popfront_panic.go	operace pop front bez testu, zda je fronta prázdná	https://github.com/tisnik/go-root/blob/master/article₉₆/04_popfront_panic.go
5	05_popfront.go	operace pop front s korektním testem, zda je fronta prázdná	https://github.com/tisnik/go-root/blob/master/article₉₆/05_popfront.go
6	06_as_queue₁.go	obousměrná fronta použitá jako klasická fronta (queue)	https://github.com/tisnik/go-root/blob/master/article₉₆/06_as_queue₁.go
7	07_as_queue₂.go	obousměrná fronta použitá jako klasická fronta (queue)	https://github.com/tisnik/go-root/blob/master/article₉₆/07_as_queue₂.go
8	08_as_stack₁.go	obousměrná fronta použitá jako klasický zásobník (stack)	https://github.com/tisnik/go-root/blob/master/article₉₆/08_as_stack₁.go
9	09_as_stack₂.go	obousměrná fronta použitá jako klasický zásobník (stack)	https://github.com/tisnik/go-root/blob/master/article₉₆/09_as_stack₂.go
10	10_stack_rpn.go	vyhodnocení RPN výrazů s využitím deque ve funkci zásobníku	https://github.com/tisnik/go-root/blob/master/article₉₆/10_stack_rpn.go
11	11_rotate.go	obousměrná fronta a operace rotate	https://github.com/tisnik/go-root/blob/master/article₉₆/11_rotate.go
12	12_rotate.go	obousměrná fronta a operace rotate	https://github.com/tisnik/go-root/blob/master/article₉₆/12_rotate.go

Poznámka: k dispozici je i benchmark, jenž je dostupný na adrese https://github.com/tisnik/go-root/blob/master/article₉₆/benchmarks/.

19. Odkazy na Internetu

Double-ended queue
https://en.wikipedia.org/wiki/Double-ended_queue
Deque package reference documentation
https://pkg.go.dev/github.com/gammazero/deque
Fast ring-buffer deque (double-ended queue) implementation.
https://github.com/gammazero/deque
Highly optimized double-ended queue
https://github.com/edwingeng/deque/tree/master/v2
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
Circular buffer
https://en.wikipedia.org/wiki/Circular_buffer
Circular Buffer
http://wiki.c2.com/?CircularBuffer

Seriál: Programovací jazyk Go

Zpracování n-rozměrných polí v jazyce Go s využitím knihovny narray
Obousměrná fronta (deque) v programovacím jazyku Go
Převody zdrojových kódů z jazyka C do jazyka Go

Přečtěte si všechny díly seriálu Programovací jazyk Go nebo sledujte jeho RSS

Vstoupit do diskuse (16 názorů)

Pavel Tišnovský

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.

Témata:

Dnešní Javu neznám, naposledy jsem v ní psal někdy okolo roku 2005. Ale faktem je, že překopírovat mapu je o dost složitější než řez.

Calculon

Sdílet

Obsah

1. Obousměrná fronta – deque – v programovacím jazyku Go

2. Instalace balíčku deque

3. Konstruktor obousměrné fronty s uvedením typů prvků

4. Operace push back, růst počtu prvků a kapacity fronty

5. Algoritmus pro zvýšení kapacity fronty při přidávání prvků

6. Čtení prvků z čela (začátku) fronty

7. Oboustranná fronta ve funkci klasické fronty: dvojice operací push back + pop front a push front + pop back

8. Oboustranná fronta ve funkci klasického zásobníku: dvojice operací push back + pop back a push front + pop front

9. Praktické využití zásobníku – výpočet výrazu zapsaného v RPN

10. Rotace prvků v oboustranné frontě

11. Časová složitost operací prováděných s oboustrannou frontou

12. Implementace benchmarku

13. Výsledky benchmarků pro krátké obousměrné fronty

14. Výsledky benchmarků pro fronty s větším počtem prvků

15. Závěrečné zhodnocení

16. Příloha 1: CSV soubor s výsledky benchmarků

17. Příloha 2: Názvy operací s obousměrnou frontou

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

19. Odkazy na Internetu

Zpracování n-rozměrných polí v jazyce Go s využitím knihovny narray