The highest tagged major version is
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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Sort ¶
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 ¶ added in v1.5.0
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 ¶ added in v1.5.0
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 ¶ added in v1.5.0
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 ¶ added in v1.5.0
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 ¶ added in v1.5.0
type FloatSorter[F constraints.Float] interface { // Sort sorts float slices Sort(x []F) }
FloatSorter describes types that can sort float slices
func NewFloatSorter ¶ added in v1.5.0
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 ¶ added in v1.5.0
type IntSorter[I constraints.Integer] interface { // Sort sorts integer slices. Sort(x []I) }
IntSorter describes types that can sort integer slices
func NewIntSorter ¶ added in v1.5.0
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.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package zfloat32 implements radix sort for []float32.
|
Package zfloat32 implements radix sort for []float32. |
|
Package zfloat64 implements radix sort for []float64.
|
Package zfloat64 implements radix sort for []float64. |
|
Package zint implements radix sort for []int.
|
Package zint implements radix sort for []int. |
|
Package zint32 implements radix sort for []int32.
|
Package zint32 implements radix sort for []int32. |
|
Package zint64 implements radix sort for []int64.
|
Package zint64 implements radix sort for []int64. |
|
Package zuint implements radix sort for []uint.
|
Package zuint implements radix sort for []uint. |
|
Package zuint32 implements radix sort for []uint32.
|
Package zuint32 implements radix sort for []uint32. |
|
Package zuint64 implements radix sort for []uint64.
|
Package zuint64 implements radix sort for []uint64. |