README
¶
decundec
Introduction
decundec is a package for the Go programming language that sorts data using a decorate-sort-undecorate idiom to improve performance when the comparison function is time-consuming to compute.
By "decorate-sort-undecorate" we mean that
- a sort key is associated with each data element to be sorted,
- the data are sorted based on those keys, carrying along the original data, and finally,
- the sort keys that were added are stripped, leaving only the sorted elements.
The advantage of decorate-sort-undecorate is that sort keys are computed only once per element, not each time an element is used in a comparison, which typically will be many more than the number of elements. The disadvantages are that additional memory must be allocated to store the decorated slice and that more data must be moved on each element swap.
Usage
decundec replacements are provided for all of the sorting functions in Go's slices package. In all cases, the decundec version takes an extra argument: a function that maps an element to a sort key. User-provided comparison functions are defined in terms of the sort key's type rather than the original element's type.
Performance
As a test of decundec's performance, consider sorting a list of uint16 values in reverse order of their base-10 digits. For example, the list
- 46792
- 25213
- 27803
- 26265
- 33681
should be sorted as
- 33681
- 46792
- 27803
- 25213
- 26265
The following graph plots the speedup of decundec.SortFunc and decundec.SortedFunc over their slices.SortFunc and slices.SortedFunc counterparts as a function of element count:
Speedup is defined as
100\% \cdot \left( \frac{T_\text{slices}}{T_\text{decundec}} - 1 \right)
Hence, bars less than 0% indicate that slices is faster while bars greater than 0% indicate that decundec is faster. Data were gathered by running
go test -bench . -count=11 -timeout 0
and processing the output with benchstat.
The graph illustrates that for this digit-reversal test, slices is faster up to a list length of 32 elements and decundec is faster for all longer lists. decundec's SortFunc runs twice as fast as slices's (100% speedup) while decundec's SortedFunc runs 75% faster than slices's.
Author
Documentation
¶
Overview ¶
Package decundec wraps the sorting functions in Go's slices package to employ a decorate-sort-undecorate idiom. This can improve sorting performance when the comparison function is time-consuming to compute but does require allocating additional memory for the sort keys.
Index ¶
- func Sort[S ~[]E, E any, Ekey cmp.Ordered](x S, key func(E) Ekey)
- func SortFunc[S ~[]E, E, Ekey any](x S, cmp func(a, b Ekey) int, key func(E) Ekey)
- func SortStableFunc[S ~[]E, E, Ekey any](x S, cmp func(a, b Ekey) int, key func(E) Ekey)
- func Sorted[E any, Ekey cmp.Ordered](seq iter.Seq[E], key func(E) Ekey) []E
- func SortedFunc[E any, Ekey cmp.Ordered](seq iter.Seq[E], cmp func(a, b Ekey) int, key func(E) Ekey) []E
- func SortedStableFunc[E any, Ekey cmp.Ordered](seq iter.Seq[E], cmp func(a, b Ekey) int, key func(E) Ekey) []E
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Sort ¶
Sort sorts a slice in ascending order given a function that maps each element to a sort key.
Example ¶
Sort a list of integers by the sum of their base-10 digits.
numbers := []uint{
87138, 33405, 12313, 42691, 33687, 56336, 53757, 89532, 75941, 80650,
}
sumDigits := func(n uint) uint {
var s uint
for ; n > 0; n /= 10 {
s += n % 10
}
return s
}
Sort(numbers, sumDigits)
fmt.Println(numbers)
Output: [12313 33405 80650 42691 56336 75941 87138 33687 53757 89532]
func SortFunc ¶
SortFunc sorts a slice in ascending order as determined by the cmp function and given a function that maps each element to a sort key.
func SortStableFunc ¶
SortStableFunc sorts a slice in ascending order as determined by the cmp function and given a function that maps each element to a sort key. SortStableFunc preserves the original order of elements with equal keys.
Example ¶
Given a list of strings of the form "⟨name⟩_⟨age⟩", sort the list by decreasing age. Preserve the original order of people who are the same age.
people := []string{
"James_18",
"Mary_15",
"Michael_17",
"Patricia_16",
"Robert_15",
"Jennifer_16",
"John_17",
"Linda_18",
}
SortStableFunc(people,
func(a, b uint8) int {
return cmp.Compare(b, a)
},
func(s string) uint8 {
toks := strings.Split(s, "_")
if len(toks) != 2 {
panic("invalid name_age string")
}
age, err := strconv.ParseUint(toks[1], 10, 8)
if err != nil {
panic("invalid name_age string")
}
return uint8(age)
})
for _, s := range people {
fmt.Println(s)
}
Output: James_18 Linda_18 Michael_17 John_17 Patricia_16 Jennifer_16 Mary_15 Robert_15
func Sorted ¶
Sorted takes a slice and a function that maps each element to a sort key and returns a new, sorted slice.
Example ¶
Sort a sequence of float64 values in increasing order of their cosine.
seq := func(yield func(x float64) bool) {
v := 0.0
for range 25 {
if !yield(v) {
return
}
v += 0.75
}
}
sorted := Sorted(seq,
func(x float64) float64 { return math.Cos(x) })
fmt.Println(sorted)
Output: [15.75 3 9.75 9 3.75 15 16.5 2.25 10.5 8.25 4.5 14.25 17.25 1.5 11.25 7.5 5.25 13.5 18 0.75 12 6.75 6 12.75 0]
func SortedFunc ¶
func SortedFunc[E any, Ekey cmp.Ordered](seq iter.Seq[E], cmp func(a, b Ekey) int, key func(E) Ekey) []E
SortedFunc takes a slice, a key-comparison function, and a function that maps each element to a sort key; it returns a new, sorted slice.
func SortedStableFunc ¶
func SortedStableFunc[E any, Ekey cmp.Ordered](seq iter.Seq[E], cmp func(a, b Ekey) int, key func(E) Ekey) []E
SortedStableFunc takes a slice, a key-comparison function, and a function that maps each element to a sort key; it returns a new, sorted slice. SortedStableFunc preserves the original order of elements with equal keys.
Types ¶
This section is empty.
Source Files