README
¶
Fast generic sort for slices in golang
This package is based on the slices package in go standard library since v1.21, but has different apis for search and sort.
API for builtin types
func BinarySearch[E constraints.Ordered](list []E, x E) (int, bool)
func IsSorted[E constraints.Ordered](list []E) bool
func Min[E cmp.Ordered](list []E) E
func Max[E cmp.Ordered](list []E) E
func Sort[E constraints.Ordered](list []E)
func SortStable[E constraints.Ordered](list []E)
API for custom types
type Order[E any] struct {
Less func(a, b E) bool
RefLess func(a, b *E) bool
}
func (od *Order[E]) BinarySearch(list []E, x E) (int, bool)
func (od *Order[E]) IsSorted(list []E) bool
func (od *Order[E]) Min(list []E) E
func (od *Order[E]) Max(list []E) E
func (od *Order[E]) Sort(list []E)
func (od *Order[E]) SortStable(list []E)
func (od *Order[E]) SortWithOption(list []E, stable, inplace bool)
Benchmark Result
On Xeon-8374C (X86-64)
name std time/op new time/op delta
Int/Small-1K 27.7µs ± 2% 24.1µs ± 3% -12.92% (p=0.008 n=5+5)
Int/Small-10K 315µs ± 0% 249µs ± 0% -20.96% (p=0.008 n=5+5)
Int/Small-100K 3.76ms ± 0% 2.86ms ± 0% -24.06% (p=0.008 n=5+5)
Int/Small-1M 44.6ms ± 0% 35.4ms ± 0% -20.57% (p=0.008 n=5+5)
Int/Random-1K 48.4µs ± 1% 38.8µs ± 1% -19.69% (p=0.008 n=5+5)
Int/Random-10K 614µs ± 1% 464µs ± 0% -24.44% (p=0.008 n=5+5)
Int/Random-100K 7.58ms ± 0% 5.61ms ± 0% -26.07% (p=0.008 n=5+5)
Int/Random-1M 90.3ms ± 1% 65.8ms ± 0% -27.08% (p=0.008 n=5+5)
Int/Constant-1K 1.33µs ± 1% 0.93µs ± 1% -30.13% (p=0.008 n=5+5)
Int/Constant-10K 11.1µs ± 4% 8.0µs ± 2% -27.36% (p=0.008 n=5+5)
Int/Constant-100K 98.0µs ± 5% 67.0µs ± 2% -31.61% (p=0.008 n=5+5)
Int/Constant-1M 932µs ± 1% 646µs ± 0% -30.72% (p=0.008 n=5+5)
Int/Ascent-1K 1.33µs ± 1% 0.93µs ± 1% -30.03% (p=0.008 n=5+5)
Int/Ascent-10K 10.8µs ± 3% 8.0µs ± 3% -26.21% (p=0.008 n=5+5)
Int/Ascent-100K 99.1µs ± 5% 66.2µs ± 1% -33.20% (p=0.008 n=5+5)
Int/Ascent-1M 926µs ± 0% 646µs ± 0% -30.19% (p=0.008 n=5+5)
Int/Descent-1K 1.85µs ± 1% 1.46µs ± 0% -21.19% (p=0.008 n=5+5)
Int/Descent-10K 14.8µs ± 3% 12.0µs ± 6% -18.43% (p=0.008 n=5+5)
Int/Descent-100K 132µs ± 1% 104µs ± 2% -21.46% (p=0.008 n=5+5)
Int/Descent-1M 1.32ms ± 0% 1.04ms ± 1% -21.37% (p=0.008 n=5+5)
Int/Mixed-1K 19.9µs ± 3% 17.1µs ± 3% -13.87% (p=0.008 n=5+5)
Int/Mixed-10K 219µs ± 1% 231µs ± 0% +5.53% (p=0.008 n=5+5)
Int/Mixed-100K 2.54ms ± 0% 2.55ms ± 0% ~ (p=0.310 n=5+5)
Int/Mixed-1M 29.5ms ± 0% 28.0ms ± 0% -5.11% (p=0.008 n=5+5)
Hybrid/5%-4 4.09ms ± 0% 3.06ms ± 0% -25.07% (p=0.008 n=5+5)
Hybrid/10% 7.12ms ± 0% 5.33ms ± 0% -25.04% (p=0.008 n=5+5)
Hybrid/20% 13.1ms ± 0% 9.9ms ± 0% -24.73% (p=0.008 n=5+5)
Hybrid/30% 19.2ms ± 1% 14.4ms ± 0% -25.00% (p=0.008 n=5+5)
Hybrid/50% 31.2ms ± 1% 23.5ms ± 0% -24.70% (p=0.008 n=5+5)
Float/1K 58.2µs ± 2% 48.6µs ± 1% -16.58% (p=0.008 n=5+5)
Float/10K 751µs ± 0% 549µs ± 0% -26.80% (p=0.008 n=5+5)
Float/100K 9.28ms ± 0% 6.41ms ± 0% -30.91% (p=0.008 n=5+5)
Float/1M 110ms ± 0% 73ms ± 0% -33.44% (p=0.008 n=5+5)
Str/1K 130µs ± 0% 125µs ± 0% -4.00% (p=0.008 n=5+5)
Str/10K 1.69ms ± 0% 1.64ms ± 0% -2.73% (p=0.008 n=5+5)
Str/100K 21.6ms ± 1% 21.1ms ± 1% -2.41% (p=0.008 n=5+5)
Str/1M 272ms ± 1% 269ms ± 2% ~ (p=0.095 n=5+5)
Struct/1K 104µs ± 1% 86µs ± 0% -17.34% (p=0.008 n=5+5)
Struct/10K 1.36ms ± 0% 1.07ms ± 0% -20.93% (p=0.008 n=5+5)
Struct/100K 16.8ms ± 0% 13.0ms ± 0% -22.48% (p=0.008 n=5+5)
Struct/1M 201ms ± 0% 152ms ± 0% -24.21% (p=0.008 n=5+5)
Stable/1K 183µs ± 1% 84µs ± 0% -53.88% (p=0.008 n=5+5)
Stable/10K 2.71ms ± 0% 1.14ms ± 0% -58.16% (p=0.008 n=5+5)
Stable/100K 37.9ms ± 0% 17.4ms ± 0% -54.15% (p=0.016 n=5+4)
Stable/1M 498ms ± 1% 175ms ± 1% -64.74% (p=0.008 n=5+5)
Pointer/1K 78.7µs ± 1% 66.1µs ± 1% -15.96% (p=0.008 n=5+5)
Pointer/10K 1.05ms ± 0% 0.90ms ± 0% -14.87% (p=0.008 n=5+5)
Pointer/100K 14.0ms ± 0% 12.1ms ± 0% -13.52% (p=0.008 n=5+5)
Pointer/1M 171ms ± 0% 159ms ± 0% -6.82% (p=0.008 n=5+5)
On Yitian-710 (ARM64)
name std time/op new time/op delta
Int/Small-1K 21.4µs ± 0% 17.4µs ± 0% -18.95% (p=0.008 n=5+5)
Int/Small-10K 253µs ± 0% 207µs ± 0% -18.18% (p=0.008 n=5+5)
Int/Small-100K 3.02ms ± 0% 2.47ms ± 0% -18.42% (p=0.008 n=5+5)
Int/Small-1M 35.7ms ± 0% 28.8ms ± 0% -19.54% (p=0.008 n=5+5)
Int/Random-1K 37.7µs ± 0% 27.6µs ± 0% -26.84% (p=0.008 n=5+5)
Int/Random-10K 492µs ± 0% 362µs ± 0% -26.46% (p=0.008 n=5+5)
Int/Random-100K 6.09ms ± 0% 4.51ms ± 0% -25.96% (p=0.008 n=5+5)
Int/Random-1M 72.5ms ± 0% 53.9ms ± 0% -25.69% (p=0.008 n=5+5)
Int/Constant-1K 1.08µs ± 1% 0.70µs ± 0% -35.23% (p=0.016 n=5+4)
Int/Constant-10K 9.60µs ± 0% 6.55µs ± 0% -31.77% (p=0.008 n=5+5)
Int/Constant-100K 93.1µs ± 0% 63.5µs ± 1% -31.78% (p=0.008 n=5+5)
Int/Constant-1M 929µs ± 0% 640µs ± 1% -31.09% (p=0.008 n=5+5)
Int/Ascent-1K 1.08µs ± 1% 0.71µs ± 4% -34.36% (p=0.008 n=5+5)
Int/Ascent-10K 9.61µs ± 0% 6.57µs ± 0% -31.57% (p=0.008 n=5+5)
Int/Ascent-100K 93.1µs ± 0% 63.1µs ± 0% -32.20% (p=0.008 n=5+5)
Int/Ascent-1M 929µs ± 0% 639µs ± 1% -31.27% (p=0.008 n=5+5)
Int/Descent-1K 1.45µs ± 0% 1.07µs ± 1% -26.66% (p=0.008 n=5+5)
Int/Descent-10K 13.2µs ± 0% 9.9µs ± 0% -25.07% (p=0.016 n=5+4)
Int/Descent-100K 130µs ± 0% 100µs ± 0% -23.09% (p=0.008 n=5+5)
Int/Descent-1M 1.30ms ± 0% 1.02ms ± 1% -22.02% (p=0.008 n=5+5)
Int/Mixed-1K 16.3µs ± 4% 12.1µs ± 0% -25.65% (p=0.008 n=5+5)
Int/Mixed-10K 187µs ± 0% 150µs ± 0% -19.82% (p=0.008 n=5+5)
Int/Mixed-100K 2.20ms ± 0% 1.77ms ± 0% -19.24% (p=0.008 n=5+5)
Int/Mixed-1M 25.3ms ± 0% 20.5ms ± 0% -19.21% (p=0.008 n=5+5)
Hybrid/5% 3.50ms ± 0% 2.59ms ± 0% -26.14% (p=0.008 n=5+5)
Hybrid/10% 5.92ms ± 0% 4.36ms ± 0% -26.33% (p=0.008 n=5+5)
Hybrid/20% 10.8ms ± 0% 7.9ms ± 0% -26.48% (p=0.008 n=5+5)
Hybrid/30% 15.6ms ± 0% 11.5ms ± 0% -26.43% (p=0.008 n=5+5)
Hybrid/50% 25.3ms ± 0% 18.6ms ± 0% -26.49% (p=0.008 n=5+5)
Float/1K 46.1µs ± 0% 35.6µs ± 0% -22.75% (p=0.008 n=5+5)
Float/10K 606µs ± 0% 467µs ± 0% -22.85% (p=0.008 n=5+5)
Float/100K 7.51ms ± 0% 5.79ms ± 0% -22.83% (p=0.008 n=5+5)
Float/1M 89.5ms ± 0% 69.0ms ± 0% -22.84% (p=0.008 n=5+5)
Str/1K 124µs ± 0% 119µs ± 0% -4.40% (p=0.008 n=5+5)
Str/10K 1.54ms ± 0% 1.48ms ± 0% -3.70% (p=0.008 n=5+5)
Str/100K 20.1ms ± 1% 19.6ms ± 0% -2.37% (p=0.008 n=5+5)
Str/1M 290ms ± 1% 286ms ± 1% -1.10% (p=0.032 n=5+5)
Struct/1K 100µs ± 0% 85µs ± 0% -14.55% (p=0.008 n=5+5)
Struct/10K 1.32ms ± 0% 1.07ms ± 0% -19.19% (p=0.008 n=5+5)
Struct/100K 16.4ms ± 0% 12.7ms ± 0% -22.38% (p=0.008 n=5+5)
Struct/1M 196ms ± 0% 141ms ± 2% -28.06% (p=0.008 n=5+5)
Stable/1K 186µs ± 0% 73µs ± 0% -60.49% (p=0.008 n=5+5)
Stable/10K 2.84ms ± 0% 1.22ms ± 0% -57.16% (p=0.008 n=5+5)
Stable/100K 40.5ms ± 0% 14.7ms ± 0% -63.75% (p=0.008 n=5+5)
Stable/1M 534ms ± 0% 163ms ± 0% -69.43% (p=0.016 n=5+4)
Pointer/1K 63.7µs ± 0% 55.3µs ± 0% -13.18% (p=0.008 n=5+5)
Pointer/10K 873µs ± 0% 775µs ± 1% -11.23% (p=0.008 n=5+5)
Pointer/100K 12.4ms ± 0% 11.3ms ± 0% -9.58% (p=0.008 n=5+5)
Pointer/1M 159ms ± 0% 147ms ± 0% -7.59% (p=0.008 n=5+5)
Documentation
¶
Overview ¶
Package slices defines various functions useful with slices of any type.
Index ¶
- func BinarySearch[E cmp.Ordered](x []E, target E) (int, bool)
- func Clip[S ~[]E, E any](s S) S
- func Clone[S ~[]E, E any](s S) S
- func Compact[S ~[]E, E comparable](s S) S
- func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S
- func Compare[S ~[]E, E cmp.Ordered](s1, s2 S) int
- func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int
- func Contains[S ~[]E, E comparable](s S, v E) bool
- func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool
- func Delete[S ~[]E, E any](s S, i, j int) S
- func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S
- func Equal[S ~[]E, E comparable](s1, s2 S) bool
- func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool
- func Grow[S ~[]E, E any](s S, n int) S
- func Index[S ~[]E, E comparable](s S, v E) int
- func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int
- func Insert[S ~[]E, E any](s S, i int, v ...E) S
- func IsSorted[E cmp.Ordered](list []E) bool
- func Max[E cmp.Ordered](list []E) E
- func Min[E cmp.Ordered](list []E) E
- func Replace[S ~[]E, E any](s S, i, j int, v ...E) S
- func Reverse[S ~[]E, E any](s S)
- func Sort[E cmp.Ordered](list []E)
- func SortStable[E cmp.Ordered](list []E)
- type Order
- func (od *Order[E]) BinarySearch(list []E, target E) (int, bool)
- func (od *Order[E]) IsSorted(list []E) bool
- func (od *Order[E]) Max(list []E) E
- func (od *Order[E]) Min(list []E) E
- func (od *Order[E]) Sort(list []E)
- func (od *Order[E]) SortStable(list []E)
- func (od *Order[E]) SortWithOption(list []E, stable, inplace bool)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
BinarySearch searches for target in a sorted slice and returns the position where target is found, or the position where target would appear in the sort order; it also returns a bool saying whether the target is really found in the slice. The slice must be sorted in increasing order.
func Clip ¶
func Clip[S ~[]E, E any](s S) S
Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
func Clone ¶
func Clone[S ~[]E, E any](s S) S
Clone returns a copy of the slice. The elements are copied using assignment, so this is a shallow clone.
func Compact ¶
func Compact[S ~[]E, E comparable](s S) S
Compact replaces consecutive runs of equal elements with a single copy. This is like the uniq command found on Unix. Compact modifies the contents of the slice s; it does not create a new slice. When Compact discards m elements in total, it might not modify the elements s[len(s)-m:len(s)]. If those elements contain pointers you might consider zeroing those elements so that objects they reference can be garbage collected.
func CompactFunc ¶
CompactFunc is like Compact but uses a comparison function.
func Compare ¶
Compare compares the elements of s1 and s2, using cmp.Compare on each pair of elements. The elements are compared sequentially, starting at index 0, until one element is not equal to the other. The result of comparing the first non-matching elements is returned. If both slices are equal until one of them ends, the shorter slice is considered less than the longer one. The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.
func CompareFunc ¶
CompareFunc is like Compare but uses a custom comparison function on each pair of elements. The result is the first non-zero result of cmp; if cmp always returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), and +1 if len(s1) > len(s2).
func Contains ¶
func Contains[S ~[]E, E comparable](s S, v E) bool
Contains reports whether v is present in s.
func ContainsFunc ¶
ContainsFunc reports whether at least one element e of s satisfies f(e).
func Delete ¶
Delete removes the elements s[i:j] from s, returning the modified slice. Delete panics if s[i:j] is not a valid slice of s. Delete modifies the contents of the slice s; it does not create a new slice. Delete is O(len(s)-j), so if many items must be deleted, it is better to make a single call deleting them all together than to delete one at a time. Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those elements contain pointers you might consider zeroing those elements so that objects they reference can be garbage collected.
func DeleteFunc ¶
DeleteFunc removes any elements from s for which del returns true, returning the modified slice. DeleteFunc modifies the contents of the slice s; it does not create a new slice. When DeleteFunc removes m elements, it might not modify the elements s[len(s)-m:len(s)]. If those elements contain pointers you might consider zeroing those elements so that objects they reference can be garbage collected.
func Equal ¶
func Equal[S ~[]E, E comparable](s1, s2 S) bool
Equal reports whether two slices are equal: the same length and all elements equal. If the lengths are different, Equal returns false. Otherwise, the elements are compared in increasing index order, and the comparison stops at the first unequal pair. Floating point NaNs are not considered equal.
func EqualFunc ¶
EqualFunc reports whether two slices are equal using a comparison function on each pair of elements. If the lengths are different, EqualFunc returns false. Otherwise, the elements are compared in increasing index order, and the comparison stops at the first index for which eq returns false.
func Grow ¶
Grow increases the slice's capacity, if necessary, to guarantee space for another n elements. After Grow(n), at least n elements can be appended to the slice without another allocation. If n is negative or too large to allocate the memory, Grow panics.
func Index ¶
func Index[S ~[]E, E comparable](s S, v E) int
Index returns the index of the first occurrence of v in s, or -1 if not present.
func Insert ¶
Insert inserts the values v... into s at index i, returning the modified slice. The elements at s[i:] are shifted up to make room. In the returned slice r, r[i] == v[0], and r[i+len(v)] == value originally at r[i]. Insert panics if i is out of range. This function is O(len(s) + len(v)).
func Max ¶
Max returns the maximal value in x. It panics if x is empty. For floating-point E, Max propagates NaNs (any NaN value in x forces the output to be NaN).
func Min ¶
Min returns the minimal value in x. It panics if x is empty. For floating-point numbers, Min propagates NaNs (any NaN value in x forces the output to be NaN).
func Replace ¶
Replace replaces the elements s[i:j] by the given v, and returns the modified slice. Replace panics if s[i:j] is not a valid slice of s.
func Reverse ¶
func Reverse[S ~[]E, E any](s S)
Reverse reverses the elements of the slice in place.
func Sort ¶
Sort sorts a slice of any ordered type in ascending order. When sorting floating-point numbers, NaNs are ordered before other values.
func SortStable ¶
SortStableFunc sorts the slice x while keeping the original order of equal elements, using cmp to compare elements.
Types ¶
type Order ¶
Order record the way of comparison, will never changed by its methods.
.Less is a comparison function with value input. .RefLess is a comparison function with pointer input. At least one of them should be set before use. If both of them are set, they must have the same behavior.
func (*Order[E]) BinarySearch ¶
The general version of BinarySearch.
func (*Order[E]) Sort ¶
func (od *Order[E]) Sort(list []E)
The general version of Sort. It tends to use faster algorithm with extra memory.
func (*Order[E]) SortStable ¶
func (od *Order[E]) SortStable(list []E)
The general version of SortStable. It tends to use faster algorithm with extra memory.
func (*Order[E]) SortWithOption ¶
The general sort function. Guarantee stability when stable flag is set. Avoid allocating O(n) size extra memory when inplace flag is set.
Source Files