zermelo

README

zermelo

A radix sorting library for Go. Trade memory for speed!

import "github.com/shawnsmithdev/zermelo"

func foo(large []uint64)
    zermelo.SortIntegers(large)
}

About

Zermelo is a sorting library featuring implementations of radix sort. I am especially influenced here by these two articles that describe various optimizations and how to work around the typical limitations of radix sort.

You will generally only want to use zermelo if you won't mind the extra memory used for buffers and your application frequently sorts slices of supported types with at least 256 elements (128 for 32-bit types, 386 for []float64). The larger the slices you are sorting, the more benefit you will gain by using zermelo instead of the standard library's in-place comparison sort or slices.Sort().

Etymology

Zermelo is named after Ernst Zermelo, who developed the proof for the well-ordering theorem.

Supported Types

SortIntegers and IntSorter support constraints.Integer slices, that is []int, []uint64, []byte, etc, and derived types.

SortFloats and FloatSorter support constraints.Float slices, specifically []float32 and []float64 and derived types.

Sorter

An IntSorter or FloatSorter will reuse buffers created during Sort() calls. This is not thread safe. Buffers are grown as needed at a 25% exponential growth rate. This means if you sort a slice of size n, subsequent calls with slices up to n * 1.25 in length will not cause another buffer allocation. This does not apply to the first allocation, which will make a buffer of the same size as the requested slice. This way, if the slices being sorted do not grow in size, there is no unused buffer space.

import "github.com/shawnsmithdev/zermelo"

func foo(bar [][]uint64) {
    sorter := zermelo.NewIntSorter[uint64]()
    for _, x := range(bar) {
        sorter.Sort(x)
    }
}

Documentation

Overview

Package zermelo is a library for sorting slices in Go.

Index

• func Sort(x any) error
• func SortFloats[F constraints.Float](x []F)
• func SortFloatsBYOB[F constraints.Float](x, buffer []F)
• func SortIntegers[T constraints.Integer](x []T)
• func SortIntegersBYOB[T constraints.Integer](x, buffer []T)
• type FloatSorter
  • func NewFloatSorter[F constraints.Float]() FloatSorter[F]
• type IntSorter
  • func NewIntSorter[I constraints.Integer]() IntSorter[I]
• type Sorter
  • func New() Sorter

Functions

func Sort

func Sort(x any) error

Sort attempts to sort x.

If x is a supported slice type, this library will be used to sort it. Otherwise, if x implements sort.Interface it will passthrough to the sort.Sort() algorithm. Returns an error on unsupported types. As of v1.5.0, is generally preferable to use zermelo.SortIntegers or zermelo.SortFloats instead.

func SortFloats

func SortFloats[F constraints.Float](x []F)

SortFloats sorts float slices. If the slice is large enough, radix sort is used by allocating a new buffer.

func SortFloatsBYOB

func SortFloatsBYOB[F constraints.Float](x, buffer []F)

SortFloatsBYOB sorts float slices with radix sort using the provided buffer. len(buffer) must be greater or equal to len(x).

func SortIntegers

func SortIntegers[T constraints.Integer](x []T)

SortIntegers sorts integer slices. If the slice is large enough, radix sort is used by allocating a new buffer.

func SortIntegersBYOB

func SortIntegersBYOB[T constraints.Integer](x, buffer []T)

SortIntegersBYOB sorts integer slices with radix sort using the provided buffer. len(buf) must be greater or equal to len(x).

Types

type FloatSorter

type FloatSorter[F constraints.Float] interface {
	// Sort sorts float slices
	Sort(x []F)
}

FloatSorter describes types that can sort float slices

func NewFloatSorter

func NewFloatSorter[F constraints.Float]() FloatSorter[F]

NewFloatSorter creates a new FloatSorter that will use radix sort on large slices and reuses buffers. The first sort creates a buffer the same size as the slice being sorted and keeps it for future use. Later sorts may grow this buffer as needed. The FloatSorter returned is not thread safe. Using this sorter can be much faster than repeat calls to SortFloats.

type IntSorter

type IntSorter[I constraints.Integer] interface {
	// Sort sorts integer slices.
	Sort(x []I)
}

IntSorter describes types that can sort integer slices

func NewIntSorter

func NewIntSorter[I constraints.Integer]() IntSorter[I]

NewIntSorter creates a new IntSorter that will use radix sort on large slices and reuses buffers. The first sort creates a buffer the same size as the slice being sorted and keeps it for future use. Later sorts may grow this buffer as needed. The IntSorter returned is not thread safe. Using this sorter can be much faster than repeat calls to SortIntegers.

type Sorter

type Sorter interface {
	// Sort attempts to sort x, returning an error if unable to sort.
	Sort(x any) error
	// CopySort returns a sorted copy of x, or an error if unable to copy or sort.
	CopySort(x any) (any, error)
}

Sorter can sort slices. This interface is deprecated, use IntSorter or FloatSorter.

func New

func New() Sorter

New creates a Sorter that reuses buffers on repeated Sort() or CopySort() calls on the same type. This is not thread safe. CopySort() does not support passthrough of sort.Interface values. This style of sorter is deprecated, use NewIntSorter or NewFloatSorter.