README
¶
structx
Data structures and algorithms implemented using generics.
Currently, structx provides the following types of data structures to support generic types:
ListMap、SyncMapLSet (ListSet)Skiplist、ZSet (SortedSet)PoolCacheBitMap
BitMap
bitmap implement backed by a slice of []uint64, and is nice wrappered.
usage
bm := structx.NewBitMap(1,2,3)
bm.Add(4) // [1,2,3,4]
bm.Add(1) // [1,2,3.4]
bm.Remove(4) // [1,2,3]
bm.Contains(2) // true
bm.Min() // 1
bm.Max() // 3
bm.Len() // 3
bm1 := structx.NewBitMap(3,4,5)
bm.Union(bm1, true) // [1,2,3,4,5] OR operation and set inplaced
Benchmark
Benchmarks below were run on a pre-allocated bitmap of 100,000,000 elements.
goos: linux
goarch: amd64
pkg: github.com/xgzlucario/structx/test
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkBmAdd-16 787935627 1.515 ns/op 0 B/op 0 allocs/op
BenchmarkBmContains-16 1000000000 0.3916 ns/op 0 B/op 0 allocs/op
BenchmarkBmRemove-16 1000000000 0.7613 ns/op 0 B/op 0 allocs/op
BenchmarkBmMax-16 1000000000 1.169 ns/op 0 B/op 0 allocs/op
BenchmarkBmMin-16 1000000000 0.8804 ns/op 0 B/op 0 allocs/op
BenchmarkBmUnion-16 2249113 512.9 ns/op 2080 B/op 2 allocs/op
BenchmarkBmUnionInplace-16 9901345 118.2 ns/op 0 B/op 0 allocs/op
BenchmarkBmIntersect-16 3246958 370.4 ns/op 1312 B/op 2 allocs/op
BenchmarkBmIntersectInplace-16 11000289 110.2 ns/op 0 B/op 0 allocs/op
BenchmarkBmDifference-16 2107741 606.5 ns/op 2080 B/op 2 allocs/op
BenchmarkBmDifferenceInplace-16 9769774 121.4 ns/op 0 B/op 0 allocs/op
BenchmarkBmMarshal-16 66 16559485 ns/op 39497262 B/op 7 allocs/op
PASS
ok github.com/xgzlucario/structx/test 32.252s
List
List is a data structure wrapping basic type slice. Compare to basic slice type, List is sequential, sortable, and nice wrappered.
usage
ls := structx.NewList(1,2,3)
ls.RPush(4) // [1,2,3,4]
ls.LPop() // 1 [2,3,4]
ls.Reverse() // [4,3,2]
ls.Index(1) // 3
ls.Find(4) // 0
ls.RShift() // [2,4,3]
ls.Top(1) // [4,2,3]
ls.Sort(func(i, j int) bool {
return i<j
}) // [2,3,4]
LSet
LSet uses Map + List as the storage structure. LSet is Inherited from List, where the elements are sequential and have good iterative performance, as well as richer api. When the data volume is small only list is used.
usage
s := structx.NewLSet(1,2,3,4,1) // [1,2,3,4]
s.Add(5) // [1,2,4,5]
s.Remove(3) // [1,2,4]
s.Reverse() // [5,4,2,1]
s.Top(2) // [2,5,4,1]
s.Rpop() // [5,4,1]
s.Range(func(k int) bool {...})
s1 := structx.NewLSet(1,2,3) // [1,2,3]
union := s.Union(s1) // [0,1,2,3]
intersect := s.Intersect(s1) // [1,2]
diff := s.Difference(s1) // [0,3]
Benchmark
Compare with mapset deckarep/golang-set.
goos: linux
goarch: amd64
pkg: github.com/xgzlucario/structx/test
cpu: AMD Ryzen 7 5800H with Radeon Graphics
Benchmark_MapSetRange-16 130693 8991 ns/op 0 B/op 0 allocs/op
Benchmark_LSetRange-16 821851 1415 ns/op 0 B/op 0 allocs/op
Benchmark_MapSetRemove-16 318151948 3.758 ns/op 0 B/op 0 allocs/op
Benchmark_LSetRemove-16 364006822 3.303 ns/op 0 B/op 0 allocs/op
Benchmark_MapSetAdd-16 21847 55064 ns/op 47871 B/op 68 allocs/op
Benchmark_LSetAdd-16 17355 68348 ns/op 73055 B/op 78 allocs/op
Benchmark_MapSetUnion-16 12676 94480 ns/op 47874 B/op 68 allocs/op
Benchmark_LSetUnion-16 31516 38181 ns/op 30181 B/op 10 allocs/op
Benchmark_MapSetIntersect-16 14566 82046 ns/op 47878 B/op 68 allocs/op
Benchmark_LSetIntersect-16 37855 31650 ns/op 30181 B/op 10 allocs/op
Benchmark_MapSetDiff-16 30876 38927 ns/op 8059 B/op 1002 allocs/op
Benchmark_LSetDiff-16 92643 12866 ns/op 153 B/op 4 allocs/op
Documentation
¶
Index ¶
- Constants
- Variables
- type BitMap
- func (bm *BitMap) Add(num uint32) bool
- func (bm *BitMap) AddRange(start uint32, end uint32) *BitMap
- func (bm *BitMap) Contains(num uint32) bool
- func (bm *BitMap) Copy() *BitMap
- func (bm *BitMap) Difference(t *BitMap, inplace ...bool) *BitMap
- func (bm *BitMap) Equal(t *BitMap) bool
- func (bm *BitMap) Intersect(target *BitMap, inplace ...bool) *BitMap
- func (bm *BitMap) Len() int
- func (bm *BitMap) MarshalJSON() ([]byte, error)
- func (bm *BitMap) Max() int
- func (bm *BitMap) Min() int
- func (bm *BitMap) Range(f func(uint32) bool)
- func (bm *BitMap) Remove(num uint32) bool
- func (bm *BitMap) RevRange(f func(uint32) bool)
- func (bm *BitMap) Union(t *BitMap, inplace ...bool) *BitMap
- func (bm *BitMap) UnmarshalJSON(src []byte) error
- type Bloom
- type Cache
- func (c *Cache[K, V]) Clear()
- func (c *Cache[K, V]) Get(key K) (v V, ok bool)
- func (c *Cache[K, V]) Keys() []K
- func (c *Cache[K, V]) Len() int
- func (c *Cache[K, V]) MSet(values map[K]V, ttl ...time.Duration)
- func (c *Cache[K, V]) MarshalJSON() ([]byte, error)
- func (c *Cache[K, V]) OnExpired(f cmap.RemoveCb[K, *cacheItem[V]]) *Cache[K, V]
- func (c *Cache[K, V]) Print()
- func (c *Cache[K, V]) Range(f func(key K, value V) bool)
- func (c *Cache[K, V]) RangeWithTTL(f func(key K, value V, ttl int64) bool)
- func (c *Cache[K, V]) Remove(key K)
- func (c *Cache[K, V]) Set(key K, value V, ttl ...time.Duration)
- func (c *Cache[K, V]) SetTTL(key K, ttl time.Duration) bool
- func (c *Cache[K, V]) UnmarshalJSON(src []byte) error
- type LSet
- func (s *LSet[T]) Add(key T) bool
- func (s LSet) Bottom(i int)
- func (s LSet) Capacity() int
- func (s *LSet[T]) Copy() *LSet[T]
- func (s *LSet[T]) Difference(t *LSet[T]) *LSet[T]
- func (s *LSet[T]) Equal(t *LSet[T]) bool
- func (s *LSet[T]) Exist(key T) bool
- func (s LSet) Find(elem T) int
- func (s LSet) Index(i int) T
- func (s *LSet[T]) Intersect(t *LSet[T]) *LSet[T]
- func (s *LSet[T]) IsSubSet(t *LSet[T]) bool
- func (s *LSet[T]) LPop() (key T, ok bool)
- func (s LSet) LShift()
- func (s LSet) Len() int
- func (s LSet) Print()
- func (s *LSet[T]) RPop() (key T, ok bool)
- func (s LSet) RShift()
- func (s *LSet[T]) RandomPop() (key T, ok bool)
- func (s LSet) Range(f func(T) bool)
- func (s *LSet[T]) Remove(key T) bool
- func (s LSet) Reverse()
- func (s LSet) Swap(i, j int)
- func (s LSet) Top(i int)
- func (s *LSet[T]) Union(t *LSet[T]) *LSet[T]
- func (s *LSet[T]) UnmarshalJSON(src []byte) error
- func (s LSet) Values() []T
- type List
- func (s List) Bottom(i int)
- func (s List) Capacity() int
- func (s *List[T]) Clip()
- func (s *List[T]) Compact()
- func (s List) Copy() array[T]
- func (ls *List[T]) Filter(f func(T) bool) *List[T]
- func (s List) Find(elem T) int
- func (s List) Index(i int) T
- func (ls *List[T]) Insert(i int, values ...T)
- func (ls *List[T]) IsSorted(f func(T, T) bool) bool
- func (ls *List[T]) LPop() (val T, ok bool)
- func (ls *List[T]) LPush(values ...T)
- func (s List) LShift()
- func (s List) Len() int
- func (s *List[T]) MarshalJSON() ([]byte, error)
- func (ls *List[T]) Max(less func(T, T) bool) T
- func (ls *List[T]) Mean(f func(T) float64) float64
- func (ls *List[T]) Min(less func(T, T) bool) T
- func (s List) Print()
- func (ls *List[T]) RPop() (val T, ok bool)
- func (ls *List[T]) RPush(values ...T)
- func (s List) RShift()
- func (s List) Range(f func(T) bool)
- func (ls *List[T]) RemoveFirst(elem T) bool
- func (ls *List[T]) RemoveIndex(i int) bool
- func (s List) Reverse()
- func (ls *List[T]) Sort(f func(T, T) bool) *List[T]
- func (ls *List[T]) Sum(f func(T) float64) float64
- func (s List) Swap(i, j int)
- func (s List) Top(i int)
- func (s *List[T]) UnmarshalJSON(src []byte) error
- func (s List) Values() []T
- type Map
- func (m Map[K, V]) Clear()
- func (m Map[K, V]) Copy() Map[K, V]
- func (m Map[K, V]) Delete(key K) error
- func (m Map[K, V]) Exist(key K) bool
- func (m Map[K, V]) Get(key K) (V, bool)
- func (m Map[K, V]) Keys() []K
- func (m Map[K, V]) Len() int
- func (m Map[K, V]) MarshalJSON() ([]byte, error)
- func (m Map[K, V]) Range(f func(K, V) bool)
- func (m Map[K, V]) Set(key K, value V)
- func (m Map[K, V]) UnmarshalJSON(src []byte) error
- func (m Map[K, V]) Values() []V
- type Pool
- type Skiplist
- func (s *Skiplist[K, V]) Add(key K, value V) *skiplistNode[K, V]
- func (s *Skiplist[K, V]) Delete(key K, value V) bool
- func (s *Skiplist[K, V]) Find(value V) bool
- func (s *Skiplist[K, V]) GetByRank(rank int) (k K, v V, err error)
- func (s *Skiplist[K, V]) GetScoreWithRank(key K) (v V, rank int, err error)
- func (s *Skiplist[K, V]) Len() int
- func (s *Skiplist[K, V]) Print()
- func (s *Skiplist[K, V]) Range(start, end int, f func(K, V) bool)
- func (s *Skiplist[K, V]) RangeByScores(min, max V, f func(K, V) bool)
- type SyncMap
- type Trie
- type ZSet
- func (z *ZSet[K, V]) Copy() *ZSet[K, V]
- func (z *ZSet[K, V]) Delete(keys ...K) error
- func (z *ZSet[K, V]) GetByRank(rank int) (k K, v V, err error)
- func (z *ZSet[K, V]) GetScore(key K) (v V, err error)
- func (z *ZSet[K, V]) GetScoreWithRank(key K) (V, int, error)
- func (z *ZSet[K, V]) Incr(key K, value V) V
- func (z *ZSet[K, V]) Len() int
- func (z *ZSet[K, V]) Print()
- func (z *ZSet[K, V]) Range(start, end int, f func(K, V) bool)
- func (z *ZSet[K, V]) RangeByScores(min, max V, f func(K, V) bool)
- func (z *ZSet[K, V]) Set(key K, value V)
- func (z *ZSet[K, V]) Union(target *ZSet[K, V])
Constants ¶
View Source
const (
NoTTL int64 = math.MaxInt64
)
Variables ¶
View Source
var ( // duration of expired keys evictions GCDuration = time.Minute // duration of update current timestamp TickerDuration = time.Millisecond // default expiry time DefaultTTL = time.Minute * 10 )
Functions ¶
This section is empty.
Types ¶
type BitMap ¶ added in v0.2.6
type BitMap struct {
// contains filtered or unexported fields
}
func (*BitMap) Add ¶ added in v0.3.0
Add If you use numbers that increment from 0, the bitmap performance will be very good.
func (*BitMap) Difference ¶ added in v0.4.2
Difference
func (*BitMap) MarshalJSON ¶ added in v0.5.0
func (*BitMap) UnmarshalJSON ¶ added in v0.5.0
type Cache ¶ added in v0.1.7
func (*Cache[K, V]) MarshalJSON ¶ added in v0.5.0
func (*Cache[K, V]) RangeWithTTL ¶ added in v0.1.7
RangeWithTTL
func (*Cache[K, V]) UnmarshalJSON ¶ added in v0.5.0
type LSet ¶ added in v0.1.4
type LSet[T comparable] struct { *List[T] // contains filtered or unexported fields }
LSet (ListSet): map + list structure LSet has richer api and faster Intersect, Union, Range operations than mapset
func NewLSet ¶ added in v0.1.4
func NewLSet[T comparable](values ...T) *LSet[T]
NewLSet: Create a new LSet
func (*LSet[T]) Difference ¶ added in v0.1.5
Difference
func (LSet) LShift ¶ added in v0.2.1
func (s LSet) LShift()
LShift: Shift all elements of the array left exp: [1, 2, 3] => [2, 3, 1]
func (LSet) RShift ¶ added in v0.2.1
func (s LSet) RShift()
RShift: Shift all elements of the array right exp: [1, 2, 3] => [3, 1, 2]
func (*LSet[T]) UnmarshalJSON ¶ added in v0.2.2
type List ¶
type List[T comparable] struct { // contains filtered or unexported fields }
func (*List[T]) Clip ¶ added in v0.6.0
func (s *List[T]) Clip()
Clip removes unused capacity from the slice.
func (*List[T]) Compact ¶ added in v0.6.0
func (s *List[T]) Compact()
Compact replaces consecutive runs of equal elements with a single copy.
func (List) LShift ¶ added in v0.2.0
func (s List) LShift()
LShift: Shift all elements of the array left exp: [1, 2, 3] => [2, 3, 1]
func (*List[T]) MarshalJSON ¶ added in v0.2.1
func (List) RShift ¶ added in v0.2.0
func (s List) RShift()
RShift: Shift all elements of the array right exp: [1, 2, 3] => [3, 1, 2]
func (*List[T]) RemoveFirst ¶ added in v0.5.0
RemoveFirst
func (*List[T]) RemoveIndex ¶ added in v0.6.0
RemoveIndex
func (*List[T]) UnmarshalJSON ¶ added in v0.2.2
type Map ¶
type Map[K comparable, V any] map[K]V
func (Map[K, V]) MarshalJSON ¶ added in v0.6.0
func (Map[K, V]) UnmarshalJSON ¶ added in v0.6.0
type Skiplist ¶ added in v0.1.7
func (*Skiplist[K, V]) Add ¶ added in v0.1.7
func (s *Skiplist[K, V]) Add(key K, value V) *skiplistNode[K, V]
Add
func (*Skiplist[K, V]) GetScoreWithRank ¶ added in v0.1.7
GetScoreWithRank: Get the score and rank by key
func (*Skiplist[K, V]) RangeByScores ¶ added in v0.1.7
RangeByScores
type SyncMap ¶
type SyncMap[K comparable, V any] struct { cmap.ConcurrentMap[K, V] }
SynMap: use ConcurrentMap
func NewSyncMapStringer ¶ added in v0.4.0
NewSyncMapStringer
func (*SyncMap[K, V]) MarshalJSON ¶ added in v0.5.0
MarshalJSON
func (*SyncMap[K, V]) UnmarshalJSON ¶ added in v0.5.0
UnmarshalJSON
type Trie ¶ added in v0.3.0
func (*Trie[T]) MarshalJSON ¶ added in v0.6.1
func (*Trie[T]) UnmarshalJSON ¶ added in v0.6.1
type ZSet ¶ added in v0.1.3
func (*ZSet[K, V]) GetScoreWithRank ¶ added in v0.1.7
GetScoreWithRank
func (*ZSet[K, V]) Incr ¶ added in v0.1.7
func (z *ZSet[K, V]) Incr(key K, value V) V
Incr: Increment value by key
func (*ZSet[K, V]) RangeByScores ¶ added in v0.1.7
RangeByScores
Source Files
¶
Directories
Click to show internal directories.
Click to hide internal directories.