store

package
v1.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 6, 2022 License: Apache-2.0 Imports: 7 Imported by: 11

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	DefaultProvider                   = Provider(BufferedPaginatedStoreConstructor)
	DenseStoreConstructor             = Provider(func() Store { return NewDenseStore() })
	BufferedPaginatedStoreConstructor = Provider(func() Store { return NewBufferedPaginatedStore() })
	SparseStoreConstructor            = Provider(func() Store { return NewSparseStore() })
)

Functions

func DecodeAndMergeWith added in v1.1.0 

func DecodeAndMergeWith(s Store, b *[]byte, binEncodingMode enc.SubFlag) error

func MergeWithProto added in v1.1.0 

func MergeWithProto(store Store, pb *sketchpb.Store)

MergeWithProto merges the distribution in a protobuf Store to an existing store. - if called with an empty store, this simply populates the store with the distribution in the protobuf Store. - if called with a non-empty store, this has the same outcome as deserializing the protobuf Store, then merging.

Types

type Bin 

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

func NewBin 

func NewBin(index int, count float64) (*Bin, error)

func (Bin) Count 

func (b Bin) Count() float64

func (Bin) Index 

func (b Bin) Index() int

type BufferedPaginatedStore added in v1.1.0 

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

BufferedPaginatedStore allocates storage for counts in aligned fixed-size pages, themselves stored in a dynamically-sized slice. A page encodes the counts for a contiguous range of indexes, and two pages that are contiguous in the slice encode ranges that are contiguous. In addition, input indexes that are added to the store with a count equal to 1 can be stored in a buffer. The store favors using the buffer and only creates pages when the memory size of the page is no greater than the memory space that is needed to keep in the buffer the indexes that could otherwise be encoded in that page. That means that some indexes may stay indefinitely in the buffer if, to be removed from the buffer, they would create a page that is almost empty. The process that transfers indexes from the buffer to pages is called compaction. This store never collapses or merges bins, therefore, it does not introduce any error in itself. In particular, MinIndex(), MaxIndex(), Bins() and KeyAtRank() return exact results. There is no upper bound on the memory size that this store needs to encode input indexes, and some input data distributions may make it reach large sizes. However, thanks to the buffer and the fact that only required pages are allocated, it can be much more space efficient than alternative stores, especially dense stores, in various situations, including when only few indexes are added (with their counts equal to 1), when the input data has a few outliers or when the input data distribution is multimodal.

func NewBufferedPaginatedStore added in v1.1.0 

func NewBufferedPaginatedStore() *BufferedPaginatedStore

func (*BufferedPaginatedStore) Add added in v1.1.0 

func (s *BufferedPaginatedStore) Add(index int)

func (*BufferedPaginatedStore) AddBin added in v1.1.0 

func (s *BufferedPaginatedStore) AddBin(bin Bin)

func (*BufferedPaginatedStore) AddWithCount added in v1.1.0 

func (s *BufferedPaginatedStore) AddWithCount(index int, count float64)

func (*BufferedPaginatedStore) Bins added in v1.1.0 

func (s *BufferedPaginatedStore) Bins() <-chan Bin

func (*BufferedPaginatedStore) Clear added in v1.1.0 

func (s *BufferedPaginatedStore) Clear()

func (*BufferedPaginatedStore) Copy added in v1.1.0 

func (s *BufferedPaginatedStore) Copy() Store

func (*BufferedPaginatedStore) DecodeAndMergeWith added in v1.1.0 

func (s *BufferedPaginatedStore) DecodeAndMergeWith(b *[]byte, encodingMode enc.SubFlag) error

func (*BufferedPaginatedStore) Encode added in v1.1.0 

func (s *BufferedPaginatedStore) Encode(b *[]byte, t enc.FlagType)

func (*BufferedPaginatedStore) ForEach added in v1.1.0 

func (s *BufferedPaginatedStore) ForEach(f func(index int, count float64) (stop bool))

func (*BufferedPaginatedStore) IsEmpty added in v1.1.0 

func (s *BufferedPaginatedStore) IsEmpty() bool

func (*BufferedPaginatedStore) KeyAtRank added in v1.1.0 

func (s *BufferedPaginatedStore) KeyAtRank(rank float64) int

func (*BufferedPaginatedStore) MaxIndex added in v1.1.0 

func (s *BufferedPaginatedStore) MaxIndex() (int, error)

func (*BufferedPaginatedStore) MergeWith added in v1.1.0 

func (s *BufferedPaginatedStore) MergeWith(other Store)

func (*BufferedPaginatedStore) MergeWithProto added in v1.1.0 

func (s *BufferedPaginatedStore) MergeWithProto(pb *sketchpb.Store)

