Skip to content

Instantly share code, notes, and snippets.

@WincerChan
Last active June 7, 2020 05:17
Show Gist options
  • Save WincerChan/7fde282d164c34eb5346c817c6fe8c1f to your computer and use it in GitHub Desktop.
Save WincerChan/7fde282d164c34eb5346c817c6fe8c1f to your computer and use it in GitHub Desktop.
某些时候,字典树比哈希表更快吗?| Sometimes, is trie faster than hashmap?
package main
const R = 26
type TrieNode struct {
value int
next []TrieNode
}
type TrieST struct {
root TrieNode
}
func (t *TrieST) Put(key string, value int) {
node := &t.root
for _, v := range key {
if node.next == nil {
node.next = make([]TrieNode, R)
}
node = &node.next[v-97]
}
node.value = value
}
func (t *TrieST) Get(key string) int {
node := t.root
for _, v := range key {
if node.next == nil {
break
}
node = node.next[v-97]
}
return node.value
}
package main
import (
"encoding/json"
"fmt"
"io/ioutil"
"testing"
"time"
)
var st *TrieST
var hm map[string]int
var start time.Time
var perm []string
func read() {
by, err := ioutil.ReadFile("./permutation.json")
if err != nil {
panic(err)
}
json.Unmarshal(by, &perm)
}
func TestTrieST_Put(t *testing.T) {
read()
st = new(TrieST)
start = time.Now()
for i, v := range perm {
st.Put(v, i+1)
}
fmt.Printf("TrieST insert %d times elapsed %v\n", len(perm), time.Since(start))
hm = make(map[string]int)
start = time.Now()
for i, v := range perm {
hm[v] = i + 1
}
fmt.Printf("HashMap insert %d times elapsed %v\n", len(perm), time.Since(start))
}
func TestTrieST_Get(t *testing.T) {
start = time.Now()
for _, v := range perm {
_ = st.Get(v)
}
fmt.Printf("TrieST hit retrival %d times elapsed %v\n", len(perm), time.Since(start))
start = time.Now()
for _, v := range perm {
_, _ = hm[v]
}
fmt.Printf("HashMap hit retrival %d times elapsed %v\n", len(perm), time.Since(start))
}
@WincerChan
Copy link
Author

permutation.json 是一个包含了 5 个字母的 1395360 种排列。
permutation.json is a json file that contains length of 1395360 permutations of 5 letters.

运行结果|Run results:
TrieST insert 1395360 times elapsed 43.278137ms
HashMap insert 1395360 times elapsed 234.236339ms
TrieST hit retrival 1395360 times elapsed 13.920475ms
HashMap hit retrival 1395360 times elapsed 77.461994ms

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment