Generic Data Structures

Auto-scalable Ring Buffer, Double Ended Queue#

Ringbuf is auto-scalable ring buffer. Ringbuf also implements deque (Double Ended Queue).

It’s better to implement deque based on ringbuf instead of slice or list.

• In contrast to slice, ringbuf can reuse memory block of removed elements, and therefore less memory allocation and less GC.
  Another disadvantage of slice is that memory block can not be recycled in time. Even though a part of a slice’s underlying array won’t be reused, that part can not be recycled instantly, because the underlying array is referenced by the slice as a whole.
• In contrast to list, ringbuf has continuous memory space, no front and back pointers, and therefore higher access speed and less memory footprint.

Import

import "github.com/burningxflame/gx/ds/ringbuf"

API:
PushBack, PushFront, PeekBack, PeekFront, PopBack, PopFront, Len, Range

Sample:
ringbuf ↗

Queue#

Queue is FIFO, a subset of deque.

Import

import "github.com/burningxflame/gx/ds/queue"

API:
Enq, Peek, Deq, Len, Range

Sample:
queue ↗

Stack#

Stack is LIFO, another subset of deque.

Import

import "github.com/burningxflame/gx/ds/stack"

API:
Push, Peek, Pop, Len, Range

Sample:
stack ↗

Heap#

Import

import "github.com/burningxflame/gx/ds/heap"

API:
Push, Pop, Len, Range

Sample:
heap ↗

Set#

Import

import "github.com/burningxflame/gx/ds/set"

API:
Add, Delete, Len, Contain, Equal, Range, Union, Intersect, Diff

Sample:
set ↗

Sorted Slice#

Import

import "github.com/burningxflame/gx/ds/sslice"

API:
Insert, Search, SearchFunc, Slice, Delete

Sample:
sslice ↗

Benchmark#

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

Note: In each of the following benchmark results, the second colume (N) represents collection size, i.e., the number of elements in a collection.

Ring Buffer, Double Ended Queue:

BenchmarkPushBack-12      92285098         17.93 ns/op       47 B/op        0 allocs/op
BenchmarkPushFront-12     95364520         14.98 ns/op       46 B/op        0 allocs/op
BenchmarkPopFront-12      385959025          3.214 ns/op        0 B/op        0 allocs/op
BenchmarkPopBack-12       359027050          3.602 ns/op        0 B/op        0 allocs/op

Queue:

BenchmarkEnq-12    	58082024	        17.98 ns/op	      49 B/op	       0 allocs/op
BenchmarkDeq-12    	616338339	         4.427 ns/op	       0 B/op	       0 allocs/op

Stack:

BenchmarkPush-12    	86427447	        16.37 ns/op	      41 B/op	       0 allocs/op
BenchmarkPop-12     	585195102	         3.419 ns/op	       0 B/op	       0 allocs/op

Heap:

BenchmarkPush-12    	35654341	        41.86 ns/op	      50 B/op	       0 allocs/op
BenchmarkPop-12     	 5362929	       234.2 ns/op	       7 B/op	       0 allocs/op

Set:

BenchmarkAdd-12       	 7962375	       203.7 ns/op	      48 B/op	       0 allocs/op
BenchmarkDelete-12    	16687696	        90.03 ns/op	       0 B/op	       0 allocs/op