func (*BufferedPaginatedStore) MinIndex added in v1.1.0 

func (s *BufferedPaginatedStore) MinIndex() (int, error)

func (*BufferedPaginatedStore) Reweight added in v1.1.0 

func (s *BufferedPaginatedStore) Reweight(w float64) error

func (*BufferedPaginatedStore) ToProto added in v1.1.0 

func (s *BufferedPaginatedStore) ToProto() *sketchpb.Store

func (*BufferedPaginatedStore) TotalCount added in v1.1.0 

func (s *BufferedPaginatedStore) TotalCount() float64

type CollapsingHighestDenseStore 

type CollapsingHighestDenseStore struct {
	DenseStore
	// contains filtered or unexported fields
}

func NewCollapsingHighestDenseStore 

func NewCollapsingHighestDenseStore(maxNumBins int) *CollapsingHighestDenseStore

func (*CollapsingHighestDenseStore) Add 

func (s *CollapsingHighestDenseStore) Add(index int)

func (*CollapsingHighestDenseStore) AddBin 

func (s *CollapsingHighestDenseStore) AddBin(bin Bin)

func (*CollapsingHighestDenseStore) AddWithCount 

func (s *CollapsingHighestDenseStore) AddWithCount(index int, count float64)

func (*CollapsingHighestDenseStore) Clear added in v1.1.0 

func (s *CollapsingHighestDenseStore) Clear()

func (*CollapsingHighestDenseStore) Copy 

func (s *CollapsingHighestDenseStore) Copy() Store

func (*CollapsingHighestDenseStore) DecodeAndMergeWith added in v1.1.0 

func (s *CollapsingHighestDenseStore) DecodeAndMergeWith(r *[]byte, encodingMode enc.SubFlag) error

func (*CollapsingHighestDenseStore) MergeWith 

func (s *CollapsingHighestDenseStore) MergeWith(other Store)

type CollapsingLowestDenseStore 

type CollapsingLowestDenseStore struct {
	DenseStore
	// contains filtered or unexported fields
}

CollapsingLowestDenseStore is a dynamically growing contiguous (non-sparse) store. The lower bins get combined so that the total number of bins do not exceed maxNumBins.

func NewCollapsingLowestDenseStore 

func NewCollapsingLowestDenseStore(maxNumBins int) *CollapsingLowestDenseStore

func (*CollapsingLowestDenseStore) Add 

func (s *CollapsingLowestDenseStore) Add(index int)

func (*CollapsingLowestDenseStore) AddBin 

func (s *CollapsingLowestDenseStore) AddBin(bin Bin)

func (*CollapsingLowestDenseStore) AddWithCount 

func (s *CollapsingLowestDenseStore) AddWithCount(index int, count float64)

func (*CollapsingLowestDenseStore) Clear added in v1.1.0 

func (s *CollapsingLowestDenseStore) Clear()

func (*CollapsingLowestDenseStore) Copy 

func (s *CollapsingLowestDenseStore) Copy() Store

func (*CollapsingLowestDenseStore) DecodeAndMergeWith added in v1.1.0 

func (s *CollapsingLowestDenseStore) DecodeAndMergeWith(r *[]byte, encodingMode enc.SubFlag) error

func (*CollapsingLowestDenseStore) MergeWith 

func (s *CollapsingLowestDenseStore) MergeWith(other Store)

type DenseStore 

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

DenseStore is a dynamically growing contiguous (non-sparse) store. The number of bins are bound only by the size of the slice that can be allocated.

func FromProto 

func FromProto(pb *sketchpb.Store) *DenseStore

FromProto returns an instance of DenseStore that contains the data in the provided protobuf representation.

func NewDenseStore 

func NewDenseStore() *DenseStore

func (*DenseStore) Add 

func (s *DenseStore) Add(index int)

func (*DenseStore) AddBin 

func (s *DenseStore) AddBin(bin Bin)

func (*DenseStore) AddWithCount 

func (s *DenseStore) AddWithCount(index int, count float64)

func (*DenseStore) Bins 

func (s *DenseStore) Bins() <-chan Bin

func (*DenseStore) Clear added in v1.1.0 

func (s *DenseStore) Clear()

func (*DenseStore) Copy 

func (s *DenseStore) Copy() Store

func (*DenseStore) DecodeAndMergeWith added in v1.1.0 

func (s *DenseStore) DecodeAndMergeWith(b *[]byte, encodingMode enc.SubFlag) error

func (*DenseStore) Encode added in v1.1.0 

func (s *DenseStore) Encode(b *[]byte, t enc.FlagType)

func (*DenseStore) ForEach added in v1.1.0 

