yagh

README

Yet Another Go Heap (YAGH)

YAGH is a small Go package that provides its clients with the IntMap[C] data structure, a priority map that orders integers from 0 to N-1 by non-decreasing cost of type C.

Data structure IntMap[C] is tailored for use cases where:

• The elements to be inserted in the map are known in advance and can be identified from 0 to N-1.
• The map is meant to experience an arbitrarily large number of mutations (including random access updates of its elements) over its lifetime.

Its operations have comparable time complexities to traditional heaps.

Garbage Friendly 🌱

IntMap[C] is designed for scenarios where frequent updates and mutations are expected. The map's constructor pre-allocates all necessary memory to store up to N elements, thus eliminating the need for further memory allocations during its lifetime. This design ensures consistent speed performance, as it minimizes variations caused by memory allocation or garbage collection.

Benchmark

We've compared the performance of YAGH's IntMap to Go's standard container/heap on multiple heapsorts of 10000 random entries (see benchmark results below).

To run the benchmark, simply run the following command from the root of this repository:

go test -benchmem -bench . 

This should output something similar to this:

goos: darwin
goarch: arm64
pkg: github.com/rhartert/yagh
BenchmarkIntMapSort-8  1030  1082324 ns/op       0 B/op      0 allocs/op
BenchmarkGoHeapSort-8   712  1687413 ns/op  320000 B/op  20000 allocs/op

On average, YAGH achieves a 1.56x speed-up compared to Go's standard heap. Also, note that zero allocs are made in BenchmarkIntMapSort (i.e. the heapsort using YAGH).

Documentation

Overview

Package yagh exposes the IntMap[C] data structure, a priority map that orders integers from 0 to N-1 by non-decreasing cost of type `C`. In case of ties, the smallest integer wins.

Data structure IntMap is tailored for use cases where:

• The elements to be inserted in the map are known in advance and can be identified from 0 to N-1.
• The map is meant to experience an arbitrarily large number of mutations (including random access updates of its elements) over its lifetime.

In particular, this implementation aims to minimize memory allocations and avoid creating objects that would ultimately have to garbage collected.

Index

• type Entry
  • func (e Entry[C]) String() string
• type IntMap
  • func New[C cmp.Ordered](n int) *IntMap[C]
  • func (h *IntMap[C]) Capa() int
  • func (h *IntMap[C]) Clear()
  • func (h *IntMap[C]) Contains(elem int) bool
  • func (h *IntMap[C]) GetCost(elem int) C
  • func (h *IntMap[C]) GrowBy(k int)
  • func (h *IntMap[C]) Min() (Entry[C], bool)
  • func (h *IntMap[C]) Pop() (Entry[C], bool)
  • func (h *IntMap[C]) Put(elem int, cost C) bool
  • func (h *IntMap[C]) Size() int
  • func (h *IntMap[C]) String() string

Examples

• IntMap.Capa
• IntMap.Clear
• IntMap.GetCost
• IntMap.GrowBy
• IntMap.Min
• IntMap.Pop
• IntMap.Put
• IntMap.Size
• New

Types

type Entry

type Entry[C cmp.Ordered] struct {
	Elem int
	Cost C
}

func (Entry[C]) String

func (e Entry[C]) String() string

type IntMap

type IntMap[C cmp.Ordered] struct {
	// contains filtered or unexported fields
}

func New

func New[C cmp.Ordered](n int) *IntMap[C]

New initializes and returns a new instance of IntMap to handle elements ranging from 0 to n-1, where n is the capacity of the map. This constructor pre-allocates the necessary memory to accommodate up to n elements, thus ensuring that no further memory allocation will be required during the instance's lifetime.

Example

m := New[float64](5)

fmt.Println(m)

// Add a few elements.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Put(4, 0.3)
m.Put(3, 0.4)

fmt.Println(m)

Output:

IntMap[]
IntMap[2:0.1 1:0.2 4:0.3 3:0.4]

func (*IntMap[C]) Capa

func (h *IntMap[C]) Capa() int

Capacity returns the capacity of the IntMap.

Example

