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

Obsah

1. Mapy jakožto jeden z nejužitečnějších datových kontejnerů

2. Implementace map v knihovně Go18DS

3. Hešovací mapy

4. Metody Empty, Size, Keys a Values

5. Kontrola typů hodnot, s nimiž se pracuje, v době překladu

6. Mapy založené na červeno-černých stromech

7. Postupná iterace přes všechny prvky uložené do mapy

8. Mapa realizovaná strukturou LinkedHashMap

9. Další chování map zachovávajících pořadí vložení prvků

10. Mapy s obousměrným mapováním – bi-directional map

11. Kontejner typu HashBidiMap

12. Metody Get a GetKey

13. Kontejner typu TreeBidiMap

14. Benchmark pro porovnání různých implementací map

15. Výsledky benchmarku pro mapy s relativně malým počtem prvků

16. Výsledky benchmarku pro větší počet prvků

17. Shrnutí – všechny datové kontejnery poskytované knihovnou Go18DS

18. Všechny implementace kontejnerů poskytovaných knihovnou Go18DS

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

20. Odkazy na Internetu

1. Mapy jakožto jeden z nejužitečnějších datových kontejnerů

Při popisu knihovny Go18DS, která do programovacího jazyka Go přináší podporu pro různé genericky pojaté datové struktury, jsme se seznámili s většinou datových kontejnerů, které tato knihovna programátorům nabízí. Připomeňme si, že se jednalo o seznamy (list), množiny (set), zásobník (stack), stromy (tree) a taktéž o binární haldy (binary heap). První ze zmíněných datových kontejnerů, tedy seznamy, jsou velmi důležité, protože sémanticky rozšiřují možnosti polí a taktéž řezů (slice). V některých aplikacích se používají i množiny, a to například ve chvíli, kdy potřebujeme reprezentovat přítomnost či naopak nepřítomnost určitého prvku, a to nezávisle na jeho umístění v nějaké datové kolekci (nezajímá nás tedy například to, že se jedná o třetí prvek, ale o to, zda takový prvek vůbec existuje; navíc je zaručena unikátnost prvků). Právě množiny jsou v programovacím jazyku Go mnohdy realizovány pomocí vestavěných map, konkrétně map, jejichž prvky jsou typu struct{}, což lze ovšem považovat za (poněkud špinavý) trik.

Výše zmíněné seznamy, množiny, zásobníky nebo stromy nalezneme v prakticky jakémkoli rozsáhlejším programu psaném v jazyce Go, ovšem zdaleka nejužitečnějším datovým typem (datovým kontejnerem) jsou pro vysokoúrovňové aplikace, nikoli nutně pro výpočty a systémové úlohy, mapy (maps). A právě velmi časté používání map v programech psaných v jazyce Go odlišuje tento jazyk například od céčka, kde je pochopitelně možné mapy taktéž implementovat, ovšem kvůli nutnosti manuální správy paměti (a neexistence generických datových typů) se ani zdaleka nejedná o elegantní řešení (typickým problémem je uvolňování prvků z mapy atd.). Mapy jsou skutečně velmi flexibilním a téměř univerzálním datovým typem (či možná lépe řečeno datovou strukturou), který může nahradit například hodnotové objekty (viz například toto známé video, které je orientováno na Clojure), mnohdy se používají namísto pojmenovaných parametrů funkcí (v Pythonu je nazýváme „keyword parametry“, v Go tato možnost chybí) a samozřejmě jsou (alespoň většinou) výsledkem deserializace souborů typu JSON, YAML, XML apod. Na tomto místě je nutné upozornit na to, že mapy, a to i jejich implementace popsané níže, nejsou persistentní datovou strukturou, což znamená, že do nich je možné přidávat prvky, odstraňovat prvky atd. – a tudíž může být problematické bez dalších technik (zámky atd.) mapy sdílet mezi gorutinami.

2. Implementace map v knihovně Go18DS

Existuje poměrně velké množství způsobů implementace map, přesněji řečeno způsobů ukládání dvojic klíč-hodnota do paměti s možností jejich pozdějšího přečtení. Jednotlivé implementace se od sebe odlišují svými základními vlastnostmi, například tím, zda jsou prvky v mapě setříděny na základě svého klíče, zda je naopak zachováno pořadí prvků podle pořadí jejich vkládání do mapy či zda jsou prvky obecně neuspořádány. Liší se i časové složitosti základních operací – tedy operace pro vložení prvku do mapy a operace pro získání prvku na základě jeho klíče. Navíc v některých případech vyžadujeme specifické chování mapy, například možnost mapování nejenom v jednom směru (tedy klasické klíč→hodnota), ale i ve směru opačném (hodnota→klíč). Toto chování realizují mapy, v jejichž jméně se objevuje zkratka „bidi“ (neboli bi-directional). Všechny implementace map dostupné v knihovně Go18DS jsou vypsány v následujícím seznamu:

