README
¶
QuickSelect
QuickSelect is a Go package which provides primitives for finding the smallest k elements in slices and user-defined collections. The primitives used in the package are modeled off of the standard sort library for Go. Quickselect uses Hoare's Selection Algorithm which finds the smallest k elements in expected O(n) time, and is thus an asymptotically optimal algorithm (and is faster than sorting or heap implementations). QuickSelect is also faster than just Hoare's Selection Algorithm alone, since it switches to less asymptotically optimal algorithms for small k (which have smaller constant factors and thus run faster for small numbers of elements).
In addition to its main functionality of finding the smallest k elements in a slice or a user-defined collection, QuickSelect also does the following:
- Provides convenience methods for integers, floats, and strings for finding the smallest k elements without having to write boilerplate.
- Provides a reverse method to get the largest k elements in a collection.
Example Usage
Using QuickSelect is as simple as using Go's built in sorting package, since it uses the exact same interfaces. Here's an example for getting the smallest 3 integers in an array:
package quickselect_test
import (
"fmt"
"github.com/wangjohn/quickselect"
)
func Example_intSlice() {
integers := []int{5, 2, 6, 3, 1, 4}
quickselect.QuickSelect(quickselect.IntSlice(integers), 3)
fmt.Println(integers[:3])
// Output: [2 3 1]
}
For more examples, see the documentation.
Is QuickSelect Fast?
I'm glad you asked. Actually, QuickSelect is on average about 20x faster than a naive sorting implementation. It's also faster than any selection algorithm alone, since it combines the best of many algorithms and figures out which algorithm to use for a given input.
You can see the benchmark results below (run on an Intel Core i7-4600U CPU @ 2.10GHz × 4 with 7.5 GiB of memory). Note that the name of the benchmark shows the inputs to the QuickSelect function where size denotes the length of the array and K denotes k as the integer input.
QuickSelect Benchmark ns/operation Speedup
-------------------------------------------------------------
BenchmarkQuickSelectSize1e2K1e1 27278 2.229672263
BenchmarkQuickSelectSize1e3K1e1 100185 9.038249239
BenchmarkQuickSelectSize1e3K1e2 209630 4.319501026
BenchmarkQuickSelectSize1e4K1e1 694067 17.86898815
BenchmarkQuickSelectSize1e4K1e2 1627887 7.618633849
BenchmarkQuickSelectSize1e4K1e3 2030468 6.108086904
BenchmarkQuickSelectSize1e5K1e1 6518500 31.63981913
BenchmarkQuickSelectSize1e5K1e2 8595422 23.99465215
BenchmarkQuickSelectSize1e5K1e3 16288198 12.66218405
BenchmarkQuickSelectSize1e5K1e4 20089387 10.26632425
BenchmarkQuickSelectSize1e6K1e1 67049413 30.49306274
BenchmarkQuickSelectSize1e6K1e2 70430656 29.02914829
BenchmarkQuickSelectSize1e6K1e3 110968263 18.42456484
BenchmarkQuickSelectSize1e6K1e4 161747855 12.64030337
BenchmarkQuickSelectSize1e6K1e5 189164465 10.80827711
BenchmarkQuickSelectSize1e7K1e1 689406050 32.98466508
BenchmarkQuickSelectSize1e7K1e2 684015273 33.24461976
BenchmarkQuickSelectSize1e7K1e3 737196456 30.84636053
BenchmarkQuickSelectSize1e7K1e4 1876629975 12.11737421
BenchmarkQuickSelectSize1e7K1e5 1454794314 15.6309572
BenchmarkQuickSelectSize1e7K1e6 2102171556 10.81730347
BenchmarkQuickSelectSize1e8K1e1 6822528776 39.07737829
BenchmarkQuickSelectSize1e8K1e2 6873096754 38.78987121
BenchmarkQuickSelectSize1e8K1e3 6922456224 38.51328622
BenchmarkQuickSelectSize1e8K1e4 16263664611 16.39277151
BenchmarkQuickSelectSize1e8K1e5 16568509572 16.09115996
BenchmarkQuickSelectSize1e8K1e6 20671732970 12.89715469
BenchmarkQuickSelectSize1e8K1e7 22154108390 12.03418044
Naive Sorting Benchmark ns/operation
-------------------------------------------------------------
BenchmarkSortSize1e2K1e1 60821
BenchmarkSortSize1e3K1e1 905497
BenchmarkSortSize1e4K1e1 12402275
BenchmarkSortSize1e5K1e1 206244161
BenchmarkSortSize1e6K1e1 2044541957
BenchmarkSortSize1e7K1e1 22739827661
BenchmarkSortSize1e8K1e1 266606537874
Speedup Statistics
------------------
AVG 19.16351964
MAX 39.07737829
MIN 2.229672263
If you'd like to run the benchmarks yourself, you can run them by doing go test -bench . inside of a checkout of the quickselect source.
Documentation
¶
Overview ¶
The quickselect package provides primitives for finding the smallest k elements in slices and user-defined collections. The primitives used in the package are modeled off of the standard sort library for Go. Quickselect uses Hoare's Selection Algorithm which finds the smallest k elements in expected O(n) time, and is thus an asymptotically optimal algorithm (and is faster than sorting or heap implementations).
Example ¶
package main
import (
"fmt"
"github.com/wangjohn/quickselect"
)
type Person struct {
Name string
Age int
}
func (p Person) String() string {
return fmt.Sprintf("%s: %d", p.Name, p.Age)
}
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func main() {
people := []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
quickselect.QuickSelect(ByAge(people), 2)
fmt.Println(people[:2])
}
Output: [Michael: 17 Jenny: 26]
Example (IntQuickSelect) ¶
package main
import (
"fmt"
"github.com/wangjohn/quickselect"
)
func main() {
integers := []int{5, 2, 6, 3, 1, 4}
quickselect.IntQuickSelect(integers, 3)
fmt.Println(integers[:3])
}
Output: [2 3 1]
Example (IntSlice) ¶
package main
import (
"fmt"
"github.com/wangjohn/quickselect"
)
func main() {
integers := []int{5, 2, 6, 3, 1, 4}
quickselect.QuickSelect(quickselect.IntSlice(integers), 3)
fmt.Println(integers[:3])
}
Output: [2 3 1]
Example (ReverseQuickSelect) ¶
package main
import (
"fmt"
"github.com/wangjohn/quickselect"
)
func main() {
integers := []int{5, 2, 6, 3, 1, 4}
quickselect.QuickSelect(quickselect.Reverse(quickselect.IntSlice(integers)), 3)
fmt.Println(integers[:3])
}
Output: [5 6 4]
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64QuickSelect ¶
Float64Select mutates the data so that the first k elements in the float64 slice are the k smallest elements in the slice. This is a convenience method for QuickSelect on float64 slices.
func IntQuickSelect ¶
IntQuickSelect mutates the data so that the first k elements in the int slice are the k smallest elements in the slice. This is a convenience method for QuickSelect on int slices.
func QuickSelect ¶
QuickSelect 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.
QuickSelect 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.
Note that k must be in the range [0, data.Len()), otherwise the QuickSelect method will raise an error.
func StringQuickSelect ¶
StringQuickSelect mutates the data so that the first k elements in the string slice are the k smallest elements in the slice. This is a convenience method for QuickSelect on string slices.
Types ¶
type Float64Slice ¶
type Float64Slice []float64
The Float64Slice type attaches the QuickSelect interface to an array of float64s. It implements Interface so that you can call QuickSelect(k) on any Float64Slice.
func (Float64Slice) Len ¶
func (t Float64Slice) Len() int
func (Float64Slice) Less ¶
func (t Float64Slice) Less(i, j int) bool
func (Float64Slice) QuickSelect ¶
func (t Float64Slice) QuickSelect(k int) error
QuickSelect(k) mutates the Float64Slice so that the first k elements in the Float64Slice are the k smallest elements in the slice. This is a convenience method for QuickSelect
func (Float64Slice) Swap ¶
func (t Float64Slice) Swap(i, j int)
type IntSlice ¶
type IntSlice []int
The IntSlice type attaches the QuickSelect interface to an array of ints. It implements Interface so that you can call QuickSelect(k) on any IntSlice.
func (IntSlice) QuickSelect ¶
QuickSelect(k) mutates the IntSlice so that the first k elements in the IntSlice are the k smallest elements in the slice. This is a convenience method for QuickSelect
type Interface ¶
type Interface interface {
// Len is the number of elements in the collection
Len() int
// Less reports whether the element with
// index i should sort before the element with index j
Less(i, j int) bool
// Swap swaps the order of elements i and j
Swap(i, j int)
}
A type, typically a collection, which satisfies quickselect.Interface can be used as data in the QuickSelect method. The interface is the same as the interface required by Go's canonical sorting package (sort.Interface).
Note that the methods require that the elements of the collection be enumerated by an integer index.
type StringSlice ¶
type StringSlice []string
The StringSlice type attaches the QuickSelect interface to an array of float64s. It implements Interface so that you can call QuickSelect(k) on any StringSlice.
func (StringSlice) Len ¶
func (t StringSlice) Len() int
func (StringSlice) Less ¶
func (t StringSlice) Less(i, j int) bool
func (StringSlice) QuickSelect ¶
func (t StringSlice) QuickSelect(k int) error
QuickSelect(k) mutates the StringSlice so that the first k elements in the StringSlice are the k smallest elements in the slice. This is a convenience method for QuickSelect
func (StringSlice) Swap ¶
func (t StringSlice) Swap(i, j int)
Source Files