README
¶
kth: High-Performance Selection Algorithms for Go
kth provides high-performance selection algorithms that find the k-th smallest element without sorting the entire dataset. It's especially useful for operations like finding top-N elements or medians in large datasets.
Features
- Algorithms for Different Needs:
- FloydRivest: Fastest for random data distributions
- PDQSelect: Most consistent across all data patterns
- Speed: Both significantly outperform sort-based selection, with up to 99% improvement in common cases
- Memory Efficient: All operations are in-place, requiring no additional memory
- Production Ready: Battle-tested and fuzzed implementations that work with any ordered type
Installation
go get github.com/tsenart/kth
Usage
The library provides three ways to use each algorithm, depending on your data type:
// 1. For types implementing sort.Interface
func PDQSelect(data sort.Interface, k int)
func FloydRivest(data sort.Interface, k int)
// 2. For slices of ordered types
func PDQSelectOrdered[T cmp.Ordered](data []T, k int)
func FloydRivestOrdered[T cmp.Ordered](data []T, k int)
// 3. For custom comparison functions
func PDQSelectFunc[E any](data []E, k int, less func(a, b E) bool)
func FloydRivestFunc[E any](data []E, k int, less func(a, b E) bool)
Examples
- Using with
sort.Interface:
type Ints []int
func (x Ints) Len() int { return len(x) }
func (x Ints) Less(i, j int) bool { return x[i] < x[j] }
func (x Ints) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
data := Ints{7, 4, 9, 1, 3, 8, 2, 6, 5}
FloydRivest(data, 3) // Find 3rd smallest
// data is now partitioned with the 3rd element (3) in position
// [1 2 3 | 7 4 9 8 6 5] (elements around 3 may not be sorted)
- Using with
cmp.Orderedtypes:
scores := []float64{89.7, 95.3, 78.4, 92.1, 88.9}
PDQSelectOrdered(scores, len(scores)/2) // Find median
// scores now has median at middle position
- Using with custom comparison:
type User struct {
Name string
Age int
}
users := []User{
{"Alice", 25},
{"Bob", 30},
{"Charlie", 20},
}
// Find youngest 2 users
PDQSelectFunc(users, 2, func(a, b User) bool {
return a.Age < b.Age
})
Benchmarks
goos: darwin
goarch: arm64
pkg: github.com/tsenart/kth
cpu: Apple M3 Max
│ PDQSortOrdered │ PDQSelectOrdered │ FloydRivestSelectOrdered │
│ sec/op │ sec/op vs base │ sec/op vs base │
Select/n=10000000/k=1/dist=uniform/order=random-16 659.651m ± 0% 6.817m ± 1% -98.97% (p=0.000 n=15) 4.145m ± 1% -99.37% (p=0.000 n=15)
Select/n=10000000/k=1/dist=uniform/order=sorted-16 6.928m ± 1% 6.757m ± 0% -2.47% (p=0.000 n=15) 4.119m ± 0% -40.54% (p=0.000 n=15)
Select/n=10000000/k=1/dist=uniform/order=reversed-16 9.155m ± 1% 6.851m ± 1% -25.17% (p=0.000 n=15) 9.440m ± 1% +3.12% (p=0.000 n=15)
Select/n=10000000/k=1/dist=uniform/order=mostly_sorted-16 241.363m ± 0% 6.875m ± 2% -97.15% (p=0.000 n=15) 4.123m ± 0% -98.29% (p=0.000 n=15)
Select/n=10000000/k=1/dist=uniform/order=push_front-16 14.211m ± 0% 6.887m ± 1% -51.54% (p=0.000 n=15) 4.131m ± 1% -70.93% (p=0.000 n=15)
Select/n=10000000/k=1/dist=uniform/order=push_middle-16 10.610m ± 1% 6.892m ± 0% -35.04% (p=0.000 n=15) 4.123m ± 0% -61.14% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=random-16 659.398m ± 0% 6.766m ± 1% -98.97% (p=0.000 n=15) 4.208m ± 0% -99.36% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=sorted-16 7.095m ± 1% 6.854m ± 1% -3.39% (p=0.000 n=15) 4.105m ± 2% -42.15% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=reversed-16 22.861m ± 1% 25.139m ± 0% +9.97% (p=0.000 n=15) 9.512m ± 1% -58.39% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=mostly_sorted-16 248.027m ± 1% 6.775m ± 2% -97.27% (p=0.000 n=15) 4.108m ± 0% -98.34% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=push_front-16 14.022m ± 0% 6.753m ± 0% -51.84% (p=0.000 n=15) 4.098m ± 0% -70.77% (p=0.000 n=15)
Select/n=10000000/k=1/dist=normal/order=push_middle-16 8.897m ± 2% 6.318m ± 0% -28.99% (p=0.000 n=15) 3.843m ± 1% -56.80% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=random-16 120.732m ± 1% 6.744m ± 3% -94.41% (p=0.000 n=15) 23.277m ± 2% -80.72% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=sorted-16 6.950m ± 2% 6.782m ± 0% -2.42% (p=0.000 n=15) 7.519m ± 1% +8.18% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=reversed-16 21.812m ± 0% 6.849m ± 0% -68.60% (p=0.000 n=15) 15.954m ± 1% -26.86% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=mostly_sorted-16 49.029m ± 0% 6.772m ± 1% -86.19% (p=0.000 n=15) 11.284m ± 1% -76.99% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=push_front-16 10.007m ± 2% 6.766m ± 1% -32.39% (p=0.000 n=15) 7.491m ± 1% -25.14% (p=0.000 n=15)
Select/n=10000000/k=1/dist=zipf/order=push_middle-16 9.195m ± 1% 6.747m ± 0% -26.62% (p=0.000 n=15) 7.616m ± 1% -17.17% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=random-16 7.216m ± 1% 6.822m ± 1% -5.46% (p=0.000 n=15) 12.506m ± 2% +73.32% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=sorted-16 6.993m ± 1% 6.812m ± 1% -2.60% (p=0.000 n=15) 12.497m ± 0% +78.69% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=reversed-16 6.968m ± 0% 6.790m ± 0% -2.56% (p=0.000 n=15) 12.476m ± 1% +79.05% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=mostly_sorted-16 6.994m ± 1% 6.771m ± 2% -3.19% (p=0.000 n=15) 12.499m ± 2% +78.70% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=push_front-16 6.981m ± 1% 6.750m ± 0% -3.31% (p=0.000 n=15) 12.446m ± 0% +78.27% (p=0.000 n=15)
Select/n=10000000/k=1/dist=constant/order=push_middle-16 6.931m ± 2% 6.751m ± 1% -2.59% (p=0.000 n=15) 12.543m ± 1% +80.97% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=random-16 650.814m ± 0% 6.835m ± 0% -98.95% (p=0.000 n=15) 4.116m ± 1% -99.37% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=sorted-16 7.036m ± 0% 6.813m ± 1% -3.17% (p=0.003 n=15) 4.133m ± 0% -41.26% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=reversed-16 21.472m ± 0% 25.146m ± 0% +17.11% (p=0.000 n=15) 9.375m ± 0% -56.34% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=mostly_sorted-16 245.840m ± 0% 6.740m ± 0% -97.26% (p=0.000 n=15) 4.089m ± 1% -98.34% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=push_front-16 13.970m ± 0% 6.749m ± 0% -51.69% (p=0.000 n=15) 4.108m ± 0% -70.60% (p=0.000 n=15)
Select/n=10000000/k=1/dist=bimodal/order=push_middle-16 9.349m ± 0% 6.755m ± 0% -27.75% (p=0.000 n=15) 4.098m ± 0% -56.17% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=random-16 656.304m ± 0% 45.236m ± 0% -93.11% (p=0.000 n=15) 4.561m ± 1% -99.31% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=sorted-16 6.905m ± 0% 6.909m ± 1% ~ (p=0.935 n=15) 4.098m ± 0% -40.65% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=reversed-16 9.121m ± 0% 9.110m ± 0% ~ (p=0.305 n=15) 9.389m ± 0% +2.94% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=mostly_sorted-16 240.205m ± 0% 19.080m ± 0% -92.06% (p=0.000 n=15) 4.097m ± 1% -98.29% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=push_front-16 13.934m ± 0% 13.918m ± 0% ~ (p=0.148 n=15) 4.095m ± 0% -70.61% (p=0.000 n=15)
Select/n=10000000/k=100/dist=uniform/order=push_middle-16 10.439m ± 1% 10.392m ± 0% ~ (p=0.217 n=15) 4.096m ± 0% -60.76% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=random-16 658.613m ± 0% 54.247m ± 0% -91.76% (p=0.000 n=15) 4.656m ± 0% -99.29% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=sorted-16 6.929m ± 0% 6.917m ± 0% ~ (p=0.325 n=15) 4.082m ± 0% -41.09% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=reversed-16 22.587m ± 0% 12.884m ± 0% -42.96% (p=0.000 n=15) 9.396m ± 0% -58.40% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=mostly_sorted-16 245.850m ± 0% 19.411m ± 0% -92.10% (p=0.000 n=15) 4.113m ± 0% -98.33% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=push_front-16 13.927m ± 0% 13.920m ± 0% ~ (p=0.345 n=15) 4.091m ± 0% -70.63% (p=0.000 n=15)
Select/n=10000000/k=100/dist=normal/order=push_middle-16 9.289m ± 0% 9.296m ± 0% ~ (p=0.061 n=15) 4.068m ± 1% -56.20% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=random-16 132.35m ± 0% 30.71m ± 0% -76.79% (p=0.000 n=15) 24.11m ± 0% -81.78% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=sorted-16 6.879m ± 0% 6.903m ± 0% +0.35% (p=0.005 n=15) 7.478m ± 0% +8.70% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=reversed-16 21.67m ± 0% 11.02m ± 0% -49.15% (p=0.000 n=15) 15.97m ± 0% -26.29% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=mostly_sorted-16 48.88m ± 0% 13.74m ± 0% -71.90% (p=0.000 n=15) 11.27m ± 0% -76.94% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=push_front-16 9.761m ± 1% 9.723m ± 1% ~ (p=0.595 n=15) 7.475m ± 0% -23.42% (p=0.000 n=15)
Select/n=10000000/k=100/dist=zipf/order=push_middle-16 9.098m ± 1% 9.091m ± 1% ~ (p=0.806 n=15) 7.474m ± 0% -17.85% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=random-16 6.924m ± 0% 6.931m ± 0% ~ (p=0.512 n=15) 12.375m ± 0% +78.73% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=sorted-16 6.932m ± 0% 6.934m ± 0% ~ (p=0.935 n=15) 12.383m ± 0% +78.65% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=reversed-16 6.934m ± 0% 6.926m ± 0% ~ (p=0.050 n=15) 12.376m ± 0% +78.47% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=mostly_sorted-16 6.927m ± 0% 6.925m ± 0% ~ (p=0.967 n=15) 12.367m ± 0% +78.54% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=push_front-16 6.924m ± 0% 6.934m ± 0% ~ (p=0.126 n=15) 12.375m ± 0% +78.72% (p=0.000 n=15)
Select/n=10000000/k=100/dist=constant/order=push_middle-16 6.912m ± 0% 6.929m ± 0% ~ (p=0.106 n=15) 12.386m ± 0% +79.20% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=random-16 663.006m ± 0% 61.886m ± 1% -90.67% (p=0.000 n=15) 4.626m ± 1% -99.30% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=sorted-16 6.931m ± 0% 6.949m ± 0% ~ (p=0.161 n=15) 4.105m ± 1% -40.78% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=reversed-16 21.726m ± 0% 13.001m ± 0% -40.16% (p=0.000 n=15) 9.441m ± 1% -56.54% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=mostly_sorted-16 247.029m ± 0% 19.339m ± 1% -92.17% (p=0.000 n=15) 4.126m ± 2% -98.33% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=push_front-16 14.231m ± 1% 14.033m ± 1% -1.39% (p=0.002 n=15) 4.120m ± 0% -71.05% (p=0.000 n=15)
Select/n=10000000/k=100/dist=bimodal/order=push_middle-16 9.383m ± 2% 9.476m ± 1% ~ (p=0.325 n=15) 4.129m ± 1% -55.99% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=random-16 659.06m ± 1% 67.93m ± 0% -89.69% (p=0.000 n=15) 34.63m ± 0% -94.74% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=sorted-16 6.924m ± 0% 6.923m ± 0% ~ (p=0.624 n=15) 5.130m ± 0% -25.91% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=reversed-16 9.143m ± 0% 9.154m ± 0% ~ (p=0.174 n=15) 11.192m ± 0% +22.41% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=mostly_sorted-16 240.69m ± 0% 19.27m ± 0% -91.99% (p=0.000 n=15) 11.60m ± 0% -95.18% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=push_front-16 11.832m ± 0% 11.773m ± 0% -0.50% (p=0.000 n=15) 8.056m ± 0% -31.91% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=uniform/order=push_middle-16 10.471m ± 0% 10.467m ± 0% ~ (p=0.345 n=15) 5.180m ± 1% -50.53% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=random-16 647.88m ± 0% 42.67m ± 0% -93.41% (p=0.000 n=15) 34.56m ± 0% -94.67% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=sorted-16 6.940m ± 0% 6.919m ± 1% ~ (p=0.106 n=15) 6.788m ± 0% -2.18% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=reversed-16 23.41m ± 0% 12.57m ± 0% -46.30% (p=0.000 n=15) 12.58m ± 0% -46.25% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=mostly_sorted-16 245.94m ± 0% 19.31m ± 0% -92.15% (p=0.000 n=15) 12.83m ± 0% -94.78% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=push_front-16 14.058m ± 0% 14.031m ± 0% -0.19% (p=0.026 n=15) 5.398m ± 0% -61.60% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=normal/order=push_middle-16 9.331m ± 0% 9.336m ± 0% ~ (p=0.744 n=15) 5.213m ± 0% -44.13% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=random-16 133.99m ± 0% 54.72m ± 0% -59.16% (p=0.000 n=15) 40.84m ± 1% -69.52% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=sorted-16 6.929m ± 0% 6.923m ± 0% ~ (p=0.461 n=15) 8.838m ± 0% +27.55% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=reversed-16 21.92m ± 0% 11.56m ± 0% -47.24% (p=0.000 n=15) 10.25m ± 0% -53.25% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=mostly_sorted-16 48.89m ± 0% 18.57m ± 0% -62.02% (p=0.000 n=15) 16.21m ± 0% -66.84% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=push_front-16 9.691m ± 0% 9.677m ± 0% ~ (p=0.325 n=15) 8.742m ± 0% -9.79% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=zipf/order=push_middle-16 9.113m ± 0% 9.074m ± 0% -0.43% (p=0.015 n=15) 8.739m ± 0% -4.10% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=random-16 6.926m ± 0% 6.967m ± 2% +0.59% (p=0.001 n=15) 12.675m ± 0% +83.00% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=sorted-16 7.051m ± 2% 6.949m ± 1% ~ (p=0.174 n=15) 12.602m ± 1% +78.73% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=reversed-16 7.112m ± 1% 7.134m ± 0% ~ (p=0.389 n=15) 12.444m ± 0% +74.98% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=mostly_sorted-16 7.040m ± 2% 7.092m ± 0% +0.74% (p=0.029 n=15) 12.781m ± 1% +81.56% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=push_front-16 7.111m ± 1% 7.061m ± 0% -0.70% (p=0.011 n=15) 12.429m ± 2% +74.78% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=constant/order=push_middle-16 6.976m ± 1% 7.002m ± 1% ~ (p=0.902 n=15) 12.580m ± 1% +80.33% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=random-16 651.88m ± 0% 63.31m ± 0% -90.29% (p=0.000 n=15) 34.74m ± 0% -94.67% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=sorted-16 7.048m ± 1% 7.043m ± 0% ~ (p=0.744 n=15) 5.404m ± 1% -23.33% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=reversed-16 23.51m ± 2% 12.81m ± 0% -45.53% (p=0.000 n=15) 12.72m ± 1% -45.91% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=mostly_sorted-16 248.08m ± 1% 19.42m ± 0% -92.17% (p=0.000 n=15) 11.62m ± 0% -95.32% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=push_front-16 14.150m ± 1% 14.098m ± 0% ~ (p=0.806 n=15) 8.101m ± 0% -42.75% (p=0.000 n=15)
Select/n=10000000/k=5000000/dist=bimodal/order=push_middle-16 9.429m ± 1% 9.536m ± 1% ~ (p=0.161 n=15) 6.887m ± 0% -26.96% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=random-16 659.848m ± 0% 46.110m ± 1% -93.01% (p=0.000 n=15) 6.865m ± 1% -98.96% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=sorted-16 7.080m ± 1% 7.099m ± 1% ~ (p=0.074 n=15) 6.392m ± 3% -9.73% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=reversed-16 9.275m ± 2% 9.287m ± 1% ~ (p=0.838 n=15) 9.452m ± 0% +1.92% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=mostly_sorted-16 241.538m ± 0% 19.124m ± 0% -92.08% (p=0.000 n=15) 6.684m ± 0% -97.23% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=push_front-16 14.261m ± 0% 14.250m ± 1% ~ (p=0.967 n=15) 6.832m ± 1% -52.09% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=uniform/order=push_middle-16 10.710m ± 1% 10.474m ± 0% -2.20% (p=0.000 n=15) 6.709m ± 0% -37.35% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=random-16 660.408m ± 1% 57.425m ± 0% -91.30% (p=0.000 n=15) 6.907m ± 1% -98.95% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=sorted-16 7.152m ± 1% 6.956m ± 0% -2.74% (p=0.000 n=15) 6.416m ± 2% -10.29% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=reversed-16 23.199m ± 0% 12.441m ± 0% -46.37% (p=0.000 n=15) 9.494m ± 0% -59.08% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=mostly_sorted-16 250.625m ± 5% 14.519m ± 1% -94.21% (p=0.000 n=15) 6.742m ± 1% -97.31% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=push_front-16 14.350m ± 1% 14.045m ± 1% -2.13% (p=0.000 n=15) 6.854m ± 1% -52.24% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=normal/order=push_middle-16 9.493m ± 1% 9.556m ± 1% ~ (p=0.202 n=15) 6.813m ± 0% -28.23% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=random-16 133.915m ± 0% 45.148m ± 0% -66.29% (p=0.000 n=15) 6.855m ± 1% -94.88% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=sorted-16 6.945m ± 2% 7.069m ± 1% ~ (p=0.074 n=15) 6.640m ± 1% -4.39% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=reversed-16 21.879m ± 1% 12.750m ± 0% -41.73% (p=0.000 n=15) 9.740m ± 0% -55.48% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=mostly_sorted-16 49.487m ± 0% 21.267m ± 0% -57.03% (p=0.000 n=15) 6.736m ± 1% -86.39% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=push_front-16 9.933m ± 2% 10.049m ± 3% ~ (p=0.512 n=15) 6.720m ± 1% -32.35% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=zipf/order=push_middle-16 9.021m ± 0% 9.412m ± 0% +4.34% (p=0.000 n=15) 6.781m ± 1% -24.83% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=random-16 7.060m ± 2% 7.076m ± 1% ~ (p=0.233 n=15) 12.560m ± 1% +77.89% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=sorted-16 6.992m ± 1% 7.005m ± 1% ~ (p=0.512 n=15) 12.553m ± 1% +79.55% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=reversed-16 7.043m ± 1% 7.061m ± 2% ~ (p=0.486 n=15) 12.429m ± 0% +76.47% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=mostly_sorted-16 6.931m ± 1% 7.016m ± 1% +1.23% (p=0.002 n=15) 12.613m ± 0% +81.98% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=push_front-16 7.051m ± 1% 7.056m ± 0% ~ (p=0.367 n=15) 12.679m ± 0% +79.82% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=constant/order=push_middle-16 6.887m ± 0% 6.917m ± 0% +0.44% (p=0.015 n=15) 12.386m ± 0% +79.85% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=random-16 654.581m ± 0% 41.624m ± 0% -93.64% (p=0.000 n=15) 6.920m ± 0% -98.94% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=sorted-16 7.039m ± 1% 7.059m ± 1% ~ (p=0.187 n=15) 6.493m ± 3% -7.77% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=reversed-16 22.755m ± 1% 12.763m ± 1% -43.91% (p=0.000 n=15) 9.588m ± 1% -57.87% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=mostly_sorted-16 247.710m ± 1% 19.633m ± 1% -92.07% (p=0.000 n=15) 6.727m ± 1% -97.28% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=push_front-16 14.178m ± 0% 14.086m ± 0% -0.65% (p=0.033 n=15) 6.731m ± 0% -52.53% (p=0.000 n=15)
Select/n=10000000/k=9999900/dist=bimodal/order=push_middle-16 9.376m ± 2% 9.521m ± 1% +1.54% (p=0.045 n=15) 6.806m ± 0% -27.41% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=random-16 657.806m ± 1% 46.257m ± 1% -92.97% (p=0.000 n=15) 6.577m ± 1% -99.00% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=sorted-16 7.058m ± 1% 6.942m ± 2% -1.65% (p=0.019 n=15) 6.319m ± 1% -10.47% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=reversed-16 9.277m ± 1% 9.244m ± 1% -0.36% (p=0.033 n=15) 9.470m ± 1% +2.07% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=mostly_sorted-16 244.087m ± 0% 16.881m ± 1% -93.08% (p=0.000 n=15) 6.317m ± 1% -97.41% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=push_front-16 14.132m ± 1% 14.117m ± 1% ~ (p=0.653 n=15) 6.713m ± 1% -52.50% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=uniform/order=push_middle-16 10.498m ± 0% 10.555m ± 1% ~ (p=0.074 n=15) 6.686m ± 0% -36.32% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=random-16 660.338m ± 0% 52.250m ± 0% -92.09% (p=0.000 n=15) 6.581m ± 0% -99.00% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=sorted-16 6.939m ± 0% 6.937m ± 0% ~ (p=0.935 n=15) 6.430m ± 0% -7.33% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=reversed-16 23.444m ± 0% 12.342m ± 0% -47.36% (p=0.000 n=15) 9.494m ± 0% -59.50% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=mostly_sorted-16 245.705m ± 0% 19.720m ± 0% -91.97% (p=0.000 n=15) 6.438m ± 2% -97.38% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=push_front-16 14.026m ± 0% 13.989m ± 0% -0.26% (p=0.029 n=15) 6.718m ± 0% -52.10% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=normal/order=push_middle-16 9.331m ± 1% 9.273m ± 0% -0.62% (p=0.021 n=15) 6.578m ± 1% -29.50% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=random-16 126.208m ± 0% 61.855m ± 0% -50.99% (p=0.000 n=15) 6.204m ± 1% -95.08% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=sorted-16 6.870m ± 0% 6.888m ± 1% ~ (p=0.461 n=15) 6.507m ± 1% -5.29% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=reversed-16 20.413m ± 7% 11.869m ± 0% -41.85% (p=0.000 n=15) 9.060m ± 0% -55.62% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=mostly_sorted-16 46.959m ± 1% 20.379m ± 1% -56.60% (p=0.000 n=15) 6.268m ± 1% -86.65% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=push_front-16 9.062m ± 1% 9.420m ± 1% +3.94% (p=0.000 n=15) 6.252m ± 0% -31.01% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=zipf/order=push_middle-16 9.046m ± 0% 9.013m ± 1% ~ (p=0.116 n=15) 6.572m ± 1% -27.35% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=random-16 6.468m ± 4% 6.627m ± 1% +2.46% (p=0.023 n=15) 12.095m ± 1% +87.00% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=sorted-16 6.838m ± 1% 6.913m ± 0% +1.09% (p=0.000 n=15) 12.349m ± 0% +80.59% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=reversed-16 6.895m ± 0% 6.909m ± 0% ~ (p=0.202 n=15) 12.319m ± 6% +78.66% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=mostly_sorted-16 6.658m ± 2% 6.844m ± 0% +2.79% (p=0.000 n=15) 12.311m ± 0% +84.91% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=push_front-16 6.898m ± 0% 6.908m ± 0% ~ (p=0.325 n=15) 11.704m ± 5% +69.67% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=constant/order=push_middle-16 6.615m ± 1% 6.774m ± 1% +2.40% (p=0.000 n=15) 12.287m ± 0% +85.73% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=random-16 616.328m ± 1% 54.625m ± 0% -91.14% (p=0.000 n=15) 6.206m ± 2% -98.99% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=sorted-16 6.477m ± 1% 6.665m ± 2% +2.90% (p=0.000 n=15) 5.964m ± 1% -7.92% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=reversed-16 22.531m ± 0% 12.493m ± 0% -44.55% (p=0.000 n=15) 9.091m ± 1% -59.65% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=mostly_sorted-16 229.074m ± 0% 18.020m ± 0% -92.13% (p=0.000 n=15) 6.274m ± 0% -97.26% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=push_front-16 13.268m ± 1% 13.443m ± 1% +1.32% (p=0.000 n=15) 6.262m ± 0% -52.80% (p=0.000 n=15)
Select/n=10000000/k=9999999/dist=bimodal/order=push_middle-16 9.269m ± 0% 9.284m ± 0% ~ (p=0.067 n=15) 6.471m ± 1% -30.18% (p=0.000 n=15)
geomean 23.57m 11.24m -52.32% 7.955m -66.24%
Contributing
Contributions are welcome! Please feel free to submit a Pull Request.
License
This project is licensed under the MIT License - see the LICENSE file for details.
Acknowledgments
- Built upon Go's internal
pdqsortalgorithm.
Documentation
¶
Index ¶
- func FloydRivest(data sort.Interface, k int)
- func FloydRivestFunc[E any](data []E, k int, less func(a, b E) bool)
- func FloydRivestOrdered[T cmp.Ordered](data []T, k int)
- func PDQSelect(data sort.Interface, k int)
- func PDQSelectFunc[E any](data []E, k int, less func(i, j E) bool)
- func PDQSelectOrdered[T cmp.Ordered](data []T, k int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FloydRivest ¶
FloydRivest implements the Floyd-Rivest selection algorithm to find the k-th smallest elements. It typically makes fewer comparisons than other selection algorithms by narrowing the search range based on order statistics estimates before partitioning.
func FloydRivestFunc ¶
FloydRivestFunc is a generic version of FloydRivest that allows the caller to provide a custom comparison function to determine the order of elements.
func FloydRivestOrdered ¶
FloydRivestOrdered is a specialized version of FloydRivest that works with slices of ordered types (i.e. types that implement the cmp.Ordered interface).
func PDQSelect ¶
PDQSelect swaps elements in the data provided so that the first k elements (i.e. the elements occuping indices 0, 1, ..., k-1) are the smallest k elements in the data. It doesn't guarantee any particular order among the smallest k elements, only that they are the smallest k elements in the data.
PDQSelect implements Hoare's Selection Algorithm and runs in O(n) time, so it is asymptotically faster than sorting or other heap-like implementations for finding the smallest k elements in a data structure.
It's an adaptation of Go's internal pdqsort implementation, which makes it adaptive to bad data patterns like already sorted data, duplicate elements, and more.
func PDQSelectFunc ¶
PDQSelectFunc is a generic version of Select that allows the caller to provide a custom comparison function to determine the order of elements.
func PDQSelectOrdered ¶
PDQSelectOrdered is a specialized version of Select that works with slices of ordered types (i.e. types that implement the cmp.Ordered interface).
Types ¶
This section is empty.
Source Files
Click to show internal directories.
Click to hide internal directories.