Documentation
¶
Overview ¶
Package sort provides implementations of parallel sorting algorithms.
Example ¶
// Adapted by Pascal Costanza for the Pargo package.
package main
import (
"fmt"
stdsort "sort"
sort "github.com/exascience/pargo/sort"
)
type Person struct {
Name string
Age int
}
func (p Person) String() string {
return fmt.Sprintf("%s: %d", p.Name, p.Age)
}
// ByAge implements sort.SequentialSorter, sort.Sorter, and sort.StableSorter
// for []Person based on the Age field.
type ByAge []Person
func (a ByAge) SequentialSort(i, j int) {
stdsort.SliceStable(a, func(i, j int) bool {
return a[i].Age < a[j].Age
})
}
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 (a ByAge) NewTemp() sort.StableSorter { return make(ByAge, len(a)) }
func (this ByAge) Assign(that sort.StableSorter) func(i, j, len int) {
dst, src := this, that.(ByAge)
return func(i, j, len int) {
for k := 0; k < len; k++ {
dst[i+k] = src[j+k]
}
}
}
func main() {
people := []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
fmt.Println(people)
sort.Sort(ByAge(people))
fmt.Println(people)
people = []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
fmt.Println(people)
sort.StableSort(ByAge(people))
fmt.Println(people)
}
Output: [Bob: 31 John: 42 Michael: 17 Jenny: 26] [Michael: 17 Jenny: 26 Bob: 31 John: 42] [Bob: 31 John: 42 Michael: 17 Jenny: 26] [Michael: 17 Jenny: 26 Bob: 31 John: 42]
Index ¶
- func Float64sAreSorted(a []float64) bool
- func IntsAreSorted(a []int) bool
- func IsSorted(data sort.Interface) bool
- func Sort(data Sorter)
- func StableSort(data StableSorter)
- func StringsAreSorted(a []string) bool
- type Float64Slice
- type IntSlice
- type SequentialSorter
- type Sorter
- type StableSorter
- type StringSlice
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64sAreSorted ¶
Float64sAreSorted determines in parallel whether a slice of float64s is already sorted in increasing order. It attempts to terminate early when the return value is false.
func IntsAreSorted ¶
IntsAreSorted determines in parallel whether a slice of ints is already sorted in increasing order. It attempts to terminate early when the return value is false.
func IsSorted ¶
IsSorted determines in parallel whether data is already sorted. It attempts to terminate early when the return value is false.
func Sort ¶
func Sort(data Sorter)
Sort uses a parallel quicksort implementation.
It is good for small core counts and small collection sizes.
func StableSort ¶
func StableSort(data StableSorter)
StableSort uses a parallel implementation of merge sort, also known as cilksort.
StableSort is only stable if data's SequentialSort method is stable.
StableSort is good for large core counts and large collection sizes, but needs a shallow copy of the data collection as additional temporary memory.
func StringsAreSorted ¶
StringsAreSorted determines in parallel whether a slice of strings is already sorted in increasing order. It attempts to terminate early when the return value is false.
Types ¶
type Float64Slice ¶
type Float64Slice []float64
Float64Slice attaches the methods of sort.Interface, SequentialSorter, Sorter, and StableSorter to []float64, sorting in increasing order.
func (Float64Slice) Assign ¶
func (s Float64Slice) Assign(source StableSorter) func(i, j, len int)
Assign implements the method of the StableSorter interface.
func (Float64Slice) Len ¶
func (s Float64Slice) Len() int
func (Float64Slice) Less ¶
func (s Float64Slice) Less(i, j int) bool
func (Float64Slice) NewTemp ¶
func (s Float64Slice) NewTemp() StableSorter
NewTemp implements the method of the StableSorter interface.
func (Float64Slice) SequentialSort ¶
func (s Float64Slice) SequentialSort(i, j int)
SequentialSort implements the method of the SequentialSorter interface.
func (Float64Slice) Swap ¶
func (s Float64Slice) Swap(i, j int)
type IntSlice ¶
type IntSlice []int
IntSlice attaches the methods of sort.Interface, SequentialSorter, Sorter, and StableSorter to []int, sorting in increasing order.
func (IntSlice) Assign ¶
func (s IntSlice) Assign(source StableSorter) func(i, j, len int)
Assign implements the method of the StableSorter interface.
func (IntSlice) NewTemp ¶
func (s IntSlice) NewTemp() StableSorter
NewTemp implements the method of the StableSorter interface.
func (IntSlice) SequentialSort ¶
SequentialSort implements the method of of the SequentialSorter interface.
type SequentialSorter ¶
type SequentialSorter interface {
// Sort the range that starts at index i and ends at index j. If the
// collection that is represented by this interface is a slice, then the
// slice expression collection[i:j] returns the correct slice to be sorted.
SequentialSort(i, j int)
}
SequentialSorter is a type, typically a collection, that can be sequentially sorted. This is needed as a base case for the parallel sorting algorithms in this package. It is recommended to implement this interface by using the functions in the sort package of Go's standard library.
type Sorter ¶
type Sorter interface {
SequentialSorter
sort.Interface
}
Sorter is a type, typically a collection, that can be sorted by Sort in this package. The methods require that (ranges of) elements of the collection can be enumerated by integer indices.
type StableSorter ¶
type StableSorter interface {
SequentialSorter
// NewTemp creates a new collection that can hold as many elements as the
// original collection. This is temporary memory needed by StableSort, but
// not needed anymore afterwards. The temporary collection does not need to
// be initialized.
NewTemp() StableSorter
// 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
// Assign returns a function that assigns ranges from source to the receiver
// collection. The element with index i is the first element in the receiver
// to assign to, and the element with index j is the first element in the
// source collection to assign from, with len determining the number of
// elements to assign. The effect should be the same as receiver[i:i+len] =
// source[j:j+len].
Assign(source StableSorter) func(i, j, len int)
}
StableSorter is a type, typically a collection, that can be sorted by StableSort in this package. The methods require that ranges of elements of the collection can be enumerated by integer indices.
type StringSlice ¶
type StringSlice []string
StringSlice attaches the methods of sort.Interface, SequentialSorter, Sorter, and StableSorter to []string, sorting in increasing order.
func (StringSlice) Assign ¶
func (s StringSlice) Assign(source StableSorter) func(i, j, len int)
Assign implements the method of the StableSorter interface.
func (StringSlice) Len ¶
func (s StringSlice) Len() int
func (StringSlice) Less ¶
func (s StringSlice) Less(i, j int) bool
func (StringSlice) NewTemp ¶
func (s StringSlice) NewTemp() StableSorter
NewTemp implements the method of the StableSorter interface.
func (StringSlice) SequentialSort ¶
func (s StringSlice) SequentialSort(i, j int)
SequentialSort implements the method of the SequentialSorter interface.
func (StringSlice) Swap ¶
func (s StringSlice) Swap(i, j int)
Source Files