sparsesets

Documentation

Index

• Constants
• type SparseDense
  • func (s *SparseDense) Clear()
  • func (s *SparseDense) Copy(x *SparseDense)
  • func (s *SparseDense) Has(x int) bool
  • func (s *SparseDense) Insert(x int) bool
  • func (s *SparseDense) IsEmpty() bool
  • func (s *SparseDense) Len() int
  • func (s *SparseDense) Max() int
  • func (s *SparseDense) Min() int
  • func (s *SparseDense) Remove(x int) bool
  • func (s *SparseDense) String() string
  • func (s *SparseDense) TakeMin(p *int) bool
  • func (s *SparseDense) UnionWith(x *SparseDense) bool

Constants

const (
	//ExpansionFactor = 1.5                //how much do we expand if array length is not enough
	MaxInt = int(^uint(0) >> 1) //max value in sparse array
	MinInt = -MaxInt - 1
)

bz: implementation-specific setting

Types

type SparseDense

type SparseDense struct {
	// contains filtered or unexported fields
}

bz: this is a sparse set implementation according to https://www.geeksforgeeks.org/sparse-set/ in order to replace /containner/intsets/sparse.go (since it does deep copy, which limits the performance) for smooth replacement, this will have the same api as intset.Sparse, also will borrow the size of fields

TODO: (1) not sure about this performance, will test

(2) from Jeff: "im not expecting len(pts) > 1000, ... ", ... so let's set ptsLimit when using this?
(3) do we use ExpansionFactor or double linked-list like block in intset.Sparse?
   ExpansionFactor -> deep copy requires a lot of time ...
   double linked-list -> estimate the size of block/array
=> check console-grpc-dist.txt, console-ethereum-dist.txt (callback), console-kubernetes-dist.txt (callback):
did a statistic survey on the mains of these benchmarks:
1. 96% has <10 obj in a pts;
2. 92% has idx < 5000 as the min obj idx;
3. 90% has < 10 distance between max and min obj idx
similar trends in other benchmarks
so, use linked-list (not double), 1st block will have maxVal == 6000 -> this can cover the majority cases
if needs to expend, expend by 1000

func (*SparseDense) Clear

func (s *SparseDense) Clear()

func (*SparseDense) Copy

func (s *SparseDense) Copy(x *SparseDense)

Copy sets s to the value of x. s -> x

func (*SparseDense) Has

func (s *SparseDense) Has(x int) bool

Has reports whether x is an element of the set s.

func (*SparseDense) Insert

func (s *SparseDense) Insert(x int) bool

Insert adds x to the set s, and reports whether the set grew. bz: for most cases, s.root is enough

func (*SparseDense) IsEmpty

func (s *SparseDense) IsEmpty() bool

func (*SparseDense) Len

func (s *SparseDense) Len() int

func (*SparseDense) Max

func (s *SparseDense) Max() int

Max returns the maximum element of the set s, or MinInt if s is empty.

func (*SparseDense) Min

func (s *SparseDense) Min() int

Min returns the minimum element of the set s, or MaxInt if s is empty.

func (*SparseDense) Remove

func (s *SparseDense) Remove(x int) bool

Remove removes x from the set s, and reports whether the set shrank. bz: for most cases, s.root is enough

func (*SparseDense) String

func (s *SparseDense) String() string

func (*SparseDense) TakeMin

func (s *SparseDense) TakeMin(p *int) bool

bz: see @container/intsets/sparse.go:416

func (*SparseDense) UnionWith

func (s *SparseDense) UnionWith(x *SparseDense) bool

UnionWith sets s to the union s ∪ x, and reports whether s grew.