Sunday, March 19, 2017

Golang: Traverse a Map in Sorted Keys

Using mapk from github.com/noypi/mapk.

mapk gives you sorted keys everytime you use Each(...) or EachFrom(prefix, ...).

mapk is using slice:
type _kv struct {
    k, v interface{}
}
type _kvslist []*_kv

type _SliceMap struct {
    kvs _kvslist
    cmp func(k1, k2 interface{}) int
}

taking advantage of the "sort" package's powerful tools, like the Search() function:
func (this _SliceMap) find(k interface{}) int {
    return sort.Search(len(this.kvs), func(i int) bool {
        return 0 <= this.cmp(this.kvs[i].k, k)
    })
}

since Search() needs the container to be sorted, we sort the slice every time we add an element:
func (this *_SliceMap) Put(k, v interface{}) {
 if 0 == len(this.kvs) {
  this.kvs = append(this.kvs, &_kv{k: k, v: v})
  return
 }

 i := this.find(k)
 if i >= len(this.kvs) {
  this.kvs = append(this.kvs, &_kv{k: k, v: v})
  return
 }

 if 0 == this.cmp(this.kvs[i].k, k) {
  this.kvs[i].v = v
  return
 }

 this.kvs = append(this.kvs[:i], append(_kvslist{&_kv{k: k, v: v}}, this.kvs[i:]...)...)

}

here's a benchmark, comparing the native use of "map" and "gtreap":

BenchmarkPutTen_GTreap-8                     1000000       1932 ns/op      640 B/op       30 allocs/op
BenchmarkGetTen_GTreap-8                     1000000       1681 ns/op      480 B/op       20 allocs/op
BenchmarkEachFrom7of10_GTreap-8              5000000        291 ns/op       48 B/op        2 allocs/op
BenchmarkEachTen_GTreap-8                    5000000        354 ns/op       64 B/op        2 allocs/op
BenchmarkDeleteAdd5of10_GTreap-8              200000       5250 ns/op     3215 B/op       86 allocs/op
BenchmarkPutTen_Slice-8                      1000000       1768 ns/op      320 B/op       20 allocs/op
BenchmarkGetTen_Slice-8                      1000000       1167 ns/op      160 B/op       10 allocs/op
BenchmarkEachFrom7of10_Slice-8              10000000        134 ns/op       16 B/op        1 allocs/op
BenchmarkEachTen_Slice-8                    50000000         35.0 ns/op        0 B/op        0 allocs/op
BenchmarkDeleteAdd5of10_Slice-8              1000000       2012 ns/op      624 B/op       25 allocs/op
BenchmarkPutTen_Native-8                     5000000        361 ns/op        0 B/op        0 allocs/op
BenchmarkGetTen_Native-8                    10000000        187 ns/op        0 B/op        0 allocs/op
BenchmarkDeleteAdd5of10_Native-8             3000000        383 ns/op        0 B/op        0 allocs/op
BenchmarkEachFrom_Native_NOT_SUPPORTED-8    2000000000          0.00 ns/op        0 B/op        0 allocs/op
BenchmarkEachTen_Native-8                   10000000        153 ns/op        0 B/op        0 allocs/op

Thanks.