I wrote a program in Go that finds the smallest number in a list and it works. However, I don't really understand the logic. Could you please explait how comes that it works?
package main
import "fmt"
func main() {
x := []int{
48, 96, 86, 68,
57, 82, 63, 70,
37, 34, 83, 27,
19, 97, 9, 17,
}
for i, num := range x {
if num < i {
fmt.Println(num)
}
}
}
Playground: https://play.golang.org/p/Awuw2Th1g2V
Output:
9
The solution in my textbook is different and I understand the logic there.
To expand a bit on @hoque's answer: The fact that the sample program you give is purely coincidental. If the correct value 9 would be the first in the slice, there would be no output at all.
There are various ways to achieve the goal of identifying the smallest int (there are more ways):
func smallestOfCopyWithSort(in []int) int {
// Make a copy, so we do not have to modify the original slice.
// Note: Do NOT use this approach, it is here only for completeness.
copy := append([]int(nil), in...)
sort.Ints(copy)
return (copy[0])
}
func smallestWithSort(in []int) int {
// Sort the slice.
// Note that it will be modified and you
// need to make sure that it will always
// be sorted, even when you add new values.
sort.Ints(in)
return (in[0])
}
func smallestWithMattsApproach(in []int) int {
smallest := in[0] // set the smallest number to the first element of the list
for _, num := range in[1:] { // iterate over the rest of the list
if num < smallest { // if num is smaller than the current smallest number
smallest = num // set smallest to num
}
}
return smallest
}
@Matt's approach is probably the best one, as it is quite fast without the need of modifying the original slice. And it really depends on what you want to achieve. Here are some benchmarks
$ go test -test.benchmem -bench=. -test.cpu 1,2,4 -test.benchtime=10s
goos: darwin
goarch: amd64
pkg: <redacted>
BenchmarkSortWithCopy 5000000 345 ns/op 160 B/op 2 allocs/op
BenchmarkSortWithCopy-2 5000000 354 ns/op 160 B/op 2 allocs/op
BenchmarkSortWithCopy-4 5000000 352 ns/op 160 B/op 2 allocs/op
BenchmarkMattsApproach 100000000 15.1 ns/op 0 B/op 0 allocs/op
BenchmarkMattsApproach-2 100000000 15.1 ns/op 0 B/op 0 allocs/op
BenchmarkMattsApproach-4 100000000 15.2 ns/op 0 B/op 0 allocs/op
BenchmarkSort 2000000000 0.00 ns/op 0 B/op 0 allocs/op
BenchmarkSort-2 2000000000 0.00 ns/op 0 B/op 0 allocs/op
BenchmarkSort-4 2000000000 0.00 ns/op 0 B/op 0 allocs/op
Non-surprisingly, smallestOfCopyWithSort is orders of magnitude slower than the other approaches if called multiple times.
Matts approach is blazing fast and does not copy or modify anything.
However, if you need to access the smallest number of the slice multiple times, sorting the slice (ascending) and simply accessing the first member is more efficient. The reason for this is that the slice will be modified to be in sorted order. There is a caveat to this approach, however: you either need to be very careful when you add values to the slice or resort it every time you modify it, which might nullify the performance advantage, depending on your ratio of reads and writes to/from the slice. Personally, I find the smallestWithSort the solution I use most often, since the slices I am working with usually do not change.
If you only need to access the smallest number once or the order of the slice values matters, use Matt's approach. If the order does not matter and you need to access the smallest number more than once, you probably should go with smallestWithSort, keeping the constraints in mind.