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.
In
for i, num := range x {
if num < i {
fmt.Println(num)
}
}
Here, i represents index and num represents the value. So, your if condition represents value is less than index then prints the value. For, 9 value is 9 and index is 14. so It prints 9, Which is not what you want to do.
To find the smallest number in the list you will need to iterate over the list and store the smallest number you have currently found. Compare this "smallest-so-far" number against each other number in the list and if you find a smaller one, replace your smallest number with it. At the end of the iteration you will know the smallest number in the list.
smallest := x[0] // set the smallest number to the first element of the list
for _, num := range x[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
}
}
fmt.Println(smallest)
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.