Go API reference
Every public function of the Go package, a cgo wrapper over the C library, with its parameters and results (Kwker 0.1.0).
Import path: kwker.io/go/kwker
Package kwker sorts, selects and ranks slices of numbers in place and without copies, with the fastest engine for the CPU chosen at run time (the C library libkwker_c).
a := []float64{3.5, 0.5, 2, 1}
kwker.Sort(a) // [0.5 1 2 3.5]
values, positions := kwker.TopK(a, 2, kwker.Descending, true) // [3.5 2] [3 2]
Key types: uint8, int8, uint16, int16, uint32, int32, float32, uint64, int64, float64 (and types defined on them).
Install: the Kwker C package first (the release archive, .deb or .rpm:
pkg-config must find kwker), then go get kwker.io/go/kwker. Inside the Kwker
repository, build with -tags kwker_repo to link the workspace's own build
instead (link_repo.go: target/release/libkwker_c.a, from cargo build --release
-p kwker-c or ss go).
Notes: floats sort -0.0 before +0.0 and NaNs last (first with NaNsFirst). Sort is not stable; Argsort, ArgSelect and TopK keep equal keys in index order.
Functions
ArgSelect Page
func ArgSelect[T Key](s []T, k int, o Order) []int
ArgSelect returns the indices of the stable order's first k keys, in any order. k > len(s) means all.
Remarks: The positions of the stable order's first k keys, in any order (rule 6). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Top-k and selection: Only the positions
Argsort Page
func Argsort[T Key](s []T, o Order) []int
Argsort returns the stable sorting permutation of s in order o (s is not modified).
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Get the order, not the sorted data, Order and ranking: The order of an array: argsort, Languages: The same calls in every language, Order and ranking: Reorder several columns together
ArgsortStrings Page
func ArgsortStrings(s []string, c Collation) []int
ArgsortStrings returns the stable order of s in collation c: s[idx[0]], s[idx[1]], ... is sorted, and strings the collation treats as equal keep their input order. s is not modified.
Examples: Strings: The order of strings
BucketCounts Page
func BucketCounts[T Key](values, boundaries []T, right bool, o Order) []uint64
BucketCounts counts values per bucket of the sorted boundaries: len(boundaries)+1 counts. With right false, v lands in bucket i when boundaries[i-1] < v <= boundaries[i] (torch.bucketize); with right true when boundaries[i-1] <= v < boundaries[i].
Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).
Examples: Searching sorted data: How many in each bucket? bucket_counts
CountByKey Page
func CountByKey[K Key](keys []K, o Order) ([]K, []uint64)
CountByKey returns the distinct keys in order o and how often each occurs.
Examples: Groups, merges and sets: Totals per key: reduce_by_key
GroupCodes Page
func GroupCodes(cols ...Column) (codes []uint32, first []int, sizes []int)
GroupCodes numbers the rows' groups 0.. in the columns' lexicographic order (equal keys: one group): codes per row, each group's first row and size.
Examples: Groups, merges and sets: Group several key columns: group_codes
ISA Page
func ISA() string
ISA returns the engine in use: "avx512", "avx2", "sse42", "neon", "sve" or "portable".
Remarks: The engine changes only the speed, never a result (rule 11).
KWayMerge Page
func KWayMerge[T Key](o Order, runs ...[]T) []T
KWayMerge merges sorted runs (each sorted in order o) into one sorted slice; equal keys keep run, then index order.
Examples: Groups, merges and sets: Merge sorted lists: kway_merge
LexSelect Page
func LexSelect(k int, cols ...Column) int
LexSelect returns the row at position k of LexSort's order, without sorting.
LexSort Page
func LexSort(cols ...Column) []int
LexSort returns the stable permutation sorting the rows by the columns, the first most significant.
Examples: Order and ranking: Sort by several columns
LexTopK Page
func LexTopK(k int, cols ...Column) []int
LexTopK returns the first min(k, n) rows of LexSort's order without sorting every row.
Examples: Order and ranking: Sort by several columns
Observe Page
func Observe(f func()) (string, error)
Observe runs f with the engines' path trace on and returns the report as JSON: {"isa", "traced", "stages": [{"id", "name", "about", "count", "cycles"}, ...]} - the engine stages the calls ran (the x86 engines are traced). Process-wide; an error while another observation runs.
PartialSort Page
func PartialSort[T Key](s []T, k int, o Order)
PartialSort puts the first k keys of order o, sorted, into s[:k]; the rest in any order. k > len(s) sorts all.
Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Top-k and selection: Sort only the beginning
PartialSortKV Page
func PartialSortKV[T Key, V any](keys []T, values []V, k int, o Order)
PartialSortKV sorts the first min(k, len) keys in order o at the front, each with its value.
Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6).
Examples: Sorting keys with values: Only the first k pairs
PercentRank Page
func PercentRank[T Key](s []T, o Order) []float64
PercentRank returns (min rank - 1) / (n - 1) for every key (SQL PERCENT_RANK).
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
PermuteInPlace Page
func PermuteInPlace[R any](records []R, perm []int)
PermuteInPlace reorders records so that record j becomes the one at perm[j] (an Argsort result applied), without a copy of the records (n bits of scratch). Panics unless perm is a permutation of 0..len(records).
Examples: Order and ranking: Reorder records in place
Rank Page
func Rank[T Key](s []T, o Order, ties Ties) []uint64
Rank returns the 1-based rank of every key of s in order o (ranks[i] belongs to s[i]); s is not modified.
Remarks: Ordinal ranks give equal keys increasing ranks in input order (rule 6). Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
RankAverage Page
func RankAverage[T Key](s []T, o Order) []float64
RankAverage returns the average ranks (1-based; equal keys share the mean of their positions, as scipy.stats.rankdata's "average").
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Order and ranking: Ranks
ReduceByKey Page
func ReduceByKey[K Key, V ValueOf](keys []K, values []V, op Reduce, o Order) ([]K, []V)
ReduceByKey returns the distinct keys in order o and one reduction of their values each.
Examples: Groups, merges and sets: Totals per key: reduce_by_key
SearchSorted Page
func SearchSorted[T Key](sorted, queries []T, right bool, o Order) []int
SearchSorted returns each query's insertion position in sorted (sorted in order o, not checked): before equal keys, or after them with right.
Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).
Examples: Searching sorted data: Where does a value go? searchsorted, Searching sorted data: Which bucket? bucketize
Select Page
func Select[T Key](s []T, k int, o Order)
Select moves the key a full sort in order o would put at s[k] there; every key before it sorts before or equal to it, every key after it after or equal. Neither side is sorted. Panics unless 0 <= k < len(s).
Remarks: Position k holds the key a full sort puts there; the keys before it are ordered before or equal to it, the keys after it after or equal (rule 7). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: The median, without a full sort, Top-k and selection: The median and other positions
SelectKV Page
func SelectKV[T Key, V any](keys []T, values []V, k int, o Order)
SelectKV is Select with the values: keys[k] gets the key a full sort in order o would put there, with its value; neither side is sorted (k < len).
Remarks: Position k holds the key a full sort puts there; the keys before it are ordered before or equal to it, the keys after it after or equal (rule 7). Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6).
SetISA Page
func SetISA(name string) (string, error)
SetISA caps the engine of later calls at run time ("avx512", "avx2", "sse42", "neon", "simd128", "portable"; "" for the best the CPU and KWKER_ISA allow) and returns the engine now in use. Results never depend on the engine, only speed. Process-wide.
Remarks: The engine changes only the speed, never a result (rule 11).
Examples: Runtime controls: Fallback switches
SetOperation Page
func SetOperation[T Key](a, b []T, op SetOp, multiset bool, o Order) []T
SetOperation combines a and b (both sorted in order o, not checked) into a new sorted slice: by presence, or with multiset by copy counts (as C++ std::set_*).
Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).
Examples: Groups, merges and sets: Set operations
Sort Page
func Sort[T Key](s []T)
Sort sorts s in place, ascending.
Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Sort an array, Core concepts: In place or a copy, Runtime controls: Fallback switches, Sorting: Sort in place
SortFile Page
func SortFile[T Key](input, output string, memory int, o Order, threads int) error
SortFile sorts the file input of native-endian T keys into output (may be the same path) with about memory bytes of buffers (0: 256 MiB) - files larger than memory included.
Examples: Large data: Sort a file larger than memory
SortKV Page
func SortKV[T Key, V any](keys []T, values []V, o Order)
SortKV sorts keys in place in order o and moves each value with its key. V must hold no Go pointers and be 1, 2, 4, 8, 12, 16, 24 or 32 bytes large; equal keys' values end in unspecified order. Panics if the lengths differ.
Remarks: Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Core concepts: In place or a copy, Sorting keys with values: Sort keys and values together
SortKVStable Page
func SortKVStable[T Key, V any](keys []T, values []V, o Order)
ISA is the engine in use: "avx512", "avx2" or "portable". SortKVStable is SortKV with equal keys' values kept in input order (allocates O(n)).
Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Sorting keys with values: Keep equal keys in order: the stable sort
SortMT Page
func SortMT[T Key](s []T, o Order, threads int)
SortMT sorts s in order o on threads threads (0: the default count).
The result is exactly SortOrder's.
Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).
Examples: Sorting: Big arrays: use more cores, Large data: Use several cores
SortOrder Page
func SortOrder[T Key](s []T, o Order)
SortOrder sorts s in place in order o.
Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Largest first, or a sorted copy, Core concepts: Special float values, Sorting: Largest first, Sorting: Missing values (NaN)
SortRows Page
func SortRows[T Key](s []T, rowLen int, o Order)
SortRows sorts each row of the row-major matrix s (rows of rowLen keys) in place. Panics unless rowLen divides len(s).
Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Sorting: Sort each row
SortStrings Page
func SortStrings(s []string, c Collation)
SortStrings sorts s in place in collation c; strings the collation treats as equal keep their order (stable).
Examples: Strings: Sort a list of strings
TopK Page
func TopK[T Key](s []T, k int, o Order, sorted bool) ([]T, []int)
TopK returns the stable order's first k keys and their indices (in order if sorted). k > len(s) means all.
Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.
Examples: Quickstart: Kwker Core: Find the top results, Use Kwker from Go: The program, Top-k and selection: The k largest or smallest values, Languages: The same calls in every language
TopKByGroup Page
func TopKByGroup[T Key](s []T, groups []int64, k int, o Order) (labels []int64, offsets []int, idx []int)
TopKByGroup returns, for every distinct group label (ascending), the indices of that group's first k keys in the stable order: labels[i] owns indices[offsets[i]:offsets[i+1]].
Examples: Top-k and selection: Top-k per group
TopKMasked Page
func TopKMasked[T Key](s []T, mask []bool, k int, o Order, sorted bool) ([]T, []int)
TopKMasked returns the first k keys of the stable order among the positions where mask is true, and their indices (fewer when fewer positions take part). mask has the length of s.
Examples: Top-k and selection: Top-k with a filter
Unique Page
func Unique[T Key](s []T) (values []T, inverse []int, counts []uint64)
Unique returns the distinct keys of s ascending, the index of each key's value (inverse, len(s)) and each value's count, as numpy.unique(return_inverse, return_counts).
Remarks: -0.0 and +0.0 are one value; every NaN is a value of its own, listed last (rule 15).
Version Page
func Version() string
Version is the library version.
WithScratchLimit Page
func WithScratchLimit(bytes int, f func())
WithScratchLimit runs f with Kwker's extra memory limited to bytes (0: Sort, Select, PartialSort and SortKV allocate nothing). The limit belongs to an OS thread, so f runs locked to one; results never change, some inputs sort slower.
Examples: Large data: Limit the extra memory
Types
Collation Page
type Collation uint32
Collation is how SortStrings and ArgsortStrings compare strings.
CollateBytes Page
const (
CollateBytes Collation = 0 // byte order (for UTF-8: Unicode code point order)
CollateCaseless Collation = 1 // ASCII letters compare without case
CollateNatural Collation = 2 // digit runs compare as numbers: "file2" before "file10", leading zeros ignored
CollateNaturalCaseless Collation = 3 // both
)
Column Page
type Column struct {
// Has unexported fields.
}
Column is one key column of LexSort / LexTopK / LexSelect.
Col Page
func Col[T Key](s []T, o Order) Column
Col makes a Column of s in order o.
Examples: Order and ranking: Sort by several columns, Groups, merges and sets: Group several key columns: group_codes
Key Page
type Key interface {
~uint8 | ~int8 | ~uint16 | ~int16 | ~uint32 | ~int32 | ~float32 | ~uint64 | ~int64 | ~float64
}
Key is a primitive key type Kwker sorts.
Order Page
type Order uint32
Order selects the direction and the NaN placement; combine with |.
Ascending Page
const (
Ascending Order = 0 // smallest first, NaNs last
Descending Order = 1 // largest first
NaNsFirst Order = 2 // NaNs at the start instead of the end
)
Reduce Page
type Reduce int
Reduce is the reduction ReduceByKey applies per key.
ReduceSum Page
const (
ReduceSum Reduce = 0 // integers wrap; floats add in input order
ReduceMin Reduce = 1 // in the ascending order: -0.0 below +0.0, NaN above all
ReduceMax Reduce = 2
ReduceFirst Reduce = 3 // the key's first value in input order
ReduceLast Reduce = 4
)
SetOp Page
type SetOp int
SetOp selects a sorted-set operation.
Intersection Page
const (
Intersection SetOp = 0
Union SetOp = 1
Difference SetOp = 2 // a minus b
SymmetricDifference SetOp = 3
)
Ties Page
type Ties int
Ties selects how Rank numbers equal keys.
Ordinal Page
const (
Ordinal Ties = 0 // distinct ranks in the stable order (equal keys by index)
Min Ties = 1 // every equal key gets the group's lowest rank (SQL RANK)
Max Ties = 2 // ... the group's highest rank
Dense Ties = 3 // groups numbered 1, 2, 3, ... (SQL DENSE_RANK)
)
ValueOf Page
type ValueOf interface {
~uint32 | ~int32 | ~float32 | ~uint64 | ~int64 | ~float64
}
ValueOf are the value types ReduceByKey takes.