I need to sort a slice of custom type as fast as possible.
The generalize the problem, I have a slice points defined as:
type point struct {
x float64
y int32
}
var points []point
I need now, based on the user input, sort the slice either by its filed x or by its fields y and then x.
I have read in multiple places that sort.Interface performs better than sort.Slice, so I am doing as follow for sorting by x:
type Slice struct {
sort.Interface
idx []int
}
func (s Slice) Swap(i, j int) {
s.Interface.Swap(i, j)
s.idx[i], s.idx[j] = s.idx[j], s.idx[i]
}
func NewSlice(n sort.Interface) *Slice {
s := &Slice{Interface: n, idx: make([]int, n.Len())}
for i := range s.idx {
s.idx[i] = i
}
return s
}
func NewFloat64Slice(n ...float64) *Slice {
return NewSlice(sort.Float64Slice(n))
}
/// in main
var S *Slice
xx := make([]float64, len(points))
for v := range points {
xx[v] = points[v].x
}
S = NewFloat64Slice(xx...)
sort.Sort(S)
sortedbyX := make([]point, len(points))
for j, i := range S.idx {
sortedbyX[j] = points[i]
}
or for sorting by y and then x:
type byYX []point
func (pnts byYX) Len() int { return len(pnts) }
func (pnts byYX) Swap(i, j int) { pnts[i], pnts[j] = pnts[j], pnts[i] }
func (pnts byYX) Less(i, j int) bool {
if pnts[i].y == pnts[j].y {
return pnts[i].x < pnts[j].x
} else {
return pnts[i].y < pnts[j].y
}
}
func NewCSlice(n ...point) *Slice {
return NewSlice(byYX(n))
}
/// in main
S = NewCSlice(points...)
sort.Sort(S)
Here is a full examples with some real data (someone might noticed that the slice xs is already sorted, but it is just a dummy dataset here, this never happens in my application).
I am now wondering whether this is indeed the fastest way to sort, or if there is a better way to do it.
Any suggestion?
