Go: rychlost přístupu k položce v map

V podstatě asi každý modernější jazyk nabízí nějakou možnost práce s hash tabulkami. Má ji Python, JavaScript, TypeScript a má ji i Golang.

Příklad využití takové datové struktůry se nabízí: máte klíčů, pod kterým z hash tabulky získáváte nějakou datovou strukturu, kterou může být cokoliv.

Performance otázkou pak zůstává, jak rychlý je přístup skrze klíče do hash tabulky je.

Napsal jsem si jednoduchý test, který pro jednoduchost vytovří hash table s 20.000.000 položkami, kde klíčem je 10 znakový string, pod kterým je ten stejný 10 znakový string. Měřil jsem pak rychlost přístupu k random klíči ve slovníku.

Prvním nápadem optimalizace rychlosti přístupu pak bylo setřízení hash tabulky podle klíče. Nad setřízeným hash tablem jsem pak opětovně měřil rychlost přístupu ke stejnému klíči.

package main

import (
	"fmt"
	"log"
	"math/rand"
	"sort"
	"time"
)

var i = 20000000
var randomIndex string

func init() {
	rand.Seed(time.Now().UnixNano())
}

func timer(name string) func() {
	st := time.Now()
	log.Println(name, "START")
	return func() {
		et := time.Now().Sub(st)
		log.Println(name, "DURATION", et)
	}
}

func randString(n int) string {
	var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
	b := make([]rune, n)
	for i := range b {
		b[i] = letters[rand.Intn(len(letters))]
	}
	return string(b)
}

func createMap(i int) map[string]string {
	t := timer("createMap")
	defer t()

	m := make(map[string]string)

	index := rand.Intn(i)

	for ; i > 0; i-- {
		rs := randString(10)
		m[rs] = rs

		if i == index {
			randomIndex = rs
		}
	}
	return m
}

func sortMap(m map[string]string) map[string]string {
	t := timer("sorteMap")
	defer t()

	keys := []string{}
	for k := range m {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	sm := make(map[string]string)
	for _, k := range keys {
		sm[k] = m[k]
	}
	return sm
}

func getItem(m map[string]string, k string) string {
	t := timer("getItem")
	defer t()

	return m[k]
}

func main() {
	fmt.Println("LEN OF MAPS:", i)
	m := createMap(i)
	sm := sortMap(m)

	v := getItem(m, randomIndex)
	fmt.Println(v)

	v = getItem(sm, randomIndex)
	fmt.Println(v)

}

A tady je výsledek:

Resume

Bez ohledu na délku doby setřízení hash table podle klíče, jsem byl překvapen jak velký rozdíl byl v době přístupu ke stejnému klíči nad původní a setřízenou datovou struktůrou.

Vím, že furt jsem ve stejném řádu, nicméně pokud rozdíl tu je.