1. HashMap
2. TreeMap
3. LinkedHashMap
4. HashBidiMap
5. TreeBidiMap

3. Hešovací mapy

Nejprve si popišme hešovací mapy (hash maps), protože ty se v praxi používají velmi často. V knihovně Go18DS jsou standardní hešovací mapy realizovány v balíčku s plným jménem github.com/daichi-m/go18ds/maps/hashmap. Při konstrukci prázdné hešovací mapy je zapotřebí specifikovat jak typ klíčů, tak i typ hodnot – je tomu tak z toho důvodu, že knihovna Go18DS je založena na použití generických datových typů. Způsob volání konstruktoru hešovací mapy vypadá následovně:

m := mapImpl.New[string, string]()

Dvojice klíč-hodnota se do hešovací mapy (ale i do dalších typů map) přidává metodou Put, kterou lze zavolat velmi snadno (ovšem překladač provede kontrolu typů):

m.Put("klíč", "hodnota")

V dnešním prvním demonstračním příkladu je ukázána jak konstrukce mapy, tak i její naplnění dvanácti dvojicemi klíč-hodnota. Jak klíče, tak i hodnoty musí být typu řetězec (v jazyce Go tedy string):

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Po spuštění tohoto demonstračního příkladu se postupně začne vypisovat obsah hešovací mapy, a to od prázdné mapy vytvořené konstruktorem až do situace, kdy je mapa naplněna dvanácti dvojicemi:

HashMap
map[]
HashMap
map[Leden:Ianuarius]
HashMap
map[Leden:Ianuarius Únor:Februarius]
HashMap
map[Březen:Martius Leden:Ianuarius Únor:Februarius]
HashMap
map[Březen:Martius Duben:Aprilis Leden:Ianuarius Únor:Februarius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius Červenec:Iulius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Únor:Februarius Červen:Iunius Červenec:Iulius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
HashMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Prosinec:December Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]

Pro přečtení prvku z mapy na základě klíče se používá metoda Get. Tato metoda vrací dvě hodnoty – samotnou hodnotu přečteného prvku (pokud byl prvek s uvedeným klíčem nalezen) a pravdivostní hodnotu true/false značící, zda prvek byl či naopak nebyl nalezen. Pokud prvek nalezen nebyl, je první vrácená hodnota „nulovou“ hodnotou platnou pro daný typ (0 u numerických typů, prázdný řetězec u řetězců, prázdné pole u polí a řezů atd).

Například pro mapu naplněnou názvy všech dvanácti měsíců v roce vypíšou následující dvě volání:

fmt.Println(m.Get("Leden"))
fmt.Println(m.Get("Srpenec"))

dvojici řádků:

Ianuarius true
 false

přičemž na druhém řádku je před hodnotou false prázdný řetězec oddělený mezerou.

Opět se podívejme na úplný zdrojový kód demonstračního příkladu, který nejprve naplní hešovací mapu a následně se z ní pokusí přečíst dva prvky:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        fmt.Println(m.Get("Leden"))
        fmt.Println(m.Get("Srpenec"))
}

4. Metody Empty, Size, Keys a Values

Všechny implementace map a tedy pochopitelně i hešovací mapy nabízí i další užitečné metody. Jedná se o metodu Emptu, která vrací (podle očekávání) hodnotu true/false podle toho, zda je mapa zcela prázdná či nikoli, dále o metodu Size vracející počet dvojic klíč-hodnota uložených do mapy. Metoda Keys vrací řez se všemi klíči a metoda Values řez se všemi hodnotami. Použití těchto čtyř metod si ukážeme na dalším demonstračním příkladu:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
        }
 
        fmt.Println("Metadata")
        fmt.Println("Empty?", m.Empty())
        fmt.Println("Size", m.Size())
 
        fmt.Println()
        fmt.Println("Keys")
        fmt.Printf("%T\n", m.Keys())
        fmt.Println(m.Keys())
 
        fmt.Println()
        fmt.Println("Values")
        fmt.Printf("%T\n", m.Values())
        fmt.Println(m.Values())
}

Po překladu a spuštění tohoto demonstračního příkladu se vypíšou metainformace o hešovací mapě, tedy zda je mapa prázdná, a kolik má prvků. Dále se vypíše řez se všemi klíči a následně i řez s hodnotami. Opět si povšimněte, že prvky nejsou v hešovací mapě nijak (z našeho pohledu rozumně) seřazeny:

Metadata
Empty? false
Size 12
 
Keys
[]string
[Leden Duben Květen Červen Červenec Říjen Únor Březen Srpen Září Listopad Prosinec]
 
Values
[]string
[Iunius Iulius October Ianuarius Aprilis Maius September November December Februarius Martius Augustus]

5. Kontrola typů hodnot, s nimiž se pracuje, v době překladu

