Obsah
1. Mapy jakožto jeden z nejužitečnějších datových kontejnerů
2. Implementace map v knihovně Go18DS
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
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
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:
- HashMap
- TreeMap
- LinkedHashMap
- HashBidiMap
- 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:
Kontejner | Překlad |
---|---|
List | seznam |
Set | množina |
Stack | zásobník |
Tree | strom |
BinaryHeap | binární halda |
Map | mapa |
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:
Rozhraní (typ kontejneru) | Implementace kontejneru |
---|---|
List | ArrayList SinglyLinkedList DoublyLinkedList |
Set | HashSet TreeSet LinkedHashSet |
Stack | LinkedListStack ArrayStack |
Tree | RedBlackTree AVLTree BTree BinaryHeap |
Map | HashMap TreeMap LinkedHashMap HashBidiMap TreeBidiMap |
19. Repositář s demonstračními příklady
Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/go-root (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně stovku kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady, které naleznete v následující tabulce:
# | Příklad/soubor | Stručný popis | Cesta |
---|---|---|---|
1 | arraylist01.go | konstrukce seznamu s přidáním prvků pro seznam typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist01.go |
2 | arraylist02.go | přidání nových prvků do seznamu metodou Add pro seznam typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist02.go |
3 | arraylist03.go | pokus o přidání prvků odlišného datového typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist03.go |
4 | arraylist04.go | pokus o přidání prvků odlišného datového typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist04.go |
5 | arraylist05.go | vymazání všech prvků ze seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist05.go |
6 | arraylist06.go | test na existenci prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist06.go |
7 | arraylist07.go | přečtení prvků se zadaným indexem ze seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist07.go |
8 | arraylist08.go | odstranění prvků se zadaným indexem ze seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist08.go |
9 | arraylist09.go | operace Swap – prohození dvou prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist09.go |
10 | arraylist10.go | operace Sort – setřídění prvků v seznamu typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist10.go |
11 | arraylist11.go | implementace iterátoru nad seznamem typu arraylist | https://github.com/tisnik/go-root/blob/master/article92/arraylist11.go |
12 | singlylinkedlist01.go | konstrukce seznamu s přidáním prvků pro seznam typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist01.go |
13 | singlylinkedlist02.go | přidání nových prvků do seznamu metodou Add pro seznam typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist02.go |
14 | singlylinkedlist03.go | pokus o přidání prvků odlišného datového typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist03.go |
15 | singlylinkedlist04.go | pokus o přidání prvků odlišného datového typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist04.go |
16 | singlylinkedlist05.go | vymazání všech prvků ze seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist05.go |
17 | singlylinkedlist06.go | test na existenci prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist06.go |
18 | singlylinkedlist07.go | přečtení prvků se zadaným indexem ze seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist07.go |
19 | singlylinkedlist08.go | odstranění prvků se zadaným indexem ze seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist08.go |
20 | singlylinkedlist09.go | operace Swap – prohození dvou prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist09.go |
21 | singlylinkedlist10.go | operace Sort – setřídění prvků v seznamu typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist10.go |
22 | singlylinkedlist11.go | implementace iterátoru nad seznamem typu singlylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/singlylinkedlist11.go |
23 | doublylinkedlist01.go | konstrukce seznamu s přidáním prvků pro seznam typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist01.go |
24 | doublylinkedlist02.go | přidání nových prvků do seznamu metodou Add pro seznam typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist02.go |
25 | doublylinkedlist03.go | pokus o přidání prvků odlišného datového typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist03.go |
26 | doublylinkedlist04.go | pokus o přidání prvků odlišného datového typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist04.go |
27 | doublylinkedlist05.go | vymazání všech prvků ze seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist05.go |
28 | doublylinkedlist06.go | test na existenci prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist06.go |
29 | doublylinkedlist07.go | přečtení prvků se zadaným indexem ze seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist07.go |
30 | doublylinkedlist08.go | odstranění prvků se zadaným indexem ze seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist08.go |
31 | doublylinkedlist09.go | operace Swap – prohození dvou prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist09.go |
32 | doublylinkedlist10.go | operace Sort – setřídění prvků v seznamu typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist10.go |
33 | doublylinkedlist11.go | implementace iterátoru nad seznamem typu doublylinkedlist | https://github.com/tisnik/go-root/blob/master/article92/doublylinkedlist11.go |
34 | arraystack01.go | operace Push nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack01.go |
35 | arraystack02.go | operace Pop nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack02.go |
36 | arraystack03.go | operace Peek nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack03.go |
37 | arraystack04.go | metody Size a Empty nad zásobníkem typu arraystack | https://github.com/tisnik/go-root/blob/master/article92/arraystack04.go |
38 | linkedliststack01.go | operace Push nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack01.go |
39 | linkedliststack02.go | operace Pop nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack02.go |
40 | linkedliststack03.go | operace Peek nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack03.go |
41 | linkedliststack04.go | metody Size a Empty nad zásobníkem typu linkedliststack | https://github.com/tisnik/go-root/blob/master/article92/linkedliststack04.go |
42 | stack_rpn.go | vyhodnocení výrazu zapsaného v RPN | https://github.com/tisnik/go-root/blob/master/article92/stack_rpn.go |
43 | stack_rpn_B.go | vyhodnocení výrazu zapsaného v RPN, použití odlišné implementace zásobníku | https://github.com/tisnik/go-root/blob/master/article92/stack_rpn_B.go |
44 | rpn.go | vyhodnocení aritmetického výrazu | https://github.com/tisnik/go-root/blob/master/article92/rpn.go |
45 | erasthotenes.go | implementace Eratosthenova síta | https://github.com/tisnik/go-root/blob/master/article92/erasthotenes.go |
46 | avl-tree01.go | přidání prvků do stromu, výpis struktury stromu (AVL-stromy) | https://github.com/tisnik/go-root/blob/master/article93/avl-tree01.go |
47 | avl-tree02.go | iterace přes všechny prvky stromu (AVL-stromy) | https://github.com/tisnik/go-root/blob/master/article93/avl-tree02.go |
48 | avl-tree03.go | přečtení všech prvků uložených ve stromu (AVL-stromy) | https://github.com/tisnik/go-root/blob/master/article93/avl-tree03.go |
49 | avl-tree04.go | získání obsahů prvků (AVL-stromy) | https://github.com/tisnik/go-root/blob/master/article93/avl-tree04.go |
50 | rb-tree01.go | přidání prvků do stromu, výpis struktury stromu (RB-stromy) | https://github.com/tisnik/go-root/blob/master/article93/rb-tree01.go |
51 | rb-tree02.go | iterace přes všechny prvky stromu (RB-stromy) | https://github.com/tisnik/go-root/blob/master/article93/rb-tree02.go |
52 | rb-tree03.go | přečtení všech prvků uložených ve stromu (RB-stromy) | https://github.com/tisnik/go-root/blob/master/article93/rb-tree03.go |
53 | rb-tree04.go | získání obsahů prvků (RB-stromy) | https://github.com/tisnik/go-root/blob/master/article93/rb-tree04.go |
54 | btree01.go | konstrukce B-stromu řádu 3 | https://github.com/tisnik/go-root/blob/master/article93/btree01.go |
55 | btree02.go | konstrukce B-stromu řádu 4 | https://github.com/tisnik/go-root/blob/master/article93/btree02.go |
56 | btree03.go | konstrukce B-stromu řádu 20 | https://github.com/tisnik/go-root/blob/master/article93/btree03.go |
57 | btree04.go | iterace přes všechny prvky stromu (B-stromy) | https://github.com/tisnik/go-root/blob/master/article93/btree04.go |
58 | btree05.go | přečtení všech prvků uložených ve stromu (B-stromy) | https://github.com/tisnik/go-root/blob/master/article93/btree05.go |
59 | btree06.go | získání obsahů prvků (B-stromy) | https://github.com/tisnik/go-root/blob/master/article93/btree06.go |
60 | binary_heap01.go | konstrukce binární haldy | https://github.com/tisnik/go-root/blob/master/article93/binary_heap01.go |
61 | binary_heap02.go | přidání prvků do binární haldy | https://github.com/tisnik/go-root/blob/master/article93/binary_heap02.go |
62 | binary_heap03.go | iterace přes všechny prvky binární haldy | https://github.com/tisnik/go-root/blob/master/article93/binary_heap03.go |
63 | lists_test.go | benchmark – operace se seznamy | https://github.com/tisnik/go-root/blob/master/article93/lists_test.go |
64 | tree_test.go | benchmark – operace se stromy | https://github.com/tisnik/go-root/blob/master/article93/tree_test.go |
65 | hashmap01.go | konstrukce hešovací mapy, metoda Put | https://github.com/tisnik/go-root/blob/master/article94/hashmap01.go |
66 | hashmap02.go | konstrukce hešovací mapy, metoda Get | https://github.com/tisnik/go-root/blob/master/article94/hashmap02.go |
67 | hashmap03.go | metody Empty, Size, Keys a Values | https://github.com/tisnik/go-root/blob/master/article94/hashmap03.go |
68 | treemap01.go | konstrukce mapy založené na stromu, metoda Put | https://github.com/tisnik/go-root/blob/master/article94/treemap01.go |
69 | treemap02.go | konstrukce mapy založené na stromu, metoda Get | https://github.com/tisnik/go-root/blob/master/article94/treemap02.go |
70 | treemap03.go | metody Empty, Size, Keys a Values | https://github.com/tisnik/go-root/blob/master/article94/treemap03.go |
71 | treemap04.go | iterace přes všechny dvojice klíč-hodnota | https://github.com/tisnik/go-root/blob/master/article94/treemap04.go |
72 | linkedhashmap01.go | konstrukce hešovací mapy s lineárními seznamy pro prvky se stejným hešem | https://github.com/tisnik/go-root/blob/master/article94/linkedhashmap01.go |
73 | linkedhashmap02.go | konstrukce hešovací mapy s lineárními seznamy pro prvky se stejným hešem | https://github.com/tisnik/go-root/blob/master/article94/linkedhashmap02.go |
74 | linkedhashmap03.go | metody Empty, Size, Keys a Values | https://github.com/tisnik/go-root/blob/master/article94/linkedhashmap03.go |
75 | linkedhashmap04.go | iterace přes všechny dvojice klíč-hodnota | https://github.com/tisnik/go-root/blob/master/article94/linkedhashmap04.go |
76 | hashbidimap01.go | hešovací „obousměrná“ mapa – konstrukce a přidání prvků | https://github.com/tisnik/go-root/blob/master/article94/hashbidimap01.go |
77 | hashbidimap02.go | hešovací „obousměrná“ mapa – přečtení hodnoty či naopak klíče | https://github.com/tisnik/go-root/blob/master/article94/hashbidimap02.go |
78 | hashbidimap03.go | hešovací „obousměrná“ mapa – metody Empty, Size, Keys a Values | https://github.com/tisnik/go-root/blob/master/article94/hashbidimap03.go |
79 | hashbidimap04.go | hešovací „obousměrná“ mapa – mapování mezi celými čísly | https://github.com/tisnik/go-root/blob/master/article94/hashbidimap04.go |
80 | treebidimap01.go | „obousměrná“ mapa založená na stromu – konstrukce a přidání prvků | https://github.com/tisnik/go-root/blob/master/article94/treebidimap01.go |
81 | treebidimap02.go | „obousměrná“ mapa založená na stromu – přečtení hodnoty či naopak klíče | https://github.com/tisnik/go-root/blob/master/article94/treebidimap02.go |
82 | treebidimap03.go | „obousměrná“ mapa založená na stromu – metody Empty, Size, Keys a Values | https://github.com/tisnik/go-root/blob/master/article94/treebidimap03.go |
83 | treebidimap04.go | „obousměrná“ mapa založená na stromu – mapování mezi celými čísly | https://github.com/tisnik/go-root/blob/master/article94/treebidimap04.go |
84 | hashmap01error.go | kontrola datových typů u operace Put | https://github.com/tisnik/go-root/blob/master/article94/hashmap01error.go |
85 | hashmap02error.go | kontrola datových typů u operace Get | https://github.com/tisnik/go-root/blob/master/article94/hashmap02error.go |
86 | maps_test.go | benchmark – základní operace s mapami | https://github.com/tisnik/go-root/blob/master/article94/benchmarks/maps_test.go |
20. Odkazy na Internetu
- Genfuncs – implements various functions utilizing Go's Generics to help avoid writing boilerplate code
https://github.com/nwillc/genfuncs - Go18DS (Go 1.18+ Data Structures)
https://github.com/daichi-m/go18ds - TreeMap v2
https://github.com/igrmk/treemap - Fp-go is a collection of Functional Programming helpers powered by Golang 1.18+ generics
https://github.com/repeale/fp-go - The Go Programming Language Specification
https://go.dev/ref/spec - Generics in Go
https://bitfieldconsulting.com/golang/generics - Tutorial: Getting started with generics
https://go.dev/doc/tutorial/generics - Type parameters in Go
https://bitfieldconsulting.com/golang/type-parameters - Go Data Structures: Binary Search Tree
https://flaviocopes.com/golang-data-structure-binary-search-tree/ - Gobs of data
https://blog.golang.org/gobs-of-data - How the Go runtime implements maps efficiently (without generics)
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics - Go 1.18 Release Notes
https://golang.org/doc/go1.18 - Go 1.17 Release Notes
https://golang.org/doc/go1.17 - Go 1.16 Release Notes
https://golang.org/doc/go1.16 - Go 1.15 Release Notes
https://golang.org/doc/go1.15 - Go 1.14 Release Notes
https://golang.org/doc/go1.14 - Go 1.13 Release Notes
https://golang.org/doc/go1.13 - Go 1.12 Release Notes
https://golang.org/doc/go1.12 - Go 1.11 Release Notes
https://golang.org/doc/go1.11 - Go 1.11 Release Notes
https://golang.org/doc/go1.11 - Go 1.10 Release Notes
https://golang.org/doc/go1.10 - Go 1.9 Release Notes
https://golang.org/doc/go1.9 - Go 1.8 Release Notes
https://golang.org/doc/go1.8 - A Proposal for Adding Generics to Go
https://go.dev/blog/generics-proposal - Proposal: Go should have generics
https://github.com/golang/proposal/blob/master/design/15292-generics.md - Know Go: Generics (Kniha)
https://bitfieldconsulting.com/books/generics - Go 1.18 Generics based slice package
https://golangexample.com/go-1–18-generics-based-slice-package/ - The missing slice package
https://github.com/ssoroka/slice - Dlouho očekávaná novinka v Go 1.18 – generické datové typy
https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–18-genericke-datove-typy/ - Dlouho očekávaná novinka v Go 1.18 – generické datové typy (dokončení)
https://www.root.cz/clanky/dlouho-ocekavana-novinka-v-go-1–8-genericke-datove-typy-dokonceni/ - Generické datové typy v jazyce Go?
https://www.root.cz/clanky/genericke-datove-typy-v-jazyce-go/ - GoDS (Go Data Structures)
https://github.com/emirpasic/gods - Binární halda
https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_halda - Binární strom
https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_strom - AVL-strom
https://cs.wikipedia.org/wiki/AVL-strom - Červeno-černý strom
https://cs.wikipedia.org/wiki/%C4%8Cerveno-%C4%8Dern%C3%BD_strom - B-strom
https://cs.wikipedia.org/wiki/B-strom