algorithm

Documentation

Overview

Package algorithm contains some useful algorithms

Index

• func BinarySearch[T any](s []T, cmp func(index int, element T) int) int
• func GetLargestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)
• func GetSmallestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)
• func GetTopKItems[T common.Sortable](inputChan <-chan T, topN int, sortOrder common.SortOrder) (result []T, err error)
• type Deque
  • func NewDeque[T any](optfs ...DequeOptFunc) (Deque[T], error)
• type DequeOptFunc
  • func WithDequeCurrentCapacity(size int) DequeOptFunc
  • func WithDequeMinimalCapacity(size int) DequeOptFunc
• type FIFO
  • func NewFIFO() *FIFO
  • func (f *FIFO) Get() any
  • func (f *FIFO) Len() int
  • func (f *FIFO) Put(d any)
• type PriorityItem
  • func (t PriorityItem[T]) GetVal() T
• type PriorityQ
  • func NewPriorityQ[T common.Sortable](order common.SortOrder) *PriorityQ[T]
  • func (pq *PriorityQ[T]) Len() int
  • func (pq *PriorityQ[T]) Peek() PriotiryItemItf[T]
  • func (pq *PriorityQ[T]) Pop() PriotiryItemItf[T]
  • func (pq *PriorityQ[T]) Push(v PriotiryItemItf[T])
• type PriotiryItemItf
• type SkipList
  • func NewSkiplist[T skiplist.Sortable]() SkipList[T]

Examples

• FIFO

Functions

func BinarySearch

func BinarySearch[T any](s []T, cmp func(index int, element T) int) int

BinarySearch searches for target in a sorted slice s.

cmp must implement the same ordering as the slice, i.e. it must return a negative value if the target is less than the element at index, a positive value if the target is greater than the element at index, and zero if the target is equal to the element at index.

Returns the index of target in s, or -1 if target is not present.

I thinks this function is better than built-in slices.BinarySearchFunc, since of the cmp function is more flexible, you can get the index and element at each iteration, that can enpower you to do more things rather than just comparing. BTW, I think there is no need for the target as the parameter, since you can wrap the target in the cmp function.

func GetLargestNItems

func GetLargestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)

GetLargestNItems get N highest priority items

func GetSmallestNItems

func GetSmallestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)

GetSmallestNItems get N smallest priority items

func GetTopKItems

func GetTopKItems[T common.Sortable](
	inputChan <-chan T,
	topN int,
	sortOrder common.SortOrder,
) (result []T, err error)

GetTopKItems calculate topN by heap

Types

type Deque

type Deque[T any] interface {
	PushBack(T)
	PushFront(T)
	PopFront() T
	PopBack() T
	Len() int
	Front() T
	Back() T
}

Deque

https://pkg.go.dev/github.com/gammazero/deque#Deque

func NewDeque

func NewDeque[T any](optfs ...DequeOptFunc) (Deque[T], error)

NewDeque new deque

type DequeOptFunc

type DequeOptFunc func(*dequeOpt) error

DequeOptFunc optional arguments for deque

func WithDequeCurrentCapacity

func WithDequeCurrentCapacity(size int) DequeOptFunc

WithDequeCurrentCapacity preallocate memory for deque

func WithDequeMinimalCapacity

func WithDequeMinimalCapacity(size int) DequeOptFunc

WithDequeMinimalCapacity set deque minimal capacity

type FIFO

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

FIFO is a lock-free First-In-First-Out queue

paper: https://1drv.ms/b/s!Au45o0W1gVVLuNxYkPzfBo4fOssFPQ?e=TYxHKl

Example

f := NewFIFO()
f.Put(1)
v := f.Get()
if v == nil {
	panic("empty")
}

fmt.Println(v.(int))

Output:

1

func NewFIFO

func NewFIFO() *FIFO

NewFIFO create a new FIFO queue

func (*FIFO) Get

func (f *FIFO) Get() any

Get pop data from the head of queue

func (*FIFO) Len

func (f *FIFO) Len() int

Len return the length of queue

func (*FIFO) Put

func (f *FIFO) Put(d any)

Put put an data into queue's tail

type PriorityItem

type PriorityItem[T common.Sortable] struct {
	// Val 	T
	Val T
	// Name whatever to identify this item
	Name any
}

PriorityItem priority item

func (PriorityItem[T]) GetVal

func (t PriorityItem[T]) GetVal() T

GetVal get value of priority item

type PriorityQ

type PriorityQ[T common.Sortable] struct {
	// contains filtered or unexported fields
}

PriorityQ priority queue

Do not use this structure directly, use `NewPriorityQ` instead.

func NewPriorityQ

func NewPriorityQ[T common.Sortable](order common.SortOrder) *PriorityQ[T]

NewPriorityQ create new PriorityQ

Args:

• order: common.SortOrderAsc or common.SortOrderDesc, if you want to get topN items, use common.SortOrderDesc, if you want to get bottomN items, use common.SortOrderAsc.

func (*PriorityQ[T]) Len

func (pq *PriorityQ[T]) Len() int

Len return length of priority queue

func (*PriorityQ[T]) Peek

func (pq *PriorityQ[T]) Peek() PriotiryItemItf[T]

Peek peek item from priority queue

func (*PriorityQ[T]) Pop

func (pq *PriorityQ[T]) Pop() PriotiryItemItf[T]

Pop pop item from priority queue

func (*PriorityQ[T]) Push

func (pq *PriorityQ[T]) Push(v PriotiryItemItf[T])

Push push item into priority queue

type PriotiryItemItf

type PriotiryItemItf[T common.Sortable] interface {
	GetVal() T
}

PriotiryItemItf priority item interface

type SkipList

type SkipList[T skiplist.Sortable] struct {
	*skiplist.SkipList[T]
}

SkipList skiplist

func NewSkiplist

func NewSkiplist[T skiplist.Sortable]() SkipList[T]

NewSkiplist new skiplist

https://github.com/sean-public/fast-skiplist