func (s *DenseStore) ForEach(f func(index int, count float64) (stop bool))

func (*DenseStore) IsEmpty 

func (s *DenseStore) IsEmpty() bool

func (*DenseStore) KeyAtRank 

func (s *DenseStore) KeyAtRank(rank float64) int

Return the key for the value at rank

func (*DenseStore) MaxIndex 

func (s *DenseStore) MaxIndex() (int, error)

func (*DenseStore) MergeWith 

func (s *DenseStore) MergeWith(other Store)

func (*DenseStore) MinIndex 

func (s *DenseStore) MinIndex() (int, error)

func (*DenseStore) Reweight added in v1.1.0 

func (s *DenseStore) Reweight(w float64) error

func (*DenseStore) ToProto 

func (s *DenseStore) ToProto() *sketchpb.Store

func (*DenseStore) TotalCount 

func (s *DenseStore) TotalCount() float64

type Provider added in v1.1.0 

type Provider func() Store

type SparseStore added in v1.1.0 

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

func NewSparseStore added in v1.1.0 

func NewSparseStore() *SparseStore

func (*SparseStore) Add added in v1.1.0 

func (s *SparseStore) Add(index int)

func (*SparseStore) AddBin added in v1.1.0 

func (s *SparseStore) AddBin(bin Bin)

func (*SparseStore) AddWithCount added in v1.1.0 

func (s *SparseStore) AddWithCount(index int, count float64)

func (*SparseStore) Bins added in v1.1.0 

func (s *SparseStore) Bins() <-chan Bin

func (*SparseStore) Clear added in v1.1.0 

func (s *SparseStore) Clear()

func (*SparseStore) Copy added in v1.1.0 

func (s *SparseStore) Copy() Store

func (*SparseStore) DecodeAndMergeWith added in v1.1.0 

func (s *SparseStore) DecodeAndMergeWith(b *[]byte, encodingMode enc.SubFlag) error

func (*SparseStore) Encode added in v1.1.0 

func (s *SparseStore) Encode(b *[]byte, t enc.FlagType)

func (*SparseStore) ForEach added in v1.1.0 

func (s *SparseStore) ForEach(f func(index int, count float64) (stop bool))

func (*SparseStore) IsEmpty added in v1.1.0 

func (s *SparseStore) IsEmpty() bool

func (*SparseStore) KeyAtRank added in v1.1.0 

func (s *SparseStore) KeyAtRank(rank float64) int

func (*SparseStore) MaxIndex added in v1.1.0 

func (s *SparseStore) MaxIndex() (int, error)

func (*SparseStore) MergeWith added in v1.1.0 

func (s *SparseStore) MergeWith(store Store)

func (*SparseStore) MinIndex added in v1.1.0 

func (s *SparseStore) MinIndex() (int, error)

func (*SparseStore) Reweight added in v1.1.0 

func (s *SparseStore) Reweight(w float64) error

func (*SparseStore) ToProto added in v1.1.0 

func (s *SparseStore) ToProto() *sketchpb.Store

func (*SparseStore) TotalCount added in v1.1.0 

func (s *SparseStore) TotalCount() float64

type Store 

type Store interface {
	Add(index int)
	AddBin(bin Bin)
	AddWithCount(index int, count float64)
	// Bins returns a channel that emits the bins that are encoded in the store.
	// Note that this leaks a channel and a goroutine if it is not iterated to completion.
	Bins() <-chan Bin
	// ForEach applies f to all elements of the store or until f returns true.
	ForEach(f func(index int, count float64) (stop bool))
	Copy() Store
	// Clear empties the store while allowing reusing already allocated memory.
	// In some situations, it may be advantageous to clear and reuse a store
	// rather than instantiating a new one. Keeping reusing the same store again
	// and again on varying input data distributions may however ultimately make
	// the store overly large and may waste memory space.
	Clear()
	IsEmpty() bool
	MaxIndex() (int, error)
	MinIndex() (int, error)
	TotalCount() float64
	KeyAtRank(rank float64) int
	MergeWith(store Store)
	ToProto() *sketchpb.Store
	// Reweight multiplies all values from the store by w, but keeps the same global distribution.
	Reweight(w float64) error
	// Encode encodes the bins of the store and appends its content to the
	// provided []byte.
	// The provided FlagType indicates whether the store encodes positive or
	// negative values.
	Encode(b *[]byte, t enc.FlagType)
	// DecodeAndMergeWith decodes bins that have been encoded in the format of
	// the provided binEncodingMode and merges them within the receiver store.
	// It updates the provided []byte so that it starts immediately after the
	// encoded bins.
	DecodeAndMergeWith(b *[]byte, binEncodingMode enc.SubFlag) error
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.