Go, lesson 12
Sorted data is easier to read and much faster to search. Go's slices package (with help
from the cmp package) gives you everything you need, and it works with any element type.
slices.Sort sorts numbers and strings into ascending order, in place: it rearranges the
slice you give it rather than returning a new one.
Strings sort by byte value, so all uppercase letters come before lowercase ones. For a case-insensitive order, compare lowercased copies (see below).
For descending order, sort and then call slices.Reverse(nums).
To sort structs, or to sort in any special way, use slices.SortFunc. You pass a
comparison function that receives two elements a and and returns:
2 exercises to try what you just read.
ba should come first,b should come first,cmp.Compare(x, y) produces exactly that for numbers and strings, so most comparison
functions are one line:
For descending order, swap the arguments: cmp.Compare(b.Time, a.Time).
When two elements compare equal on the main key, add a second key. cmp.Or returns its first
non-zero argument, which reads nicely as "compare by this, then by that":
slices.SortFunc is not guaranteed to be stable: equal elements may end up in any order.
If you need equal elements to keep their original order, use slices.SortStableFunc.
slices.Index(s, v) scans from the start and returns the position of v, or -1. That is a
linear search: on a list of a million items it may look at all million.
If the slice is sorted, binary search is far faster. It looks at the middle item, decides which half the target must be in, and throws the other half away. A million items take about 20 steps.
When the target is missing, the index tells you where it would be inserted to keep the slice sorted. That makes questions like "how many values are smaller than x?" easy to answer.
For struct slices, slices.BinarySearchFunc takes a comparison between an element and the
target. The slice must be sorted by that same key, or the results are meaningless.
Recall that maps have no order. To print a map in key order, collect and sort its keys.
maps.Keys returns an iterator, and slices.Sorted turns any iterator into a sorted slice:
The first line holds n, the number of players. Each of the next n lines holds a name and a
score. Print the leaderboard: highest score first; players with equal scores in alphabetical
order of name. Number the lines from 1, as <rank>. <name> <score>.
Sample input:
Sample output:
A shop has a sorted price list. The first line holds n, then n prices in ascending order
on one line. The next line holds q, then q queries on one line. For each query price p,
print p: found at <index> if it is in the list (indexes start at 0), otherwise
p: <k> cheaper where k is how many listed prices are below p. Use binary search.
Sample input:
Sample output:
nums := []int{42, 7, 19}
slices.Sort(nums)
fmt.Println(nums) // [7 19 42]
names := []string{"pear", "Apple", "fig"}
slices.Sort(names)
fmt.Println(names) // [Apple fig pear]type Runner struct {
Name string
Time int // seconds
}
slices.SortFunc(runners, func(a, b Runner) int {
return cmp.Compare(a.Time, b.Time) // fastest first
})slices.SortFunc(runners, func(a, b Runner) int {
return cmp.Or(
cmp.Compare(a.Time, b.Time),
cmp.Compare(a.Name, b.Name),
)
})sorted := []int{3, 8, 15, 23, 42}
i, found := slices.BinarySearch(sorted, 23)
fmt.Println(i, found) // 3 true
i, found = slices.BinarySearch(sorted, 10)
fmt.Println(i, found) // 2 falsefor _, k := range slices.Sorted(maps.Keys(stock)) {
fmt.Println(k, stock[k])
}4
zed 50
amy 80
bob 50
cat 951. cat 95
2. amy 80
3. bob 50
4. zed 505
3 8 15 23 42
3
23 10 5023: found at 3
10: 2 cheaper
50: 5 cheaper