V tomto seriálu jsme si již řekli, že generické datové typy jsou v jazyce Go navrženy a implementovány takovým způsobem, že se kontroly typů provádí již v době překladu, nikoli v době běhu. Podívejme se tedy, co se stane ve chvíli, kdy se pokusíme do mapy, jejíž hodnoty mají být typu int (celé číslo) uložit prvky pod klíčem typu string (řetězec), ovšem s hodnotou taktéž typu string a nikoli int:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                ...
                ...
                ...
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                ...
                ...
                ...
                "December",
        }
 
        m := mapImpl.New[string, int]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Překladač v tomto detekuje a vypíše chybu při pokusu o provedení operace Put:

./hashmap01error.go:50:16: cannot use lat[i] (variable of type string) as type int in argument to m.Put

Podobně je překladači známo, jakého typu budou hodnoty vrácené operací Get. V dalším příkladu se pokusíme o přiřazení výsledku do proměnné neočekávaného a nekompatibilního typu:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                ...
                ...
                ...
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                ...
                ...
                ...
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        var name int
 
        name, ok := m.Get("Leden")
        fmt.Println(name, ok)
}

Překladač v tomto případě opět korektně rozpozná nekompatibilní datový typ:

./hashmap02error.go:57:14: cannot use m.Get("Leden") (value of type string) as type int in assignment

6. Mapy založené na červeno-černých stromech

Druhým typem mapy, s nímž se v knihovně Go18DS můžeme setkat, jsou mapy interně založené na červeno-černých stromech (red-black tree). Prvky jsou v těchto stromech automaticky zařazeny podle hodnoty klíče (hodnoty tedy musí být porovnatelné operací „menší než“ atd. – ostatně příslušný komparátor se vybírá již při konstrukci prázdné mapy) a tedy všechny hodnoty mohou být následně získány a vypsány v seřazené podobě. Podívejme se nyní na konstrukci tohoto typu mapy i způsobu řazení prvků v ní:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treemap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWithStringComparator[string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Po spuštění tohoto demonstračního příkladu získáme obsah mapy, do které se prvky postupně přidávají a zařazují na své místo na základě porovnání hodnot klíčů:

TreeMap
map[]
TreeMap
map[Leden:Ianuarius]
TreeMap
map[Leden:Ianuarius Únor:Februarius]
TreeMap
map[Březen:Martius Leden:Ianuarius Únor:Februarius]
TreeMap
map[Březen:Martius Duben:Aprilis Leden:Ianuarius Únor:Februarius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
TreeMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Prosinec:December Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]

Povšimněte si, že prvky jsou na konci seřazeny podle abecedy, ovšem tedy s tím „malým“ problémem, že řazení neodpovídá tuzemské normě.

Podívejme se ještě na chování operace Get, které je totožné s hešovacími mapami:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treemap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWithStringComparator[string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        fmt.Println(m.Get("Leden"))
        fmt.Println(m.Get("Srpenec"))
}

Výsledky obou operací Get jsou vypsány na dvojici řádků:

Ianuarius true
 false

Mapy založené na červeno-černých stromech nabízí i nám již známé metody Empty, Size, Keys a Values:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treemap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWithStringComparator[string]()
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
        }
 
        fmt.Println("Metadata")
        fmt.Println("Empty?", m.Empty())
        fmt.Println("Size", m.Size())
 
        fmt.Println()
        fmt.Println("Keys")
        fmt.Printf("%T\n", m.Keys())
        fmt.Println(m.Keys())
 
        fmt.Println()
        fmt.Println("Values")
        fmt.Printf("%T\n", m.Values())
        fmt.Println(m.Values())
}

Výsledky získané po spuštění tohoto příkladu:

Metadata
Empty? false
Size 12
 
Keys
[]string
[Březen Duben Květen Leden Listopad Prosinec Srpen Září Únor Červen Červenec Říjen]
 
Values
[]string
[Martius Aprilis Maius Ianuarius November December Augustus September Februarius Iunius Iulius October]

7. Postupná iterace přes všechny prvky uložené do mapy

Vzhledem k tomu, že mapy založené na červeno-černých stromech zajišťují přesně dané pořadí uložení prvků ve stromu, je možné těmito prvky postupně procházet s využitím iterátorů. To je koncept, s nímž jsme se již setkali u dalších datových typů v knihovně Go18DS, takže jen v krátkosti se podívejme na použití iterátoru:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treemap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWithStringComparator[string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        it := m.Iterator()
        for it.Next() {
                key, value := it.Key(), it.Value()
                fmt.Printf("%-10s \t %-10s \t %T\n", key, value, value)
        }
}

Povšimněte si, že v každé iteraci získáme jak klíč, tak i hodnotu prvku:

Březen           Martius         string
Duben            Aprilis         string
Květen           Maius           string
Leden            Ianuarius       string
Listopad         November        string
Prosinec         December        string
Srpen            Augustus        string
Září             September       string
Únor             Februarius      string
Červen           Iunius          string
Červenec         Iulius          string
Říjen            October         string

