README
¶
priorityqueue 
A collection of performant, concurrent safe, complex abstract data structures used for priority queues.
Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Hierarchical Queue description
An O(1)/O(1 + K) priority queue implementation for small integers, that uses an assembly of N simple queues.
It is optimized for large amount of data BUT with small value priorities ( <= 255 ). Can store any type of elements/values.
Hierarchical Queue usages
- image/video processing
- networking (routing)
- anywhere you have a small range of priorities/channels.
The original algorithm has O(1) dequeue complexity, but that adds a very strict limitation: a queue that has been empty it is removed and cannot be recreated. This means the instance cannot be reused once the dequeue finish, and inserting elements during the dequeue decrease the performance. I decided that limits the scope of the algorithm too much and has a low chance to be used in the real world, so I removed the complexity.
Hierarchical Queue implementation:
(a) - normal queue, (b) - list of queues
It is an array of buckets. The key is the priority and the bucket is a queue. Queues are linked lists dynamically growing circular slice of blocks, the advantage is that no memory preallocation is needed and the queue/dequeue is O(1).
The keys are uint8and values can be any type interface{}.
Priority: 0 (highest) - n (lowest)
Inspired by papers:
- Revisiting Priority Queues for Image Analysis, Cris L. Luengo Hendriks
- Hierarchical Queues: general description and implementation in MAMBA Image library, Nicolas Beucher and Serge Beucher
Hierarchical Queue benchmarks
This syncronous tests were done to demonstrate that Enqueue/Dequeue is O(1) regardless of the priority queue size.
The avg value is 50 ns/op using random distributed priorities and 25 ns/op using linear priorities on an I7 2.7GHz 64bit windows.
Previous implementation used list.List linked lists, they were replaced with a queue 10x faster.
Hierarhical Heap
It is a version of the Hierarchical Queue structure, adding some complexity (O(log n/k)) but removing it's limitations, proposed by Cris L. Luengo Hendriks paper
Unlike HQ that has 1 bucket for each priority value, HH priorities are grouped in K buckets.
For the best performance benchmark the Enq/Deq functions with your own data, and tweak the buckets,minP,maxP parameters!
Hierarchical Heap implementation
The keys are intand values can be any type interface{}.
Priority: 0 (highest) - n (lowest)
The HH is an array of buckets, each bucket contains 0-n number of priority values. The buckets are spread based on the priority with a linear formula:
bucketIndex = (priority - minPriority)/(maxPriority - minPriority) * bucketsCount
Buckets are Min Implicit Heaps (special binary tree) that stores all values for a specific range of priorities. Example: pMin=0, pMax=100 (0-100 priorities), K=15 (buckets) Enqueue("a", 21) will add "a" to bucket i, where i = (21 − pmin) / (pmax − pmin) * K = 3
By dividing the N elements in the queue over k buckets, the average size of each heap is reduced by a factor k, and the enqueueing and dequeueing operations thus are of order O(logN/k) if the buckets are chosen correctly. Of course, the actual algorithmic complexity depends strongly on the distribution of priority values. Calculating the bucket index adds a constant time to the enqueue operation that needs to be amortised by the O(logk) reduction in time to enqueue the element in the implicit heap. It is therefore necessary to choose k large enough.
Hierarchical Heap benchmarks
With the right bucket/priority diversity it can aproach the HQ performance by a factor of 0.5.
Documentation
¶
Overview ¶
Package priorityqueue implements a series of performant, concurrency safe data structures used for priority queues.
Hierarchical Queue - O(1) priority queues for large amounts of small priorities (uint8)
Hierarchical Heap - O(log n/k) priority queue for large amounts of data, slower than HQ but has no limitations.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HierarchicalHeap ¶
HierarchicalHeap It is a modification of the Hierarchical Queue structure, adding some complexity (O(log n/k)) but removing it's limitations. Inspired by [Cris L. Luengo Hendriks paper](http://www.cb.uu.se/~cris/Documents/Luengo2010a_preprint.pdf)
Unlike HQ that has 1 bucket for each priority value, HHeap priorities are grouped (using a linear mapping formula) in K buckets. Buckets are Implicit heaps (special binary tree) that stores all values for a specific range of priorities. Example: pMin=0, pMax=100 (0-100 priorities), K=15 (buckets) Enqueue("a", 21) will add "a" to bucket i, where i = (21 − pmin) / (pmax − pmin) * K = 3
For the best performance benchmark the Enq/Deq functions with your own data, and tweak the buckets,minP,maxP parameters! .
func NewHierarchicalHeap ¶
func NewHierarchicalHeap(buckets, pMin, pMax int, autoMutexLock bool) (*HierarchicalHeap, error)
NewHierarchicalHeap Generates a new HQ. 0 priority = max
func (*HierarchicalHeap) Dequeue ¶
func (h *HierarchicalHeap) Dequeue() (v interface{}, err error)
Dequeue Remove and return the highest key (lowest priority) O(log n/k)
func (*HierarchicalHeap) Enqueue ¶
func (h *HierarchicalHeap) Enqueue(value interface{}, priority int) error
Enqueue add a new key/value pair in the queue. 0 priority = max. O(log n/k)
func (*HierarchicalHeap) Len ¶
func (h *HierarchicalHeap) Len() int
Len Return the count of all values from all priorities. O(1)
type HierarchicalQueue ¶
HierarchicalQueue An O(1)/O(1)* priority queue implementation for small integers See the README for more info.
Example ¶
autoLockMutex := false
var lowestPriority uint8 = 10 //highest is 0
l := NewHierarchicalQueue(lowestPriority, autoLockMutex)
l.Enqueue("a", 2)
l.Enqueue("b", 0)
first, _ := l.Dequeue()
fmt.Printf("first is %v", first)
Output: first is b
func NewHierarchicalQueue ¶
func NewHierarchicalQueue(lowestPriority uint8, autoMutexLock bool) *HierarchicalQueue
NewHierarchicalQueue Generates a new HQ
func (*HierarchicalQueue) Dequeue ¶
func (l *HierarchicalQueue) Dequeue() (v interface{}, err error)
Dequeue Return the highest priority value (0-highest priority, n-lowest)
func (*HierarchicalQueue) Enqueue ¶
func (l *HierarchicalQueue) Enqueue(value interface{}, priority uint8) (err error)
Enqueue Add a new element with a priority (0-highest priority, n-lowest)
func (*HierarchicalQueue) Len ¶
func (l *HierarchicalQueue) Len() int
Len Return the count of all values from all priorities
func (*HierarchicalQueue) LenPriority ¶
func (l *HierarchicalQueue) LenPriority(priority uint8) int
LenPriority Returns the count of all values from a specific priority queue
Source Files