Go 中 Set 的實現(xiàn)方案，你會嗎？
它摒棄了其他語言一些臃腫的功能和模塊，以降低程序員的學習門檻，減少使用中的心智負擔。
本文，我們來探討 Go 中缺失的數(shù)據(jù)結構：Set，以及它的最佳實現(xiàn)方案。
Set 語義與實現(xiàn)方案
Set 集合是其他語言中常見的數(shù)據(jù)結構。特性：集合中的對象不按特定的方式排序，并且沒有重復對象。
學習 Go ，要記住：Go 沒有包含的東西，不代表 Go 真的沒有。根據(jù) Set 特性，我們可以很輕松地想到使用 map 的實現(xiàn)方案(因為 map 的 key 是不重復的)：把對象當做 key 存入 map。
使用 map 來實現(xiàn) Set，意味著我們只關心 key 的存在，其 value 值并不重要。有其他語言編程經(jīng)驗的人也許會選擇 bool 來作為 value，因為它是其它語言中內(nèi)存消耗最少的類型(1個字節(jié))。但是在 Go 中，還有另一種選擇：struct{}。
- fmt.Println(unsafe.Sizeof(struct {}{})) // output: 0
壓測對比
為了探究哪種數(shù)據(jù)結構是作為 value 的最佳選擇。我們選擇了以下常用的類型作為 value 進行測試：bool、int、interface{}、struct{}。
- package main
- import (
- "testing"
- )
- const num = int(1 << 24)
- // 測試 bool 類型
- func Benchmark_SetWithBoolValueWrite(b *testing.B) {
- set := make(map[int]bool)
- for i := 0; i < num; i++ {
- set[i] = true
- }
- }
- // 測試 interface{} 類型
- func Benchmark_SetWithInterfaceValueWrite(b *testing.B) {
- set := make(map[int]interface{})
- for i := 0; i < num; i++ {
- set[i] = struct{}{}
- }
- }
- // 測試 int 類型
- func Benchmark_SetWithIntValueWrite(b *testing.B) {
- set := make(map[int]int)
- for i := 0; i < num; i++ {
- set[i] = 0
- }
- }
- // 測試 struct{} 類型
- func Benchmark_SetWithStructValueWrite(b *testing.B) {
- set := make(map[int]struct{})
- for i := 0; i < num; i++ {
- set[i] = struct{}{}
- }
- }
我們運行以下命令，進行測試
- $ go test -v -bench=. -count=3 -benchmem | tee result.txt
- goos: darwin
- goarch: amd64
- pkg: workspace/example/demoForSet
- cpu: Intel(R) Core(TM) i5-8279U CPU @ 2.40GHz
- Benchmark_SetWithBoolValueWrite
- Benchmark_SetWithBoolValueWrite-8 1 3549312568 ns/op 883610264 B/op 614311 allocs/op
- Benchmark_SetWithBoolValueWrite-8 1 3288521519 ns/op 883599440 B/op 614206 allocs/op
- Benchmark_SetWithBoolValueWrite-8 1 3264097496 ns/op 883578624 B/op 614003 allocs/op
- Benchmark_SetWithInterfaceValueWrite
- Benchmark_SetWithInterfaceValueWrite-8 1 4397757645 ns/op 1981619632 B/op 614062 allocs/op
- Benchmark_SetWithInterfaceValueWrite-8 1 4088301215 ns/op 1981553392 B/op 613743 allocs/op
- Benchmark_SetWithInterfaceValueWrite-8 1 3990698218 ns/op 1981560880 B/op 613773 allocs/op
- Benchmark_SetWithIntValueWrite
- Benchmark_SetWithIntValueWrite-8 1 3472910194 ns/op 1412326480 B/op 615131 allocs/op
- Benchmark_SetWithIntValueWrite-8 1 3519755137 ns/op 1412187928 B/op 614294 allocs/op
- Benchmark_SetWithIntValueWrite-8 1 3459182691 ns/op 1412057672 B/op 613390 allocs/op
- Benchmark_SetWithStructValueWrite
- Benchmark_SetWithStructValueWrite-8 1 3126746088 ns/op 802452368 B/op 614127 allocs/op
- Benchmark_SetWithStructValueWrite-8 1 3161650835 ns/op 802431240 B/op 613632 allocs/op
- Benchmark_SetWithStructValueWrite-8 1 3160410871 ns/op 802440552 B/op 613748 allocs/op
- PASS
- ok workspace/example/demoForSet 42.660s
此時的結果看起來不太直觀，這里推薦一個 benchmark 統(tǒng)計工具：Benchstat。通過以下命令進行安裝
- $ go get -u golang.org/x/perf/cmd/benchstat
使用 benchstat 分析剛才得到的 benchmark 結果文件
- $ benchstat result.txt
- name time/op
- _SetWithBoolValueWrite-8 3.37s ± 5%
- _SetWithInterfaceValueWrite-8 4.16s ± 6%
- _SetWithIntValueWrite-8 3.48s ± 1%
- _SetWithStructValueWrite-8 3.15s ± 1%
- name alloc/op
- _SetWithBoolValueWrite-8 884MB ± 0%
- _SetWithInterfaceValueWrite-8 1.98GB ± 0%
- _SetWithIntValueWrite-8 1.41GB ± 0%
- _SetWithStructValueWrite-8 802MB ± 0%
- name allocs/op
- _SetWithBoolValueWrite-8 614k ± 0%
- _SetWithInterfaceValueWrite-8 614k ± 0%
- _SetWithIntValueWrite-8 614k ± 0%
- _SetWithStructValueWrite-8 614k ± 0%
從內(nèi)存開銷而言，struct{} 是最小的，反映在執(zhí)行時間上也是最少的。由于 bool 類型僅占一個字節(jié)，它相較于空結構而言，相差的并不多。但是，如果使用 interface{} 類型，那差距就很明顯了。
所以，毫無疑問，在 Set 的實現(xiàn)中， map 值類型應該選 struct{}。
總結
本文雖然討論的是 Set 的實現(xiàn)方案，但本質是涉及空結構體 struct{}{} 的 零內(nèi)存特性。
空結構體除了是實現(xiàn) Set 的 value 值最佳方案，它還可以應用于以下方面：
- 通知信號的 channel：當 channel 只用于通知 goroutine 的執(zhí)行事件，此時 channel 就不需要發(fā)送任何實質性的數(shù)據(jù)，選擇使用 chan struct{} 。
- 沒有狀態(tài)數(shù)據(jù)的結構體：當對象只擁有方法，而不包含任何的屬性字段時，選擇使用空結構體定義該對象。