8. Mapa realizovaná strukturou LinkedHashMap

Třetí způsob implementace mapy v knihovně Go18DS se jmenuje LinkedHashMap. Interně se jedná o kombinaci hešovací mapy (tato část je použita pro uložení hodnot) a obousměrně vázaného seznamu pro uložení vzájemných uspořádání (seřazení) prvků. Právě díky použití seznamu je zajištěno, že je zachováno pořadí prvků – prvky je možné získat v takovém pořadí, v jakém byly do mapy vloženy. K dispozici je pochopitelně i možnost smazání prvku atd.

Opět si pochopitelně ukážeme, jak se tyto mapy použijí v praxi. Jejich konstrukce a naplnění vypadá následovně:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/linkedhashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Ze zpráv vypsaných tímto demonstračním příkladem je patrné, že prvky jsou uloženy v takovém pořadí, které odpovídá jejich vložení do mapy:

LinkedHashMap
map[]
LinkedHashMap
map[Leden:Ianuarius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius Srpen:Augustus]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius Srpen:Augustus Září:September]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius Srpen:Augustus Září:September Říjen:October]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius Srpen:Augustus Září:September Říjen:October Listopad:November]
LinkedHashMap
map[Leden:Ianuarius Únor:Februarius Březen:Martius Duben:Aprilis Květen:Maius Červen:Iunius Červenec:Iulius Srpen:Augustus Září:September Říjen:October Listopad:November Prosinec:December]

9. Další chování map zachovávajících pořadí vložení prvků

V demonstračních příkladech uvedených v této kapitole bude ukázáno další chování map, které zachovávají pořadí vložení prvků, tedy map implementovaných balíčkem github.com/daichi-m/go18ds/maps/linkedhashmap. Nejprve si ověřme, že metoda Get se chová stejně, jako u dalších typů map:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/linkedhashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        fmt.Println(m.Get("Leden"))
        fmt.Println(m.Get("Srpenec"))
}

S očekávaným výsledkem:

Ianuarius true
 false

Dále se podívejme na metody Empty, Size, Keys a Values, které již známe z předchozího textu:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/linkedhashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
        }
 
        fmt.Println("Metadata")
        fmt.Println("Empty?", m.Empty())
        fmt.Println("Size", m.Size())
 
        fmt.Println()
        fmt.Println("Keys")
        fmt.Printf("%T\n", m.Keys())
        fmt.Println(m.Keys())
 
        fmt.Println()
        fmt.Println("Values")
        fmt.Printf("%T\n", m.Values())
        fmt.Println(m.Values())
}

Výsledky by opět neměly být překvapující (za zmínku stojí pořadí vrácených klíčů i prvků):

Metadata
Empty? false
Size 12
 
Keys
[]string
[Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec]
 
Values
[]string
[Ianuarius Februarius Martius Aprilis Maius Iunius Iulius Augustus September October November December]

A nakonec si ukážeme iteraci přes všechny prvky uložené v mapě:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/linkedhashmap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        it := m.Iterator()
        for it.Next() {
                key, value := it.Key(), it.Value()
                fmt.Printf("%-10s \t %-10s \t %T\n", key, value, value)
        }
}

Iteruje se přes prvky se zachováním pořadí jejich vložení do mapy:

Leden            Ianuarius       string
Únor             Februarius      string
Březen           Martius         string
Duben            Aprilis         string
Květen           Maius           string
Červen           Iunius          string
Červenec         Iulius          string
Srpen            Augustus        string
Září             September       string
Říjen            October         string
Listopad         November        string
Prosinec         December        string

10. Mapy s obousměrným mapováním – bi-directional map

Všechny tři implementace map, které jsme si až doposud popsali, tedy konkrétně balíčky hashmap, treemap i linkedhashmap, realizovaly klasicky pojaté mapy, u nichž je zajištěna unikátnost klíčů. To znamená, že v mapě se může každý klíč použít maximálně jen jedenkrát, čímž je zaručeno, že lze jednoznačně pro zadaný klíč přečíst hodnotu (tedy vlastní mapování), popř. zjistit, že taková hodnota neexistuje. Ovšem nic nám ve skutečnosti nebrání ve vytvoření odlišné, poněkud sofistikovanější datové struktury, u níž bude možné jak přečíst hodnotu na základě klíče, tak i klíč na základě hodnoty, tedy provést mapování opačným směrem. A právě tyto sice poněkud méně často používané, ale stále velmi užitečné datové kontejnery nalezneme i v knihovně Go18DS. Konkrétně se jedná o kontejnery HashBidiMap a TreeBidiMap, kde „bidi“ znamená „bi-directional“.

11. Kontejner typu HashBidiMap

