README
¶
IntSet
A specialized set for integers or runes, ideal when:
- The number of elements is known ahead of time (or a good approximation)
- The number of elements doesn't change drastically over time
- The values are naturally random
As long as the number of elements within the set stays close to the originally specified size (I don't know the magic number, so let's say ±10%), and that they stay evenly distributed. the set will exhibit good read and write performance, as well as decent memory usage. When packed, read performance is roughly 7 times better than a map[int]struct{}.
set := intset.NewSized(1000000) // or intset.NewSized32(1000000) or intset.NewRune(1000000)
set.Set(32)
set.Exists(32)
Methods
The int, uint32 and rune variations have the same API.
Set(int)orSet(uint32)orSet(rune)Exists(int) boolorExists(uint32) boolorExists(rune) boolRemove(int) boolorRemove(uint32) boolorRemove(rune) boolLen() intEach(f func(value int))orEach(f func(value uint32))orEach(f func(value rune))
Intersections and Unions
Two or more sets can be intersected by calling Intersect, Intersect32, or IntersectRune. This is largely a reference implementation and callers should consider implementing their own. For example, maybe you want to stop after finding X matches, want to use a pooled array object to hold intermediary objects, or are fine with getting an array back (rather than a set) (all of which should result in much better performance).
The method is called via:
result := intset.Intersect([]Set{s1, s2})
// or
result := intset.Intersect32([]Set32{s1, s2})
// or
result := intset.IntersectRune([]Set32{s1, s2})
Union, Union32, and UnionRune can be similarly used.
Advanced Sizing
The NewSizedConfig, NewSized32Config and NewRuneConfig functions can be used to have more control over how the set behaves. These functions take the size, as normal, as well as a Config:
config1 := intset.NewConfig()
set1 := intset.NewSizedConfig(1000000, config1)
config1 := intset.NewConfig().BucketSize(16)
set2 := intset.NewSizedConfig(1000000, config2)
config3 := intset.NewConfig().BucketSize(16).BucketGrowBy(4)
set3 := intset.NewSizedConfig(1000000, config3)
See This Pull Request to see the performance/memory tradeoff of possible values. In short though, the default BucketSize=4 & BucketGrowBy=1, results in faster probing at the cost of higher memory use.
Documentation
¶
Overview ¶
Package intset provides a specialized set for integers or runes
Package intset provides a specialized set for integers or runes ¶
Package intset provides a specialized set for integers or runes ¶
Package intset provides a specialized set for integers or runes ¶
Package intset provides a specialized set for integers or runes
Index ¶
Constants ¶
This section is empty.
Variables ¶
var Default = NewConfig()
Default is a default Config which favors probing performance at the cost of memory.
Functions ¶
This section is empty.
Types ¶
type Config ¶
type Config struct {
// contains filtered or unexported fields
}
Config defines the configuration for creating a new set
Smaller values for bucketSize will speed up lookups but also increase memory usage. Smaller values for bucketGrowBy will slow down the set capacity growth rate but also slow down insertions.
func (*Config) BucketGrowBy ¶
BucketGrowBy sets the amount a bucket will grow by when full
func (*Config) BucketSize ¶
BucketSize sets the initial bucket size
type Rune ¶
type Rune struct {
// contains filtered or unexported fields
}
Rune stores rune set data
func IntersectRune ¶
IntersectRune returns the intersection of an array of sets
func NewRune ¶
NewRune creates an empty rune set with target capacity specified by size using default configuration
func NewRuneConfig ¶
NewRuneConfig creates an empty rune set with target capacity specified by size
type Sized ¶
type Sized struct {
// contains filtered or unexported fields
}
Sized stores int set data
func NewSized ¶
NewSized creates an empty int set with target capacity specified by size using default configuration
func NewSizedConfig ¶
NewSizedConfig creates an empty int set with target capacity specified by size
type Sized32 ¶
type Sized32 struct {
// contains filtered or unexported fields
}
Sized32 stores uint32 set data
func Intersect32 ¶
Intersect32 returns the intersection of an array of sets
func NewSized32 ¶
NewSized32 creates an empty int set with target capacity specified by size using default configuration
func NewSized32Config ¶
NewSized32Config creates an empty uint32 set with target capacity specified by size
Source Files