README
¶
About
This package is a collection of extra primitives related to sorting. Currently, it has only two functions:
These functions allow to quickly re-sort a previously sorted slice, which has few unsorted elements appended. Appended works pretty well if the tail is small, but limitations of the in-place algorithm makes it ineffective is the tail is comparable by size with the total size of the slice. While AppendedWithBuf is effective with
As one may see resorting 100 items in a slice of length 1048576 using AppendedWithBuf is almost 100 times more effective than just full resorting using sort.Slice or sort.Sort. But if the amount of unsorted items is too high then it might be less effective. So for convenience to automatically avoid spending more time than simple through Sort/Slice these functions has heuristic fallback logic for big tails, so the actual performance for a slice of size 1048576 looks like here:
But using of these functions does not make sense if tailLength always equals to len(s).
P.S.: Also for comparison here is performance for a slice of size 256:
Quick start
In-place:
package main
import (
"fmt"
"sort"
"github.com/go-ng/xsort"
)
func main() {
s := sort.IntSlice{-4, -2, 1, 3, 4, 5, 9}
s = append(s, 2, -3)
xsort.Appended(s, 2)
fmt.Println(s) // output: [-4 -3 -2 1 2 3 4 5 9]
}
With buffer (faster):
package main
import (
"fmt"
"sort"
"github.com/go-ng/xsort"
)
func main() {
s := sort.IntSlice{-4, -2, 1, 3, 4, 5, 9}
a := []int{2, -3}
s = append(s, a...)
xsort.AppendedWithBuf(s, a)
fmt.Println(s) // output: [-4 -3 -2 1 2 3 4 5 9]
}
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Appended ¶
Appended sort a slice in assumption that the beginning of the slice is already sorted, and only tailLength new unsorted elements are added to the end of the slice. The function contains an optimization for a case where tailLength is low and it is possible to resort the slice faster than just through a full resorting.
For example if there is a slice of length 65536 with only 512 unsorted elements in the end, then `Appended` on my laptop works 7 times faster than just using `Slice` on the whole slice.
The algorithm is good if the unsorted right part of the array is much smaller than the sorted left part (see `docs/force_appended_benchmark.txt`), but otherwise it is worse than a simple quick sort. So it fallbacks to quicksort if the unsorted part is too big.
Roughly:
T: O(k*ln(n) + n + k^2) -- thus if `k` is too high then: O(k^2)
S: O(1) [if without `s`]
func AppendedWithBuf ¶
AppendedWithBuf is the same as Appended but: * Much faster. * Requires a buffer.
The buffer length should be exactly the same as the length of the unsorted tail.
For example if there is a slice of length 65536 with only 512 unsorted elements in the end, then `Appended` on my laptop works ~30 times faster than just using `Slice` on the whole slice.
T: O(k*ln(n) + n)
S: O(k) [if without `s`]
Source Files
Directories