Podívejme se nyní na kontejner typu HashBidiMap, což je implementace „obousměrné“ mapy, v níž se interně prvky rozřazují na základě hešovací funkce aplikované na hodnoty klíčů. Nejprve si ukažme konstrukci této mapy a použití nám již velmi dobře známé metody Put určené pro vložení prvku do mapy:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashbidimap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Po spuštění tohoto demonstračního příkladu je patrné, že se skutečně používá hešovací funkce, která prvky „rozhodí“:

HashBidiMap
{map[]}
HashBidiMap
{map[Leden:Ianuarius]}
HashBidiMap
{map[Leden:Ianuarius Únor:Februarius]}
HashBidiMap
{map[Březen:Martius Leden:Ianuarius Únor:Februarius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Leden:Ianuarius Únor:Februarius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius Červenec:Iulius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Únor:Februarius Červen:Iunius Červenec:Iulius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]}
HashBidiMap
{map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Prosinec:December Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]}

12. Metody Get a GetKey

U „obousměrných“ map nalezneme jak již nám dobře známou operaci Get, tak i operaci GetKey, která vrátí klíč na základě zadané hodnoty (což je ono opačné mapování). Podívejme se nyní na chování této operace:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashbidimap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        fmt.Println(m.Get("Leden"))
        fmt.Println(m.Get("Srpenec"))
 
        fmt.Println()
        fmt.Println(m.GetKey("Ianuarius"))
        fmt.Println(m.GetKey("xyzzy"))
}

Výsledek všech čtyř řádků s operacemi Get a GetKey:

Ianuarius true
 false
 
Leden true
 false

Všechny ostatní operace jsou i v případě „obousměrných“ map zachovány:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashbidimap"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.New[string, string]()
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
        }
 
        fmt.Println("Metadata")
        fmt.Println("Empty?", m.Empty())
        fmt.Println("Size", m.Size())
 
        fmt.Println()
        fmt.Println("Keys")
        fmt.Printf("%T\n", m.Keys())
        fmt.Println(m.Keys())
 
        fmt.Println()
        fmt.Println("Values")
        fmt.Printf("%T\n", m.Values())
        fmt.Println(m.Values())
}

Výsledky:

Metadata
Empty? false
Size 12
 
Keys
[]string
[Listopad Leden Únor Květen Červen Srpen Září Březen Duben Červenec Říjen Prosinec]
 
Values
[]string
[Martius Iunius October December September November Ianuarius Februarius Aprilis Maius Iulius Augustus]

Ukázka toho, že kvůli nutnosti zachování unikátnosti hodnot se operací m.Put(4, 1) do mapy nevloží další prvek, ale přepíše se prvek stávající:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/hashbidimap"
)
 
func main() {
        m := mapImpl.New[int, int]()
 
        m.Put(1, 1)
        m.Put(2, 2)
        m.Put(3, 3)
 
        fmt.Println("Size", m.Size())
        fmt.Println("Keys", m.Keys())
        fmt.Println("Values", m.Values())
 
        fmt.Println()
 
        m.Put(4, 1)
 
        fmt.Println("Size", m.Size())
        fmt.Println("Keys", m.Keys())
        fmt.Println("Values", m.Values())
}

Výsledky:

Size 3
Keys [1 2 3]
Values [1 2 3]
 
Size 3
Keys [4 2 3]
Values [1 2 3]

13. Kontejner typu TreeBidiMap

Poslední implementací mapy v knihovně Go18DS je kontejner typu TreeBidiMap, tedy „obousměrná“ mapa s uložením prvků do červeno-černého stromu. Mapa by tedy měla prvky řadit podle jejich klíčů, o čemž se ostatně můžeme velmi snadno přesvědčit (povšimněte si nutnosti specifikace komparátoru pro porovnávání hodnot):

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treebidimap"
        "github.com/daichi-m/go18ds/utils"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWith(utils.StringComparator, utils.StringComparator)
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
}

Výsledkem je mapa, jejíž prvky jsou v každém okamžiku správně seřazeny podle klíčů:

TreeBidiMap
map[]
TreeBidiMap
map[Leden:Ianuarius]
TreeBidiMap
map[Leden:Ianuarius Únor:Februarius]
TreeBidiMap
map[Březen:Martius Leden:Ianuarius Únor:Februarius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Leden:Ianuarius Únor:Februarius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]
TreeBidiMap
map[Březen:Martius Duben:Aprilis Květen:Maius Leden:Ianuarius Listopad:November Prosinec:December Srpen:Augustus Září:September Únor:Februarius Červen:Iunius Červenec:Iulius Říjen:October]

Chování metod Get a GetKey je zachováno:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treebidimap"
        "github.com/daichi-m/go18ds/utils"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWith(utils.StringComparator, utils.StringComparator)
        fmt.Println(m)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
                fmt.Println(m)
        }
 
        fmt.Println()
        fmt.Println(m.Get("Leden"))
        fmt.Println(m.Get("Srpenec"))
 
        fmt.Println()
        fmt.Println(m.GetKey("Ianuarius"))
        fmt.Println(m.GetKey("xyzzy"))
}

Výsledky:

Ianuarius true
 false
 
Leden true
 false

Stejně je zachováno i chování metod Empty, Size, Keys a Values:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treebidimap"
        "github.com/daichi-m/go18ds/utils"
)
 
func main() {
        cz := []string{
                "Leden",
                "Únor",
                "Březen",
                "Duben",
                "Květen",
                "Červen",
                "Červenec",
                "Srpen",
                "Září",
                "Říjen",
                "Listopad",
                "Prosinec",
        }
 
        lat := []string{
                "Ianuarius",
                "Februarius",
                "Martius",
                "Aprilis",
                "Maius",
                "Iunius",
                "Iulius",
                "Augustus",
                "September",
                "October",
                "November",
                "December",
        }
 
        m := mapImpl.NewWith(utils.StringComparator, utils.StringComparator)
 
        for i := 0; i < len(cz); i++ {
                m.Put(cz[i], lat[i])
        }
 
        fmt.Println("Metadata")
        fmt.Println("Empty?", m.Empty())
        fmt.Println("Size", m.Size())
 
        fmt.Println()
        fmt.Println("Keys")
        fmt.Printf("%T\n", m.Keys())
        fmt.Println(m.Keys())
 
        fmt.Println()
        fmt.Println("Values")
        fmt.Printf("%T\n", m.Values())
        fmt.Println(m.Values())
}

Výsledky:

Ovšem pozor – hodnoty jsou taktéž vráceny formou seřazeného řezu!:

Metadata
Empty? false
Size 12
 
Keys
[]string
[Březen Duben Květen Leden Listopad Prosinec Srpen Září Únor Červen Červenec Říjen]
 
Values
[]string
[Aprilis Augustus December Februarius Ianuarius Iulius Iunius Maius Martius November October September]

A konečně chování obousměrné mapy při snaze o vložení prvku s hodnotou, která již v mapě existuje:

package main
 
import (
        "fmt"
 
        mapImpl "github.com/daichi-m/go18ds/maps/treebidimap"
        "github.com/daichi-m/go18ds/utils"
)
 
func main() {
        m := mapImpl.NewWith(utils.NumberComparator[int], utils.NumberComparator[int])
 
        m.Put(1, 1)
        m.Put(2, 2)
        m.Put(3, 3)
 
        fmt.Println("Size", m.Size())
        fmt.Println("Keys", m.Keys())
        fmt.Println("Values", m.Values())
 
        fmt.Println()
 
        m.Put(4, 1)
 
        fmt.Println("Size", m.Size())
        fmt.Println("Keys", m.Keys())
        fmt.Println("Values", m.Values())
}

Výsledek by nás již neměl překvapit:

Size 3
Keys [1 2 3]
Values [1 2 3]
 
Size 3
Keys [2 3 4]
Values [1 2 3]

14. Benchmark pro porovnání různých implementací map

Víme již, že jednotlivé implementace map se od sebe odlišují především svým chováním (jak jsou uspořádány prvky atd.). Liší se však i vnitřní strukturou a tím pádem i složitostí jednotlivých operací. Pro zjištění časové složitosti obou základních operací, tedy Put a Get, vznikl následující benchmark:

package main
 
import (
        "testing"
 
        "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/utils"
)
 
const max = 1000
 
func filledMapCheck(b *testing.B, m maps.Map[int, int]) {
        if m.Empty() {
                b.Fail()
        }
 
        if m.Size() != b.N {
                b.Fail()
        }
}
 
func BenchmarkHashMapPut(b *testing.B) {
        m := hashmap.New[int, int]()
        for i := 0; i < b.N; i++ {
                m.Put(i, i)
        }
 
        filledMapCheck(b, m)
}
 
func BenchmarkLinkedHashMapPut(b *testing.B) {
        m := linkedhashmap.New[int, int]()
        for i := 0; i < b.N; i++ {
                m.Put(i, i)
        }
 
        filledMapCheck(b, m)
}
 
func BenchmarkTreeMapPut(b *testing.B) {
        m := treemap.NewWithIntComparator[int]()
        for i := 0; i < b.N; i++ {
                m.Put(i, i)
        }
 
        filledMapCheck(b, m)
}
 
func BenchmarkHashBidiMapPut(b *testing.B) {
        m := hashbidimap.New[int, int]()
        for i := 0; i < b.N; i++ {
                m.Put(i, i)
        }
 
        filledMapCheck(b, m)
}
 
func BenchmarkTreeBidiMapPut(b *testing.B) {
        m := treebidimap.NewWith(utils.NumberComparator[int], utils.NumberComparator[int])
        for i := 0; i < b.N; i++ {
                m.Put(i, i)
        }
 
        filledMapCheck(b, m)
}
 
func fillInMap(m maps.Map[int, int], max int) {
        for i := 0; i < max; i++ {
                m.Put(i, i)
        }
}
 
func getFromMap(b *testing.B, m maps.Map[int, int], max int) {
        for i := 0; i < b.N; i++ {
                for j := 0; j < max; j++ {
                        val, found := m.Get(j)
                        if !found {
                                b.Fail()
                        }
                        if val != j {
                                b.Fail()
                        }
                }
        }
}
 
func BenchmarkHashMapGet(b *testing.B) {
        m := hashmap.New[int, int]()
 
        fillInMap(m, max)
        getFromMap(b, m, max)
}
 
func BenchmarkLinkedHashMapGet(b *testing.B) {
        m := linkedhashmap.New[int, int]()
 
        fillInMap(m, max)
        getFromMap(b, m, max)
}
 
func BenchmarkTreeMapGet(b *testing.B) {
        m := treemap.NewWithIntComparator[int]()
 
        fillInMap(m, max)
        getFromMap(b, m, max)
}
 
func BenchmarkHashBidiMapGet(b *testing.B) {
        m := hashbidimap.New[int, int]()
 
        fillInMap(m, max)
        getFromMap(b, m, max)
}
 
func BenchmarkTreeBidiMapGet(b *testing.B) {
        m := treebidimap.NewWith(utils.NumberComparator[int], utils.NumberComparator[int])
 
        fillInMap(m, max)
        getFromMap(b, m, max)
}

15. Výsledky benchmarku pro mapy s relativně malým počtem prvků

Pro zjištění, jak se chová kód, který ještě nebyl dostatečně „zahřátý“ (využití cache atd.) zavoláme benchmark s nastavením N=1:

$ go test -bench=.  -benchtime=1x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkHashMapPut-8                  1              1565 ns/op
BenchmarkLinkedHashMapPut-8            1              4550 ns/op
BenchmarkTreeMapPut-8                  1              1189 ns/op
BenchmarkHashBidiMapPut-8              1              4326 ns/op
BenchmarkTreeBidiMapPut-8              1              1929 ns/op
BenchmarkHashMapGet-8                  1            102056 ns/op
BenchmarkLinkedHashMapGet-8            1            147455 ns/op
BenchmarkTreeMapGet-8                  1            195639 ns/op
BenchmarkHashBidiMapGet-8              1            235507 ns/op
BenchmarkTreeBidiMapGet-8              1            419239 ns/op

Částečně podle předpokladů je nejpomalejší operací získání hodnoty z obousměrné mapy založené na stromech.

Benchmark následně spustíme s N=100 (mapy spíše malé velikosti):

$ go test -bench=.  -benchtime=100x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkHashMapPut-8                100               192.6 ns/op
BenchmarkLinkedHashMapPut-8          100               306.3 ns/op
BenchmarkTreeMapPut-8                100               216.8 ns/op
BenchmarkHashBidiMapPut-8            100               415.2 ns/op
BenchmarkTreeBidiMapPut-8            100               528.6 ns/op
BenchmarkHashMapGet-8                100             20457 ns/op
BenchmarkLinkedHashMapGet-8          100             16144 ns/op
BenchmarkTreeMapGet-8                100             63647 ns/op
BenchmarkHashBidiMapGet-8            100             16347 ns/op
BenchmarkTreeBidiMapGet-8            100             53554 ns/op

U hashmap prozatím nedojde ke kolizím a proto je práce s nimi nejrychlejší.

Totéž platí pro N=10000

$ go test -bench=.  -benchtime=10000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkHashMapPut-8              10000                72.59 ns/op
BenchmarkLinkedHashMapPut-8        10000               174.4 ns/op
BenchmarkTreeMapPut-8              10000               170.7 ns/op
BenchmarkHashBidiMapPut-8          10000               197.6 ns/op
BenchmarkTreeBidiMapPut-8          10000               507.0 ns/op
BenchmarkHashMapGet-8              10000             15136 ns/op
BenchmarkLinkedHashMapGet-8        10000             14571 ns/op
BenchmarkTreeMapGet-8              10000             61552 ns/op
BenchmarkHashBidiMapGet-8          10000             15729 ns/op
BenchmarkTreeBidiMapGet-8          10000             50818 ns/op

Stále je Put nejrychlejší pro hashmapu, což znamená, že i pro 10000 prvků je počet kolizí pravděpodobně velmi malý.

16. Výsledky benchmarku pro větší počet prvků

Hodnotu N nyní zvýšíme na 1000000×, čímž mj. zvýšíme počet kolizí v případě zahešovaných klíčů. A výsledek je patrný – operace Put již u hešovacích map není nejrychlejší, naopak je nejrychlejší prosté zařazování prvků do stromové struktury. Na druhou stranu je však získání prvků ze stromu operací Get výrazně nejpomalejší:

$ go test -bench=.  -benchtime=1000000x
 
