I dnešní část je věnována popisu možností standardní knihovny. Dnes se zaměříme na protokol HTTP, popis balíčků s implementací různých datových struktur a taktéž na popis balíčku s rozhraními a typy pro řazení a vyhledávání.
1. Jednoduchý HTTP server využívající rozhraní ResponseWriter a strukturu Request
2. Chování HTTP serveru v případě odpovědi, která je zpracovávána delší dobu
3. Využití metody Flush rozhraní Flusher
4. Test, zda se klient odpojil
5. Základní kolekce podporované základní knihovnou programovacího jazyka Go
7. Použití seznamů ve funkci zásobníku pro implementaci RPN
8. Cyklická fronta (cyklický seznam)
9. Naplnění cyklické fronty hodnotami, hodnoty neinicializovaných prvků
11. Balíček sort: řadicí a vyhledávací algoritmy
12. Práce s poli či řezy s prvky typu int a float64
13. Složitější příklad: seřazení všech slov načtených z textového souboru
14. Typy IntSlice, Float64Slice a StringSlice
15. Řazení prvků na základě vlastní porovnávací funkce
16. Řazení pole/řezů struktur podle vlastních kritérií
17. Rozhraní Heap a jeho význam v praxi
18. Interní změna pozice prvků při práci s haldou
19. Repositář s demonstračními příklady
V předchozích dvou částech [1] [2] seriálu o programovacím jazyku Go jsme se seznámili se základními rozhraními a jejich implementacemi, které se používají pro vstupně-výstupní operace (standardní vstup, standardní výstup, soubory, síťová připojení, FIFO, paměťové buffery atd.). Dnes se tímto tématem budeme zabývat pouze okrajově, protože si ukážeme některé další možnosti poskytované implementací HTTP serveru, konkrétně datovými typy http.Server a http.ServeMUX. Touto problematikou jsme se již částečně zabývali v předchozích částech tohoto seriálu, takže si jen ve stručnosti ukažme, jakým způsobem je možné v programovacím jazyku Go vytvořit aplikaci, která bude pracovat jako HTTP server poskytující klientům statický obsah načítaný ze specifikované adresářové struktury:
package main
import (
"io"
"net/http"
)
func mainEndpoint(writer http.ResponseWriter, request *http.Request) {
io.WriteString(writer, "Hello world!\n")
}
func main() {
http.HandleFunc("/", mainEndpoint)
http.ListenAndServe(":8000", nil)
}
Zajímavější je pochopitelně implementace HTTP serveru, která bude generovat dynamický obsah. Ten lze tvořit buď přímo „ručně“ v programu, nebo můžeme využít některé balíčky ze standardní knihovny programovacího jazyka Go pro generování dat ve formátu JSON, XML popř. knihovny s implementací šablon (templates). Dnes nás ovšem bude zajímat první způsob, tj. „ruční“ generování odpovědi, která je serverem posílána klientovi na základě jeho dotazu (request). Jedna z nejjednodušších implementací takového HTTP serveru může vypadat například následovně:
package main
import (
"net/http"
)
func mainEndpoint(writer http.ResponseWriter, request *http.Request) {
response := "Hello world!\n"
writer.Write([]byte(response))
}
func main() {
http.HandleFunc("/", mainEndpoint)
http.ListenAndServe(":8000", nil)
}
Funkci takového serveru si můžeme snadno otestovat, například s využitím nástroje wget nebo ještě lépe curl. Vzhledem k tomu, že víme, na jakém portu server běží a jaký endpoint máme zavolat, sestavíme příkaz pro curl tímto způsobem:
$ curl -v localhost:8000
Výstup bude obsahovat i ladicí informace vyžádané přepínačem -v:
* Rebuilt URL to: localhost:8000/ * Hostname was NOT found in DNS cache * Trying 127.0.0.1... * Connected to localhost (127.0.0.1) port 8000 (#0) > GET / HTTP/1.1 > User-Agent: curl/7.35.0 > Host: localhost:8000 > Accept: */* > < HTTP/1.1 200 OK < Date: Mon, 06 May 2019 18:14:06 GMT < Content-Length: 13 < Content-Type: text/plain; charset=utf-8 < Hello world! * Connection #0 to host localhost left intact
Ve zdrojovém kódu si povšimněte především funkce, v níž je implementováno generování a posílání odpovědi. Této funkci jsou předány dvě hodnoty, přičemž první je typu rozhraní http.ResponseWriter a druhá je typu ukazatel na http.Request:
type ResponseWriter interface {
Header() Header
Write([]byte) (int, error)
WriteHeader(statusCode int)
}
Předchozí implementace HTTP serveru sice ukázala, jakým způsobem se generuje dynamický obsah, ovšem v některých případech je situace složitější, neboť je nutné zajistit, aby se po HTTP protokolu přenášelo větší množství dat, které klient bude zpracovávat postupně, jakoby se jednalo o stream (jedná se sice o určité zneužití původní oblasti použití HTTP, ovšem setkáme se s ním poměrně často). Vyzkoušejme si tedy, jak bude komunikace mezi klientem a serverem vypadat ve chvíli, kdy server bude dodávat data rozdělená do záznamů (record). V tomto případě využijeme toho, že v rozhraní http.ResponseWriter je předepsána metoda:
Write([]byte) (int, error)
Tuto metodu pochopitelně již dobře známe, protože jsme se s ní několikrát setkali v předchozích dvou článcích. Samotná funkce, která bude na HTTP dotaz postupně dodávat odpověď rozdělenou na mnoho záznamů, tedy může v tom nejjednodušším případě vypadat následovně:
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
writer.Write([]byte("Hello world!\n"))
}
println("handler finished")
}
Úplnou implementaci takto modifikovaného HTTP serveru nalezneme na adrese https://github.com/tisnik/go-root/blob/master/article24/01_server.go:
package main
import (
"net/http"
)
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
writer.Write([]byte("Hello world!\n"))
}
println("handler finished")
}
func main() {
http.HandleFunc("/data", handler)
http.ListenAndServe(":8080", nil)
}
Chování HTTP serveru opět otestujeme nástrojem curl:
$ curl -v localhost:8080/data * Hostname was NOT found in DNS cache * Trying 127.0.0.1... * Connected to localhost (127.0.0.1) port 8080 (#0) > GET /data HTTP/1.1 > User-Agent: curl/7.35.0 > Host: localhost:8080 > Accept: */* > < HTTP/1.1 200 OK < Date: Sat, 04 May 2019 17:43:57 GMT < Content-Length: 650 < Content-Type: text/plain; charset=utf-8 < Hello world! ... ... ... Hello world! * Connection #0 to host localhost left intact
Přidat můžeme i simulaci postupného vytváření a posílání jednotlivých záznamů:
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
writer.Write([]byte("Hello world!\n"))
time.Sleep(100 * time.Millisecond)
print(".")
}
println("\nhandler finished")
}
Následuje výpis úplného zdrojového kódu tohoto příkladu:
package main
import (
"net/http"
"time"
)
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
writer.Write([]byte("Hello world!\n"))
time.Sleep(100 * time.Millisecond)
print(".")
}
println("\nhandler finished")
}
func main() {
http.HandleFunc("/data", handler)
http.ListenAndServe(":8080", nil)
}
Nyní si chování této nové implementace HTTP serveru můžeme otestovat, a to opět s využitím nástroje curl. Po poslání požadavku:
$ curl -v localhost:8080/data
Server ihned pošle první část odpovědi (konkrétně hlavičku HTTP odpovědi):
$ curl -v localhost:8080/data * Hostname was NOT found in DNS cache * Trying 127.0.0.1... * Connected to localhost (127.0.0.1) port 8080 (#0) > GET /data HTTP/1.1 > User-Agent: curl/7.35.0 > Host: localhost:8080 > Accept: */* > < HTTP/1.1 200 OK < Date: Fri, 03 May 2019 19:34:51 GMT < Content-Length: 650 < Content-Type: text/plain; charset=utf-8
V této chvíli sice server postupně vytváří jednotlivé části těla odpovědi, ovšem klient tuto činnost nebude vidět, a to kvůli tomu, že se na straně klienta (a někdy i celého síťového stacku) používají buffery. Z pohledu klienta tedy v této chvíli dojde k jediné časové prodlevě o délce přibližně 100×50 ms = 5 sekund.
Až po této prodlevě klient přijme všechny části odpovědi, a to najednou:
Hello world! Hello world! Hello world! ... ... ... Hello world! Hello world! Hello world! * Connection #0 to host localhost left intact
V případě, že je skutečně nutné, aby klient dostal jednotlivé části odpovědi ihned po jejich vygenerování serverem, musíme se podívat na to, jak vlastně metoda http.ResponseWriter.Write() interně pracuje. Její činnost je poměrně přesně popsána v dokumentaci:
$ go doc http ResponseWriter.Write // Write writes the data to the connection as part of an HTTP reply. // // If WriteHeader has not yet been called, Write calls // WriteHeader(http.StatusOK) before writing the data. If the Header // does not contain a Content-Type line, Write adds a Content-Type set // to the result of passing the initial 512 bytes of written data to // DetectContentType. Additionally, if the total size of all written // data is under a few KB and there are no Flush calls, the // Content-Length header is added automatically. // // Depending on the HTTP protocol version and the client, calling // Write or WriteHeader may prevent future reads on the // Request.Body. For HTTP/1.x requests, handlers should read any // needed request body data before writing the response. Once the // headers have been flushed (due to either an explicit Flusher.Flush // call or writing enough data to trigger a flush), the request body // may be unavailable. For HTTP/2 requests, the Go HTTP server permits // handlers to continue to read the request body while concurrently // writing the response. However, such behavior may not be supported // by all HTTP/2 clients. Handlers should read before writing if // possible to maximize compatibility. func Write([]byte) (int, error)
Řešením (i když zdaleka ne dokonalým) je tedy volání metody Flush po každém volání Write. Tato metoda je předepsána v rozhraní http.Flusher:
type Flusher interface {
Flush()
}
Teoreticky by tedy handler mohl být upraven takto:
writer.Write([]byte("Hello world!\n"))
f.Flush()
Ve skutečnosti však nemusí všechny hodnoty implementující rozhraní ResponseWriter současně implementovat i rozhraní Flusher, takže musíme přidat test, zda je možné zavolat metodu Flush. Kód se nám nepatrně zkomplikuje:
writer.Write([]byte("Hello world!\n"))
if f, ok := writer.(http.Flusher); ok {
f.Flush()
}
Úplný zdrojový kód upravené implementace HTTP serveru naleznete na adrese https://github.com/tisnik/go-root/blob/master/article24/03_flushing_server.go:
package main
import (
"net/http"
"time"
)
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
writer.Write([]byte("Hello world!\n"))
print(".")
if f, ok := writer.(http.Flusher); ok {
f.Flush()
}
time.Sleep(100 * time.Millisecond)
}
println("\nhandler finished")
}
func main() {
http.HandleFunc("/data", handler)
http.ListenAndServe(":8080", nil)
}
Chování nové implementace HTTP serveru si můžeme otestovat, opět s využitím nástroje curl. Nyní by se již jednotlivé odpovědi měly objevovat postupně a přibližně v takových intervalech, v jakých je posílá server:
$ curl -v localhost:8080/data * Hostname was NOT found in DNS cache * Trying 127.0.0.1... * Connected to localhost (127.0.0.1) port 8080 (#0) > GET /data HTTP/1.1 > User-Agent: curl/7.35.0 > Host: localhost:8080 > Accept: */* > < HTTP/1.1 200 OK < Date: Fri, 03 May 2019 19:36:50 GMT < Content-Length: 650 < Content-Type: text/plain; charset=utf-8 <
Postupné odpovědi serveru:
Hello world! Hello world! Hello world! * Connection #0 to host localhost left intact
V případě, že HTTP server popsaný v předchozí kapitole spustíme, s využitím nástroje curl vytvoříme požadavek a následně spojení ukončíme, například stiskem Ctrl+C, bude se server pokoušet dále volat metodu Write a posílat data do již uzavřeného připojení. Pro korektní činnost tedy musíme přidat testy na to, zda se zápis podařil:
n, err := writer.Write([]byte("Hello world!\n"))
if err != nil {
println("\nI/O error:", err.Error())
return
}
Tuto novou implementaci HTTP serveru, kterou naleznete na adrese https://github.com/tisnik/go-root/blob/master/article24/04_close_detector.go, vypadá následovně:
package main
import (
"net/http"
"time"
)
func handler(writer http.ResponseWriter, request *http.Request) {
println("handler started")
for i := 0; i < 50; i++ {
n, err := writer.Write([]byte("Hello world!\n"))
if err != nil {
println("\nI/O error:", err.Error())
return
}
if n == 0 {
println("\nnothing written")
return
}
print(".")
if f, ok := writer.(http.Flusher); ok {
f.Flush()
}
time.Sleep(100 * time.Millisecond)
}
println("\nhandler finished")
}
func main() {
http.HandleFunc("/data", handler)
http.ListenAndServe(":8080", nil)
}
Začátek testování:
$ curl -v localhost:8080/data * Hostname was NOT found in DNS cache * Trying 127.0.0.1... * Connected to localhost (127.0.0.1) port 8080 (#0) > GET /data HTTP/1.1 > User-Agent: curl/7.35.0 > Host: localhost:8080 > Accept: */* > < HTTP/1.1 200 OK < Date: Fri, 03 May 2019 19:38:41 GMT < Content-Type: text/plain; charset=utf-8 < Transfer-Encoding: chunked < Hello world! Hello world! Hello world! Hello world! ^C
Po stisku klávesové zkratky Ctrl+C by se na straně serveru mělo objevit toto hlášení:
handler started ....... I/O error: write tcp 127.0.0.1:8080->127.0.0.1:47698: write: broken pipe
Ve druhé části dnešního článku si popíšeme ty balíčky, v nichž jsou implementovány takzvané kontejnery (containers). Ve skutečnosti se nejedná o nic složitého, pouze o rozšíření množiny složených datových struktur poskytovaných samotným programovacím jazykem Go. Připomeňme si, že mezi složené struktury patří zejména záznamy (struct), pole (array), od nich odvozený koncept řezů (slice) a samozřejmě taktéž mapy (map). Další kontejnery nalezneme v podbalíčcích balíčku container:
| Podbalíček | Stručný popis |
|---|---|
| container/heap | rozhraní předepisující metody a chování datového typu halda (heap) |
| container/list | obousměrně vázaný lineární seznam |
| container/ring | kruhová fronta či seznam s pevnou kapacitou |
Do těchto kontejnerů se ukládají prvky typu interface{}, což v programovacím jazyku Go de facto znamená „hodnoty neznámého typu“. Pokud z kontejneru nějakou hodnotu přečteme, musí se většinou explicitně specifikovat, jaký typ prvků očekáváme. K tomuto účelu se v Go používají takzvané typové aserce, které se zapisují následujícím způsobem:
i := x.(T) i, ok := x.(T)
kde se za T doplní konkrétní datový typ, například int nebo string. Ve druhém případě se do nové proměnné ok zapíše pravdivostní hodnota značící, zda se operace provedla či nikoli.
Touto datovou strukturou jsme se již zabývali v deváté části seriálu o programovacím jazyku Go, takže si jen ve stručnosti ukažme, jak se vytvoří nový (prázdný) seznam, vloží se do něj tři prvky a následně se celý seznam vypíše s využitím iterace přes všechny jeho prvky:
package main
import (
"container/list"
"fmt"
)
func printList(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
func main() {
l := list.New()
l.PushBack("foo")
l.PushBack("bar")
l.PushBack("baz")
printList(l)
}
Výsledkem běhu tohoto příkladu budou následující tři řádky:
foo bar baz
I s využitím obousměrně vázaného seznamu ve funkci zásobníku (stack) jsme se seznámili v deváté části tohoto seriálu. Stačí se pouze rozhodnout, který konec seznamu bude sloužit jako vrchol zásobníku (TOS – Top of Stack). Pokud zvolíme, že TOS bude ležet na konci seznamu, můžeme si vytvořit dvě pomocné funkce pro dvě základní operace se zásobníkem – push a pop. V případě, že zásobník bude obsahovat pouze celá čísla, může implementace obou zmíněných funkcí vypadat následovně:
func push(l *list.List, number int) {
l.PushBack(number)
}
func pop(l *list.List) int {
tos := l.Back()
l.Remove(tos)
return tos.Value.(int)
}
Zásobník využijeme například při implementaci kalkulačky, která rozpozná priority operátorů:
package main
import (
"container/list"
"fmt"
"strconv"
"strings"
)
type Stack list.List
func printStack(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
func push(l *list.List, number int) {
l.PushBack(number)
}
func pop(l *list.List) int {
tos := l.Back()
l.Remove(tos)
return tos.Value.(int)
}
func main() {
expression := "1 2 + 2 3 * 8 + *"
terms := strings.Split(expression, " ")
stack := list.New()
for _, term := range terms {
switch term {
case "+":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand1+operand2)
case "-":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand2-operand1)
case "*":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand1*operand2)
case "/":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand2/operand1)
default:
number, err := strconv.Atoi(term)
if err == nil {
push(stack, number)
}
}
}
printStack(stack)
}
Výsledek výpočtu je jednoznačný:
42
Nepatrnou úpravou tohoto programu získáme nástroj, který nejenže daný RPN výraz vypočítá, ale bude v průběhu výpočtu vypisovat i aktuální obsah zásobníku. Úprava spočívá v přidání řádků vypisujících prováděné operace a jejich operandy:
package main
import (
"container/list"
"fmt"
"strconv"
"strings"
)
type Stack list.List
func printStack(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("%2d ", e.Value)
}
println()
}
func push(l *list.List, number int) {
l.PushBack(number)
}
func pop(l *list.List) int {
tos := l.Back()
l.Remove(tos)
return tos.Value.(int)
}
func main() {
expression := "1 2 + 2 3 * 8 + *"
terms := strings.Split(expression, " ")
stack := list.New()
for _, term := range terms {
switch term {
case "+":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand1+operand2)
print("+ : ")
printStack(stack)
case "-":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand2-operand1)
print("- : ")
printStack(stack)
case "*":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand1*operand2)
print("* : ")
printStack(stack)
case "/":
operand1 := pop(stack)
operand2 := pop(stack)
push(stack, operand2/operand1)
print("/ : ")
printStack(stack)
default:
number, err := strconv.Atoi(term)
if err == nil {
push(stack, number)
}
fmt.Printf("%-2d: ", number)
printStack(stack)
}
}
print("Result: ")
printStack(stack)
}
Postupné provádění výpočtu s jeho vizualizací:
1 : 1 2 : 1 2 + : 3 2 : 3 2 3 : 3 2 3 * : 3 6 8 : 3 6 8 + : 3 14 * : 42 Result: 42
Druhým typem kontejneru, který si v dnešním článku popíšeme, je kruhová fronta popř. kruhový seznam s pevnou kapacitou, který se označuje termínem ring. Vlastní kontejner, který obsahuje prvky typu Ring, se vytváří konstruktorem New (pochopitelně se zadáním názvu balíčku v prefixu), kterému je nutné předat požadovanou kapacitu kontejneru:
func New(n int) *Ring
Příkladem může být cyklická fronta s kapacitou deseti prvků:
r := ring.New(10)
Ve chvíli, kdy je kontejner o požadované kapacitě vytvořen, je vrácena hodnota představovaná ukazatelem na strukturu nazvanou taktéž Ring. Tato struktura představující první prvek v kruhovém seznamu interně obsahuje jediný prvek nazvaný Value, který je typu interface{}:
type Ring struct {
Value interface{}
}
Vzhledem k tomu, že prázdné rozhraní interface{} je implementováno všemi datovými typy programovacího jazyka Go (jak těmi základními, tak i uživatelskými), je možné do kontejneru ukládat prvky libovolného typu, pochopitelně včetně celých čísel:
r := ring.New(10) r.Value = 42
Na předchozí resp. na následující prvek v kontejneru se přechází metodami :
func (r *Ring) Next() *Ring
a:
func (r *Ring) Prev() *Ring
Celková kapacita kontejneru se získá metodou Len(), která však musí všemi prvky projít, takže její časová složitost je O(n).
Mezi další užitečné metody patří:
| Metoda | Význam |
|---|---|
| Move | přesun ukazatele na aktivní prvek dopředu či dozadu o n prvků |
| Link | spojení dvou cyklických seznamů |
| Unlink | odstranění n elementů z kontejneru |
| Do | umožňuje iterovat nad jednotlivými prvky cyklického seznamu |
Základní vlastnosti cyklické fronty či cyklického seznamu si ukážeme na několika následujících demonstračních příkladech.
V prvním demonstračním příkladu, jehož zdrojový kód naleznete na adrese https://github.com/tisnik/go-root/blob/master/article24/08_empty_ring.go, je vytvořen kontejner o kapacitě deseti prvků, které ovšem nejsou žádným způsobem inicializovány. Tyto prvky (Ring.Value) ve výchozím stavu obsahují hodnotu nil:
package main
import (
"container/ring"
"fmt"
)
func printRing(r *ring.Ring) {
length := r.Len()
for i := 0; i < length; i++ {
fmt.Println(i, r.Value)
r = r.Next()
}
}
func main() {
r := ring.New(10)
printRing(r)
}
O tom, že se skutečně jedná o prvky s hodnotou nil se snadno přesvědčíme:
0 <nil> 1 <nil> 2 <nil> 3 <nil> 4 <nil> 5 <nil> 6 <nil> 7 <nil> 8 <nil> 9 <nil>
Druhý demonstrační příklad ukazuje, jakým způsobem je možné naplnit prvky kontejneru a jak se hodnoty uložené do prvků opět vytisknou (či zpracují jiným způsobem). Musíme mít přitom na paměti, že se jedná o kruhový seznam/frontu, takže když se budeme pohybovat pouze jedním směrem (Ring.Next() či naopak pouze Ring.Prev()), budou se prvky cyklicky opakovat. To je patrné i z funkce provádějící výpis, protože zde procházíme každým prvkem dvakrát:
length := r.Len()
for i := 0; i < length*2; i++ {
fmt.Println(i, r.Value)
r = r.Next()
}
Úplný zdrojový kód tohoto demonstračního příkladu vypadá následovně:
package main
import (
"container/ring"
"fmt"
)
func printRing(r *ring.Ring) {
length := r.Len()
for i := 0; i < length*2; i++ {
fmt.Println(i, r.Value)
r = r.Next()
}
}
func main() {
r := ring.New(3)
r.Value = "foo"
r = r.Next()
r.Value = "bar"
r = r.Next()
r.Value = "baz"
printRing(r)
}
Jeho výsledky:
0 baz 1 foo 2 bar 3 baz 4 foo 5 bar
V dalším příkladu jsou některé prvky kontejneru naplněny a jiné naopak přeskočeny:
r := ring.New(10) r.Value = "foo" r = r.Next() r.Value = "bar" r = r.Next() r.Value = "baz"
To se pochopitelně projeví i ve výpisu, ovšem je nutné mít na paměti, že s hodnotami nil je možné v programovacím jazyce Go pracovat zcela bez obavy.
Úplný zdrojový kód tohoto demonstračního příkladu vypadá následovně:
package <strong>main</strong>
import (
"container/ring"
"fmt"
)
func <strong>printRing</strong>(r *ring.Ring) {
length := r.Len()
for i := 0; i < length*2; i++ {
fmt.Println(i, r.Value)
r = r.Next()
}
}
func <strong>main</strong>() {
r := ring.New(10)
r.Value = "foo"
r = r.Next()
r.Value = "bar"
r = r.Next()
r.Value = "baz"
printRing(r)
}
Z výstupu je patrné, že se skutečně naplnily pouze některé prvky:
0 baz 1 <nil> 2 <nil> 3 <nil> 4 <nil> 5 <nil> 6 <nil> 7 <nil> 8 foo 9 bar 10 baz 11 <nil> 12 <nil> 13 <nil> 14 <nil> 15 <nil> 16 <nil> 17 <nil> 18 foo 19 bar
Pro procházení všemi prvky cyklické fronty/seznamu je určena metoda nazvaná Do, která umožňuje, aby se při průchodu každým prvkem (tedy v každé iteraci) zavolala určitá funkce, která se předá hodnota uložená do prvku. V následujícím – nutno říci, že velmi jednoduchém – příkladu je ukázáno, jak je možné zavolat funkci nazvanou printItem:
func printItem(item interface{}) {
fmt.Println(item)
}
Samotný průchod se pro cyklickou frontu r zajistí jediným programovým řádkem:
r.Do(printItem)
Následuje výpis zdrojového kódu tohoto příkladu:
package main
import (
"container/ring"
"fmt"
)
func printItem(item interface{}) {
fmt.Println(item)
}
func main() {
r := ring.New(3)
r.Value = "foo"
r = r.Next()
r.Value = "bar"
r = r.Next()
r.Value = "baz"
r.Do(printItem)
}
S výsledky:
baz foo bar
V případě, že budeme chtít funkci volané pro každý prvek předávat i další parametr, například spočítaný index prvku:
func printItem(index int, item interface{}) {
fmt.Println(index, item)
}
Je nutné použít uzávěr (closure), který je v jazyku Go taktéž podporován:
r.Do(func(item interface{}) {
printItem(i, item)
i++
})
Opět si ukažme upravený zdrojový kód příkladu:
package main
import (
"container/ring"
"fmt"
)
func printItem(index int, item interface{}) {
fmt.Println(index, item)
}
func main() {
r := ring.New(3)
r.Value = "foo"
r = r.Next()
r.Value = "bar"
r = r.Next()
r.Value = "baz"
i := 1
r.Do(func(item interface{}) {
printItem(i, item)
i++
})
}
Nyní se ve výsledcích objeví i indexy jednotlivých prvků (pokud ovšem mají v kruhové struktuře nějaký zvláštní význam):
1 baz 2 foo 3 bar
Nyní popis kontejnerů, které nalezneme ve standardní knihovně programovacího jazyka Go na chvíli opustíme, protože si popíšeme některé možnosti poskytované balíčkem nazvaným sort. Jak již název tohoto balíčku naznačuje, jsou v něm implementovány algoritmy pro řazení prvků; kromě toho zde však nalezneme i algoritmy pro vyhledávání prvků. Datové typy a metody v balíčku sort jsou vybrány poněkud zvláštním způsobem, protože zde nalezneme jak zcela obecné metody (řazení prvků libovolných typů), tak i metody určené pro některé konkrétní vybrané typy: pole celých čísel typu int, pole čísel s plovoucí řádovou čárkou typu float64 a konečně pole řetězců (string).
Pro samotné řazení prvků se používají následující funkce:
| # | Funkce | Význam |
|---|---|---|
| 1 | func Ints(a []int) | seřazení řezu celých čísel |
| 2 | func Float64s(a []float64) | seřazení řezu čísel typu float64 |
| 3 | func Strings(a []string) | seřazení řezu řetězců |
| 4 | func Sort(data Interface) | seřazení libovolné kolekce implementující rozhraní sort.Interface |
| 5 | func Stable(data Interface) | stabilní varianta algoritmu řazení libovolné kolekce implementující rozhraní sort.Interface |
| 6 | func Reverse(data Interface) | otočení pořadí prvků v kolekci |
Kromě toho je možné zavolat i další funkce, které zjistí, zda je určitý řez nebo kolekce již seřazená:
| # | Funkce | Význam |
|---|---|---|
| 1 | func IntsAreSorted(a []int) bool | test, zda je řez celých čísel setříděn |
| 2 | func Float64sAreSorted(a []float64) bool | test, zda je řez čísel typu float64 setříděn |
| 3 | func StringsAreSorted(a []string) bool | test, zda je řez obsahující řetězce setříděn |
| 4 | func IsSorted(data Interface) bool | test, zda jsou prvky v obecné kolekci setříděny |
Tyto funkce si popíšeme v dalších demonstračních příkladech.
Důležité je taktéž rozhraní nazvané přímočaře Interface, v němž jsou předepsány metody volané při řazení sekvencí. Toto rozhraní se používá u všech datových typů, tj. i u uživatelských typů:
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
V prvním demonstračním příkladu, jehož zdrojový kód naleznete na adrese https://github.com/tisnik/go-root/blob/master/article24/13_integer_sort.go, je ukázán způsob seřazení sekvence celých čísel a současně i zjištění, jestli je již řez, v němž je sekvence uložena, setříděn či nikoli. Na začátku je řez inicializován sekvencí náhodných hodnot; tato sekvence je vypsána, setříděna a poté znovu vypsána:
package main
import (
"fmt"
"math/rand"
"sort"
)
func printArray(prefix string, numbers []int) {
var state string
if sort.IntsAreSorted(numbers) {
state = "sorted"
} else {
state = "unsorted"
}
fmt.Printf("%s variant of %s array: %v\n", prefix, state, numbers)
}
func main() {
numbers := make([]int, 20)
for i := 0; i < len(numbers); i++ {
numbers[i] = rand.Int() % 10
}
printArray("1st", numbers)
sort.Ints(numbers)
printArray("2nd", numbers)
}
Po spuštění příkladu se nejdříve zobrazí původní náhodná sekvence a následně sekvence seřazená:
1st variant of unsorted array: [0 1 1 1 7 0 8 8 6 9 4 7 4 6 5 3 8 1 0 1] 2nd variant of sorted array: [0 0 0 1 1 1 1 1 3 4 4 5 6 6 7 7 8 8 8 9]
Druhý demonstrační příklad se do značné míry podobá příkladu předchozímu, ovšem nyní budeme pracovat s polem čísel s plovoucí řádovou čárkou, konkrétně s datovým typem float64. Až na rozdílný způsob inicializace hodnot se tento příklad podobá příkladu předchozímu. Jeho zdrojový kód naleznete na adrese https://github.com/tisnik/go-root/blob/master/article24/14_float_sort.go:
package main
import (
"fmt"
"math"
"sort"
)
func printArray(prefix string, numbers []float64) {
var state string
if sort.Float64sAreSorted(numbers) {
state = "sorted"
} else {
state = "unsorted"
}
fmt.Printf("%s variant of %s array: %v\n", prefix, state, numbers)
}
func main() {
numbers := make([]float64, 20)
for i := 0; i < len(numbers); i++ {
numbers[i] = math.Sin(float64(i) * math.Pi / float64(len(numbers)))
}
printArray("1st", numbers)
sort.Float64s(numbers)
printArray("2nd", numbers)
}
Výsledek činnosti tohoto příkladu:
1st variant of unsorted array: [0 0.15643446504023087 0.3090169943749474 0.45399049973954675 0.5877852522924731 0.7071067811865475 0.8090169943749475 0.8910065241883678 0.9510565162951535 0.9876883405951377 1 0.9876883405951378 0.9510565162951536 0.8910065241883679 0.8090169943749475 0.7071067811865477 0.5877852522924732 0.45399049973954686 0.3090169943749475 0.15643446504023098] 2nd variant of sorted array: [0 0.15643446504023087 0.15643446504023098 0.3090169943749474 0.3090169943749475 0.45399049973954675 0.45399049973954686 0.5877852522924731 0.5877852522924732 0.7071067811865475 0.7071067811865477 0.8090169943749475 0.8090169943749475 0.8910065241883678 0.8910065241883679 0.9510565162951535 0.9510565162951536 0.9876883405951377 0.9876883405951378 1]
Třetí příklad je již nepatrně složitější, protože se v něm pokusíme o načtení textového souboru, rozdělení obsahu tohoto souboru na jednotlivá slova a následně o lexikografické seřazení těchto slov. V první části je nutné načíst soubor a rozdělit ho na slova. To se provede takto:
reader, err := os.Open(filename)
if err != nil {
log.Fatal(err)
}
defer reader.Close()
bufferedReader := bufio.NewReader(reader)
words := []string{}
for {
str, err := bufferedReader.ReadString('\n')
if err != nil {
break
} else {
str = strings.Trim(str, "\n")
ws := strings.Split(str, " ")
words = append(words, ws...)
}
}
func append(slice []Type, elems ...Type) []Type
Zápisem:
words = append(words, ws...)
je možné zajistit, že se řez řetězců rozdělí a jeho jednotlivé prvky se do funkce append předají jako samostatné parametry.
Úplný zdrojový kód tohoto příkladu vypadá následovně:
package main
import (
"bufio"
"fmt"
"log"
"os"
"sort"
"strings"
)
func printArray(prefix string, values []string) {
var state string
if sort.StringsAreSorted(values) {
state = "sorted"
} else {
state = "unsorted"
}
fmt.Printf("%s variant of %s array:\n", prefix, state)
for _, s := range values {
fmt.Printf(" %s\n", s)
}
}
const filename = "test_input.txt"
func main() {
reader, err := os.Open(filename)
if err != nil {
log.Fatal(err)
}
defer reader.Close()
bufferedReader := bufio.NewReader(reader)
words := []string{}
for {
str, err := bufferedReader.ReadString('\n')
if err != nil {
break
} else {
str = strings.Trim(str, "\n")
ws := strings.Split(str, " ")
words = append(words, ws...)
}
}
printArray("1st", words)
sort.Strings(words)
printArray("2nd", words)
}
Příklad si otestujeme na textovém souboru s následujícím obsahem:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Výsledek činnosti příkladu – nejdříve se vypíše seznam slov a následně se tento seznam seřadí:
1st variant of unsorted array:
Lorem
ipsum
dolor
sit
amet,
consectetur
adipiscing
elit,
sed
do
eiusmod
tempor
incididunt
ut
labore
et
dolore
magna
aliqua.
Ut
enim
ad
minim
veniam,
quis
nostrud
exercitation
ullamco
laboris
nisi
ut
aliquip
ex
ea
commodo
consequat.
Duis
aute
irure
dolor
in
reprehenderit
in
voluptate
velit
esse
cillum
dolore
eu
fugiat
nulla
pariatur.
Excepteur
sint
occaecat
cupidatat
non
proident,
sunt
in
culpa
qui
officia
deserunt
mollit
anim
id
est
laborum.
2nd variant of sorted array:
Duis
Excepteur
Lorem
Ut
ad
adipiscing
aliqua.
aliquip
amet,
anim
aute
cillum
commodo
consectetur
consequat.
culpa
cupidatat
deserunt
do
dolor
dolor
dolore
dolore
ea
eiusmod
elit,
enim
esse
est
et
eu
ex
exercitation
fugiat
id
in
in
in
incididunt
ipsum
irure
labore
laboris
laborum.
magna
minim
mollit
nisi
non
nostrud
nulla
occaecat
officia
pariatur.
proident,
qui
quis
reprehenderit
sed
sint
sit
sunt
tempor
ullamco
ut
ut
velit
veniam,
voluptate
Kromě výše zmíněných funkcí nalezneme v balíčku sort i několik užitečných datových typů a jedno rozhraní:
| # | Typ/rozhraní | Stručný popis |
|---|---|---|
| 1 | Interface | rozhraní, kterou musí splňovat jakákoli kolekce, která má být seřaditelná |
| 2 | IntSlice | implementace (nejenom) rozhraní Interface pro řez celých čísel |
| 3 | Float64Slice | implementace (nejenom) rozhraní Interface pro řez čísel typu float64 |
| 4 | StringSlice | implementace (nejenom) rozhraní Interface pro řez řetězců |
Datové typy xxxSlice umožňují snadnější práci s řezy celých čísel, čísel s plovoucí řádovou čárkou a taktéž s řezy řetězců; například je možné zavolat operaci pro otočení celé sekvence Reverse:
package main
import (
"fmt"
"math/rand"
"sort"
)
func printArray(prefix string, numbers []int) {
var state string
if sort.IntsAreSorted(numbers) {
state = "sorted"
} else {
state = "unsorted"
}
fmt.Printf("%s variant of %s array: %v\n", prefix, state, numbers)
}
func main() {
numbers := make([]int, 20)
for i := 0; i < len(numbers); i++ {
numbers[i] = rand.Int() % 10
}
printArray("1st", numbers)
sort.Sort(sort.Reverse(sort.IntSlice(numbers)))
printArray("2nd", numbers)
}
Univerzální funkce Reverse skutečně otočila i běžný řez celých čísel:
1st variant of unsorted array: [0 1 1 1 7 0 8 8 6 9 4 7 4 6 5 3 8 1 0 1] 2nd variant of unsorted array: [9 8 8 8 7 7 6 6 5 4 4 3 1 1 1 1 1 0 0 0]
Další způsob využití typů xxxSlice spočívá v tom, že je možné daný řez seřadit na základě vlastní callback funkce volané při porovnávání dvou prvků v sekvenci. Používá se přitom metoda nazvaná Slice, které se předá jak sekvence, která se má seřadit, tak i definice příslušné callback funkce:
sort.Slice(numbers, func(i, j int) bool {
return numbers[i] > numbers[j]
})
Výše uvedená callback funkce způsobí, že se sekvence seřadí sestupně:
IntSlice: [0 1 1 1 7 0 8 8 6 9 4 7 4 6 5 3 8 1 0 1] IntSlice: [9 8 8 8 7 7 6 6 5 4 4 3 1 1 1 1 1 0 0 0]
Samozřejmě si opět ukážeme celý zdrojový kód demonstračního příkladu:
package main
import (
"fmt"
"math/rand"
"sort"
)
func printIntSlice(numbers sort.IntSlice) {
fmt.Printf("IntSlice: %v\n", numbers)
}
func main() {
numbers := make([]int, 20)
for i := 0; i < len(numbers); i++ {
numbers[i] = rand.Int() % 10
}
printIntSlice(numbers)
sort.Slice(numbers, func(i, j int) bool {
return numbers[i] > numbers[j]
})
printIntSlice(numbers)
}
Poslední příklad, který se týká přímo balíčku sort, ukazuje, jakým způsobem lze zajistit seřazení pole/řezu obsahujícího uživatelsky definované struktury, zde konkrétně strukturu:
type Role struct {
name string
surname string
}
Seřazení podle jména zajistí nám již známá funkce sort.Slice s vhodně upravenou callback funkcí:
sort.Slice(roles, func(i, j int) bool { return roles[i].name < roles[j].name })
Naopak seřazení podle příjmení bude implementováno takto:
sort.Slice(roles, func(i, j int) bool { return roles[i].surname < roles[j].surname })
Následuje výpis příkladu, který seřadí postavy ze hry Švestka napřed podle jména a potom podle příjmení:
package main
import (
"fmt"
"sort"
)
type Role struct {
name string
surname string
}
func printRoles(roles []Role) {
for i, role := range roles {
fmt.Printf("#%d: %s %s\n", i, role.name, role.surname)
}
}
func main() {
roles := []Role{
Role{"Eliška", "Najbrtová"},
Role{"Jenny", "Suk"},
Role{"Anička", "Šafářová"},
Role{"Sváťa", "Pulec"},
Role{"Blažej", "Motyčka"},
Role{"Eda", "Wasserfall"},
Role{"Přemysl", "Hájek"},
}
fmt.Println("Unsorted:")
printRoles(roles)
fmt.Println("--------------------")
sort.Slice(roles, func(i, j int) bool { return roles[i].name < roles[j].name })
fmt.Println("Sorted by name:")
printRoles(roles)
fmt.Println("--------------------")
sort.Slice(roles, func(i, j int) bool { return roles[i].surname < roles[j].surname })
fmt.Println("Sorted by surname:")
printRoles(roles)
fmt.Println("--------------------")
}
Výsledky:
Unsorted: #0: Eliška Najbrtová #1: Jenny Suk #2: Anička Šafářová #3: Sváťa Pulec #4: Blažej Motyčka #5: Eda Wasserfall #6: Přemysl Hájek -------------------- Sorted by name: #0: Anička Šafářová #1: Blažej Motyčka #2: Eda Wasserfall #3: Eliška Najbrtová #4: Jenny Suk #5: Přemysl Hájek #6: Sváťa Pulec -------------------- Sorted by surname: #0: Přemysl Hájek #1: Blažej Motyčka #2: Eliška Najbrtová #3: Sváťa Pulec #4: Jenny Suk #5: Eda Wasserfall #6: Anička Šafářová --------------------
V balíčku container nalezneme i definici rozhraní Heap, které předepisuje chování datové struktury typu halda (heap), viz též podrobnější popis na Wikipedii – https://en.wikipedia.org/wiki/Heap_%28data_structure%29.
Aby byla halda implementována korektně, musíme pro datový typ, který ji implementuje (zde například StringHeap) implementovat i metody Len, Less, Swap, Push a Pop, například tak, jak je to ukázáno v dalším příkladu:
package main
import (
"container/heap"
"fmt"
)
type StringHeap []string
func (h StringHeap) Len() int {
return len(h)
}
func (h StringHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h StringHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *StringHeap) Push(x interface{}) {
*h = append(*h, x.(string))
}
func (h *StringHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &StringHeap{"foo", "bar", "baz", "zzz", "aaa"}
heap.Init(h)
heap.Push(h, "ZZZ")
heap.Push(h, "AAA")
fmt.Printf("First item: %s\n", (*h)[0])
i := 0
for h.Len() > 0 {
i++
fmt.Printf("item #%d = %s\n", i, heap.Pop(h))
}
}
Při čtení prvků z haldy zjistíme, že prvky jsou automaticky seřazeny:
First item: AAA item #1 = AAA item #2 = ZZZ item #3 = aaa item #4 = bar item #5 = baz item #6 = foo item #7 = zzz
Pokud budeme chtít prozkoumat, jak a na základě jakých kritérií se mění pozice prvků v haldě, můžeme si předchozí příklad nepatrně upravit – přidat do něj trasovací příkazy:
package main
import (
"container/heap"
"fmt"
)
type StringHeap []string
func (h StringHeap) Len() int {
return len(h)
}
func (h StringHeap) Less(i, j int) bool {
fmt.Printf("compare %s < %s\n", h[i], h[j])
return h[i] < h[j]
}
func (h StringHeap) Swap(i, j int) {
fmt.Printf("swap %s <-> %s\n", h[i], h[j])
h[i], h[j] = h[j], h[i]
}
func (h *StringHeap) Push(x interface{}) {
*h = append(*h, x.(string))
}
func (h *StringHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &StringHeap{}
heap.Init(h)
heap.Push(h, "a")
heap.Push(h, "z")
heap.Push(h, "c")
heap.Push(h, "b")
heap.Push(h, "d")
heap.Push(h, "x")
fmt.Println("\n-----------------------------")
fmt.Printf("First item: %s\n", (*h)[0])
i := 0
for h.Len() > 0 {
i++
fmt.Printf("item #%d = %s\n", i, heap.Pop(h))
}
}
Při zápisu a čtení prvků bude docházet k jejich reorganizaci na základě jejich vzájemného porovnání:
compare z < a compare c < a compare b < z swap z <-> b compare b < a compare d < b compare x < c ----------------------------- First item: a swap a <-> x compare c < b compare b < x swap x <-> b compare d < z compare d < x swap x <-> d item #1 = a swap b <-> x compare c < d compare c < x swap x <-> c item #2 = b swap c <-> z compare x < d compare d < z swap z <-> d item #3 = c swap d <-> x compare z < x item #4 = d swap x <-> z item #5 = x swap z <-> z item #6 = z
Zdrojové kódy všech dnes popsaných demonstračních příkladů byly uloženy do 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ě dva megabajty), můžete namísto toho použít odkazy na jednotlivé příklady, které naleznete v následující tabulce:
