前置知识：无
建议：不要跳过，非常重要的自我验证技巧
对数器的适用场景
你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试
你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试
你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了，甚至有的根本不提示哪个例子错了，怎么 debug？
对数器的实现
- 你想要测的方法 a（最优解）
- 实现复杂度不好但是容易实现的方法 b（暴力解）
- 实现一个随机样本产生器（长度也随机、值也随机）
- 把方法 a 和方法 b 跑相同的输入样本，看看得到的结果是否一样
- 如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法 a 和方法 b
- 当样本数量很多时比对测试依然正确，可以确定方法 a（最优解）已经正确
关键是第 5 步，找到一个数据量小的错误样本，便于你去带入 debug
然后把错误例子带入代码一步一步排查（Print 大法、断点技术都可以）
对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个
以后的很多题目都会用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用
到时候会丰富很多对数器的实战用法，这里只是一个简单易懂的示例
对数器验证一下
用对数器验证一下 上节课 写的“三傻排序”的正确性
package main
import (
"fmt"
"math/rand"
"sort"
)
const (
N = 200 // 随机数组最大长度
MIN = -1000 // 随机数组每个值，在 [MIN, MAX) 之间等概率随机
MAX = 1001
TEST_TIMES = 50000 // 测试次数
)
func main() {
if testSort(sort.Ints, selectionSort) {
fmt.Println("选择排序正确")
} else {
fmt.Println("选择排序错误")
}
fmt.Println()
if testSort(sort.Ints, bubbleSort) {
fmt.Println("冒泡排序正确")
} else {
fmt.Println("冒泡排序错误")
}
fmt.Println()
if testSort(sort.Ints, insertionSort) {
fmt.Println("插入排序正确")
} else {
fmt.Println("插入排序错误")
}
}
// 对数器：生成随机样本，测试 方法一 和 方法二 的结果是否相同
func testSort(fn1, fn2 func([]int)) bool {
ok := true
for i := 0; i < TEST_TIMES; i++ {
arr := generateRandomArray()
copiedArr := copyArray(arr)
fn1(arr)
fn2(copiedArr)
for i := 0; i < len(arr); i++ {
if arr[i] != copiedArr[i] {
ok = false
break
}
}
}
return ok
}
// 生成一个随机 int 数组，数组最大长度为 N，数组中每个数，都在 [MIN, MAX) 之间
func generateRandomArray() []int {
length := generateRandomInt(0, N+1)
arr := make([]int, length)
for i := 0; i < length; i++ {
arr[i] = generateRandomInt(MIN, MAX)
}
return arr
}
// 拷贝数组
func copyArray(arr []int) []int {
copiedArr := make([]int, len(arr))
copy(copiedArr, arr)
return copiedArr
}
// 生成一个随机整数，[min, max) 范围
func generateRandomInt(min, max int) int {
// go 1.20 废弃，不写自动使用 globalRand 生成随机数
// rand.Seed(time.Now().UnixNano())
// rand.Intn(n)：等概率返回 [0, n) 的 int
// 若传入的 n 为负数，则 panic
return rand.Intn(max-min) + min
}
// ------------------------------
// 选择排序
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ { // i ~ n - 1 找最小值
minIdx := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIdx] {
minIdx = j
}
}
arr[minIdx], arr[i] = arr[i], arr[minIdx] // 最小值放到 i 位置
}
}
// 冒泡排序
func bubbleSort(arr []int) {
n := len(arr)
for i := n - 1; i > 0; i-- {
for j := 0; j < i; j++ { // 0 ~ i 范围上，相邻位置较大的数往后移
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
// 插入排序
func insertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
for j := i; j > 0; j-- {
if arr[j] < arr[j-1] {
arr[j], arr[j-1] = arr[j-1], arr[j]
} else {
break
}
}
}
}选择排序正确
冒泡排序正确
插入排序正确当有错时，打印是什么例子出错的，各自排序成了什么样，可能要把例子带入每个方法，去 debug！