README
¶
sorts
sorts provides parallel radix sorting by a string, []byte, or (u)int64 key, and a parallel Quicksort(data). sorts/sortutil sorts common slice types and adds functions to help sort floats.
Usually, stick to stdlib sort: that's fast, standard, and simpler. But this package may help if sorting huge datasets is a bottleneck for you. To get a sense of the potential gains, some timings are available.
To radix sort, implement sort.Interface plus one more method, Key(i int), returning the key for an item as string/[]byte/(u)int64, and call sorts.ByString, ByBytes, ByUint64, or ByInt64. See the godoc for details and examples: http://godoc.org/github.com/twotwotwo/sorts
There's no Reverse(), but sorts.Flip(data) will flip ascending-sorted data to descending. There's no stable sort. The string sorts just compare byte values; é won't sort next to e. Set sorts.MaxProcs if you want to limit concurrency. The package checks that data is sorted after every run and panics(!) if not.
Credit (but no blame, or claim of endorsement) to the authors of stdlib sort; this uses its qSort, tests, and interface, and the clarity of its code helped make this possible.
I'd love to hear if you're using this. E-mail me at my github username at GMail, or say hey on Twitter (@rf).
Documentation
¶
Overview ¶
Package sorts does parallel radix sorts of data by (u)int64, string, or []byte keys, and parallel quicksort. See the sorts/sortutil package for shortcuts for common slice types and help sorting floats.
Example ¶
package main
import (
"fmt"
"github.com/twotwotwo/sorts"
"github.com/twotwotwo/sorts/sortutil"
)
type City struct {
Name string
Latitude, Longitude float32
}
func (c City) String() string { return fmt.Sprintf("%s (%.1f, %.1f)", c.Name, c.Latitude, c.Longitude) }
// ByLatitude implements sort.Interface for []City based on
// the Latitude field, for sorting cities south to north.
type ByLatitude []City
func (a ByLatitude) Len() int { return len(a) }
func (a ByLatitude) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
// Float32Key and Float32Less make the sort handle the sign bit and sort NaN
// values to the end. There are also Float64Key and Float64Less, and
// [Type]Key functions for int types.
// Key returns a uint64 that is lower for more southerly latitudes.
func (a ByLatitude) Key(i int) uint64 {
return sortutil.Float32Key(a[i].Latitude)
}
func (a ByLatitude) Less(i, j int) bool {
return sortutil.Float32Less(a[i].Latitude, a[j].Latitude)
}
func main() {
cities := []City{
{"Vancouver", 49.3, -123.1},
{"Tokyo", 35.6, 139.7},
{"Honolulu", 21.3, -157.8},
{"Sydney", -33.9, 151.2},
}
fmt.Println(cities)
sorts.ByUint64(ByLatitude(cities))
fmt.Println(cities)
}
Output: [Vancouver (49.3, -123.1) Tokyo (35.6, 139.7) Honolulu (21.3, -157.8) Sydney (-33.9, 151.2)] [Sydney (-33.9, 151.2) Honolulu (21.3, -157.8) Tokyo (35.6, 139.7) Vancouver (49.3, -123.1)]
Example (Flip) ¶
package main
import (
"fmt"
"github.com/twotwotwo/sorts"
"github.com/twotwotwo/sorts/sortutil"
)
func main() {
scores := []int{39, 492, 4912, 39, -10, 4, 92}
data := sortutil.IntSlice(scores)
data.Sort()
sorts.Flip(data) // high scores first
fmt.Println(scores)
}
Output: [4912 492 92 39 39 4 -10]
Example (Strings) ¶
package main
import (
"fmt"
"github.com/twotwotwo/sorts/sortutil"
)
func main() {
groceries := []string{"peppers", "tortillas", "tomatoes", "cheese"}
sortutil.Strings(groceries) // or sortutil.Bytes([][]byte)
fmt.Println(groceries)
}
Output: [cheese peppers tomatoes tortillas]
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var MaxProcs = 0
MaxProcs controls how many goroutines to start for large sorts. If 0, GOMAXPROCS will be used; if 1, all sorts will be serial.
Functions ¶
Types ¶
type BytesInterface ¶
type BytesInterface interface {
sort.Interface
// Key provides the []byte key for element i.
Key(i int) []byte
}
BytesInterface represents a collection that can be sorted by a []byte key.
type Int64Interface ¶
type Int64Interface interface {
sort.Interface
// Key provides an int64 key for element i.
Key(i int) int64
}
Int64Interface represents a collection that can be sorted by an int64 key.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package index uses sorted arrays of integers to assist sorting and searching, particularly of collections of strings.
|
Package index uses sorted arrays of integers to assist sorting and searching, particularly of collections of strings. |
|
Package sortutil sorts and searches common slice types (and helps sort floats).
|
Package sortutil sorts and searches common slice types (and helps sort floats). |