76 lines
1.5 KiB
Go
76 lines
1.5 KiB
Go
package algo
|
|
|
|
import (
|
|
"fmt"
|
|
"math/rand"
|
|
"testing"
|
|
)
|
|
|
|
type testCase struct {
|
|
t1 []int
|
|
t2 []int
|
|
e1 []int
|
|
e2 []int
|
|
}
|
|
|
|
func randomCase(rng *rand.Rand, n int) testCase {
|
|
tc := testCase{
|
|
t1: make([]int, n),
|
|
t2: make([]int, n),
|
|
e1: make([]int, n),
|
|
e2: make([]int, n),
|
|
}
|
|
|
|
for i := 0; i < n; i++ {
|
|
tc.t1[i] = rng.Intn(1000)
|
|
tc.t2[i] = rng.Intn(1000)
|
|
tc.e1[i] = rng.Intn(1000)
|
|
tc.e2[i] = rng.Intn(1000)
|
|
}
|
|
|
|
return tc
|
|
}
|
|
|
|
func TestRecAndDPMatchOnRandomData(t *testing.T) {
|
|
rng := rand.New(rand.NewSource(1))
|
|
const casesPerLen = 200
|
|
|
|
for n := 1; n <= 128; n++ {
|
|
for caseIdx := 0; caseIdx < casesPerLen; caseIdx++ {
|
|
tc := randomCase(rng, n)
|
|
gotRec := Rec(tc.t1, tc.t2, tc.e1, tc.e2)
|
|
gotDP := DP(tc.t1, tc.t2, tc.e1, tc.e2)
|
|
if gotRec != gotDP {
|
|
t.Fatalf("mismatch for len=%d case=%d: Rec=%d DP=%d t1=%v t2=%v e1=%v e2=%v",
|
|
n, caseIdx, gotRec, gotDP, tc.t1, tc.t2, tc.e1, tc.e2)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func BenchmarkDP(b *testing.B) {
|
|
benchmarkByLen(b, "DP", DP)
|
|
}
|
|
|
|
func BenchmarkRec(b *testing.B) {
|
|
benchmarkByLen(b, "Rec", Rec)
|
|
}
|
|
|
|
func benchmarkByLen(b *testing.B, name string, fn func([]int, []int, []int, []int) int) {
|
|
lengths := []int{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000}
|
|
|
|
for _, n := range lengths {
|
|
n := n
|
|
b.Run(fmt.Sprintf("%s/len=%d", name, n), func(b *testing.B) {
|
|
rng := rand.New(rand.NewSource(int64(n)))
|
|
tc := randomCase(rng, n)
|
|
|
|
b.ReportAllocs()
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
_ = fn(tc.t1, tc.t2, tc.e1, tc.e2)
|
|
}
|
|
})
|
|
}
|
|
}
|