goos: linux
goarch: amd64
pkg: x
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkHashMapPut-8            1000000               333.6 ns/op
BenchmarkLinkedHashMapPut-8      1000000               361.8 ns/op
BenchmarkTreeMapPut-8            1000000               232.4 ns/o
BenchmarkHashBidiMapPut-8        1000000               486.7 ns/op
BenchmarkTreeBidiMapPut-8        1000000               657.2 ns/op
BenchmarkHashMapGet-8            1000000             17671 ns/op
BenchmarkLinkedHashMapGet-8      1000000             18113 ns/op
BenchmarkTreeMapGet-8            1000000             71979 ns/op
BenchmarkHashBidiMapGet-8        1000000             20001 ns/op
BenchmarkTreeBidiMapGet-8        1000000             59455 ns/op

17. Shrnutí – všechny datové kontejnery poskytované knihovnou Go18DS

V následující tabulce jsou uvedeny všechny datové kontejnery, které jsou poskytované knihovnou Go18DS. U každého kontejneru je uveden i odkaz na odpovídající článek a kapitolu s popisem daného kontejneru:

18. Všechny implementace kontejnerů poskytovaných knihovnou Go18DS

Každý z kontejnerů zmíněných v předchozí kapitole existuje v několika implementacích, které se od sebe odlišují svou interní strukturou a mnohdy i rozdílným chováním (viz příklady map s prvky bez specifikovaného pořadí, setříděnými prvky podle klíče nebo s prvky uspořádanými podle toho, kdy byl prvek do mapy vložen). Všechny tyto implementace jsme si již popsali a jsou vypsány v další tabulce:

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:

20. Odkazy na Internetu

1. Genfuncs – implements various functions utilizing Go's Generics to help avoid writing boilerplate code
   https://github.com/nwillc/genfuncs
2. Go18DS (Go 1.18+ Data Structures)
   https://github.com/daichi-m/go18ds
3. TreeMap v2
   https://github.com/igrmk/treemap
4. Fp-go is a collection of Functional Programming helpers powered by Golang 1.18+ generics
   https://github.com/repeale/fp-go
5. The Go Programming Language Specification
   https://go.dev/ref/spec
6. Generics in Go
   https://bitfieldconsultin­g.com/golang/generics
7. Tutorial: Getting started with generics
   https://go.dev/doc/tutorial/generics
8. Type parameters in Go
   https://bitfieldconsultin­g.com/golang/type-parameters
9. Go Data Structures: Binary Search Tree
   https://flaviocopes.com/golang-data-structure-binary-search-tree/
10. Gobs of data
    https://blog.golang.org/gobs-of-data
11. How the Go runtime implements maps efficiently (without generics)
    https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics
12. Go 1.18 Release Notes
    https://golang.org/doc/go1.18
13. Go 1.17 Release Notes
    https://golang.org/doc/go1.17
14. Go 1.16 Release Notes
    https://golang.org/doc/go1.16
15. Go 1.15 Release Notes
    https://golang.org/doc/go1.15
16. Go 1.14 Release Notes
    https://golang.org/doc/go1.14
17. Go 1.13 Release Notes
    https://golang.org/doc/go1.13
18. Go 1.12 Release Notes
    https://golang.org/doc/go1.12
19. Go 1.11 Release Notes
    https://golang.org/doc/go1.11
20. Go 1.11 Release Notes
    https://golang.org/doc/go1.11
21. Go 1.10 Release Notes
    https://golang.org/doc/go1.10
22. Go 1.9 Release Notes
    https://golang.org/doc/go1.9
23. Go 1.8 Release Notes
    https://golang.org/doc/go1.8
24. A Proposal for Adding Generics to Go
    https://go.dev/blog/generics-proposal
25. Proposal: Go should have generics
    https://github.com/golang/pro­posal/blob/master/design/15292-generics.md
26. Know Go: Generics (Kniha)
    https://bitfieldconsultin­g.com/books/generics
27. Go 1.18 Generics based slice package
    https://golangexample.com/go-1–18-generics-based-slice-package/
28. The missing slice package
    https://github.com/ssoroka/slice
29. Dlouho očekávaná novinka v Go 1.18 – generické datové typy
    https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–18-genericke-datove-typy/
30. Dlouho očekávaná novinka v Go 1.18 – generické datové typy (dokončení)
    https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–8-genericke-datove-typy-dokonceni/
31. Generické datové typy v jazyce Go?
    https://www.root.cz/clanky/genericke-datove-typy-v-jazyce-go/
32. GoDS (Go Data Structures)
    https://github.com/emirpasic/gods
33. Binární halda
    https://cs.wikipedia.org/wi­ki/Bin%C3%A1rn%C3%AD_halda
34. Binární strom
    https://cs.wikipedia.org/wi­ki/Bin%C3%A1rn%C3%AD_strom
35. AVL-strom
    https://cs.wikipedia.org/wiki/AVL-strom
36. Červeno-černý strom
    https://cs.wikipedia.org/wi­ki/%C4%8Cerveno-%C4%8Dern%C3%BD_strom
37. B-strom
    https://cs.wikipedia.org/wiki/B-strom