youbbs
youbbs
3060 0 0

go set 数据优化

go 可以用map 来实现set 数据结构,但如果集合很大,为追求性能,map 就不合适,使用bitset 可以达到优化,如果集合上亿,可以考虑使用roaring 来压缩bitset

性能比较参考:

goos: darwin
goarch: amd64
BenchmarkMap-8       	100000000	        20.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkBitset-8    	1000000000	         2.71 ns/op	       0 B/op	       0 allocs/op
BenchmarkRoaring-8   	 5000000	       299 ns/op	     184 B/op	       6 allocs/op

相关项目:

bitset demo:

package main

import (
	"fmt"
	"github.com/willf/bitset"
	"math/rand"
)

func main() {
	fmt.Printf("Hello from BitSet!\n")
	var b bitset.BitSet
	// play some Go Fish
	for i := 0; i < 100; i++ {
		card1 := uint(rand.Intn(52))
		card2 := uint(rand.Intn(52))
		b.Set(card1)
		if b.Test(card2) {
			fmt.Println("Go Fish!")
		}
		b.Clear(card1)
	}

	// Chaining
	b.Set(10).Set(11)

	for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
		fmt.Println("The following bit is set:", i)
	}
	if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
		fmt.Println("Intersection works.")
	} else {
		fmt.Println("Intersection doesn't work???")
	}
}

0

See Also

Nearby


Discussion

Login Topics