The

Golang docs say:

A set can be implemented as a map with value type bool. Set the map entry to true to put the value in the set, and then test it by simple indexing.

Here is such a set implementation:

package main
import (
"log"
"runtime"
)
func main() {
const SIZE = 10000000
set := make(map[int]bool, SIZE)
for i := 0; i < SIZE; i++ {
set[i] = true
}
memStats := runtime.MemStats{}
runtime.ReadMemStats(&memStats)
println("Used", memStats.Alloc, "bytes")
// test the set
for i := 0; i < SIZE; i++ {
_, ok := set[i]
if !ok {
log.Panic("The set does not contain the expected value!")
}
}
for i := SIZE; i < SIZE*2; i++ {
_, ok := set[i]
if ok {
log.Panic("The set contains an unexpected value!")
}
}
}

The memory usage is:

$ go run sets.go
Used 195924120 bytes

It turns out you can make the values to consuming 0 bytes of memory if they will not of type **bool**, but **struct{}**:
package main
import (
"log"
"runtime"
)
func main() {
const SIZE = 10000000
set := make(map[int]struct{}, SIZE)
for i := 0; i < SIZE; i++ {
set[i] = struct{}{}
}
memStats := runtime.MemStats{}
runtime.ReadMemStats(&memStats)
println("Used", memStats.Alloc, "bytes")
// test the set
for i := 0; i < SIZE; i++ {
_, ok := set[i]
if !ok {
log.Panic("The set does not contain the expected value!")
}
}
for i := SIZE; i < SIZE*2; i++ {
_, ok := set[i]
if ok {
log.Panic("The set contains an unexpected value!")
}
}
}

And you can see that the memory usage with a map of 10,000,000 integers dropped:

$ go run sets.go
Used 177338200 bytes

The difference is 18,585,920 bytes.

## No comments:

## Post a Comment