m := New[float64](0)
fmt.Println(m.Capa())

m.GrowBy(2)
fmt.Println(m.Capa())

m.GrowBy(3)
fmt.Println(m.Capa())

Output:

0
2
5

func (*IntMap[C]) Clear

func (h *IntMap[C]) Clear()

Clear removes all the elements contained in the IntMap in O(Size). It is more efficient to call Clear than Pop repeatedly.

Example

m := New[float64](5)

// Add new elements.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Put(3, 0.3)
m.Put(4, 0.4)

// Remove everything.
m.Clear()

fmt.Println(m.Size())

Output:

0

func (*IntMap[C]) Contains

func (h *IntMap[C]) Contains(elem int) bool

Contains returns true if elem is in the map; it returns false otherwise.

func (*IntMap[C]) GetCost

func (h *IntMap[C]) GetCost(elem int) C

GetCost returns the last cost that was assigned to elem (no matter if elem is still contained in the IntMap or not). It returns the cost's zero value if the element was never added to the IntMap.

Example

m := New[int](5)

fmt.Println(m.GetCost(2))
m.Put(2, 2)
fmt.Println(m.GetCost(2))
m.Pop()
fmt.Println(m.GetCost(2))

Output:

0
2
2

func (*IntMap[C]) GrowBy

func (h *IntMap[C]) GrowBy(k int)

GrowBy increases the IntMap's capacity to accomodate k new elements. This method does nothing if k is not positive.

Example

m := New[float64](2)

m.Put(1, 0.1)
m.GrowBy(3)
m.Put(2, 0.2)
m.Put(3, 0.3)

fmt.Println(m)

Output:

IntMap[1:0.1 2:0.2 3:0.3]

func (*IntMap[C]) Min

func (h *IntMap[C]) Min() (Entry[C], bool)

Min returns the entry with the smallest cost. The second returned value (ok) is a bool that indicates whether a valid entry was found. If the map is empty, it returns false, along with a zero value for the entry.

Example

m := New[float64](5)

// Add a few elements.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Put(3, 0.3)
m.Put(4, 0.4)

e, _ := m.Min()
fmt.Printf("%d:%v\n", e.Elem, e.Cost)

Output:

2:0.1

func (*IntMap[C]) Pop

func (h *IntMap[C]) Pop() (Entry[C], bool)

Pop returns and removes the entry with the smallest cost. The second returned value (ok) is a bool that indicates whether a valid entry was found. If the map is empty, it returns false, along with a zero value for the entry.

Example

m := New[float64](5)

// Add a few elements to pop.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Put(4, 0.3)
m.Put(3, 0.4)

for m.Size() > 0 {
	e, _ := m.Pop()
	fmt.Printf("%d:%v\n", e.Elem, e.Cost)
}

Output:

2:0.1
1:0.2
4:0.3
3:0.4

func (*IntMap[C]) Put

func (h *IntMap[C]) Put(elem int, cost C) bool

Put inserts a new element into the map or updates its cost (and position) if it already exists. It returns true if the element was not previously in the map; otherwise, it returns false.

Example

m := New[float64](5)

// Add new elements.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Put(3, 0.3)
m.Put(4, 0.4)

// Update the values of existing elements.
m.Put(1, 0.01)
m.Put(2, 0.02)

// Prioritized over elem 1 due to tie-breaking on elem value.
m.Put(0, 0.01)

for m.Size() > 0 {
	e, _ := m.Pop()
	fmt.Printf("%d:%v\n", e.Elem, e.Cost)
}

Output:

0:0.01
1:0.01
2:0.02
3:0.3
4:0.4

func (*IntMap[C]) Size

func (h *IntMap[C]) Size() int

Size returns the number of elements in the IntMap.

Example

m := New[float64](5)

// Add and remove some elements.
m.Put(2, 0.1)
m.Put(1, 0.2)
m.Pop()
m.Put(4, 0.3)
m.Put(3, 0.4)
m.Pop()

fmt.Println(m.Size())

Output:

2

func (*IntMap[C]) String

func (h *IntMap[C]) String() string