Optimize FirstUniqueStrings and FirstUniquePaths
FirstUniquePaths is called on some long lists where the O(n^2)
behavior is problematic. Use a map-based implementation for
longer lists.
Test: TestFirstUniqueStrings
Change-Id: I7181aba869e5ccc0f99c2fa7b8f03839f06e4307
diff --git a/android/util_test.go b/android/util_test.go
index 1f9ca36..25b52ca 100644
--- a/android/util_test.go
+++ b/android/util_test.go
@@ -17,6 +17,7 @@
import (
"fmt"
"reflect"
+ "strconv"
"testing"
)
@@ -59,15 +60,25 @@
}
func TestFirstUniqueStrings(t *testing.T) {
- for _, testCase := range firstUniqueStringsTestCases {
- out := FirstUniqueStrings(testCase.in)
- if !reflect.DeepEqual(out, testCase.out) {
+ f := func(t *testing.T, imp func([]string) []string, in, want []string) {
+ t.Helper()
+ out := imp(in)
+ if !reflect.DeepEqual(out, want) {
t.Errorf("incorrect output:")
- t.Errorf(" input: %#v", testCase.in)
- t.Errorf(" expected: %#v", testCase.out)
+ t.Errorf(" input: %#v", in)
+ t.Errorf(" expected: %#v", want)
t.Errorf(" got: %#v", out)
}
}
+
+ for _, testCase := range firstUniqueStringsTestCases {
+ t.Run("list", func(t *testing.T) {
+ f(t, firstUniqueStringsList, testCase.in, testCase.out)
+ })
+ t.Run("map", func(t *testing.T) {
+ f(t, firstUniqueStringsMap, testCase.in, testCase.out)
+ })
+ }
}
var lastUniqueStringsTestCases = []struct {
@@ -568,3 +579,51 @@
})
}
}
+
+func BenchmarkFirstUniqueStrings(b *testing.B) {
+ implementations := []struct {
+ name string
+ f func([]string) []string
+ }{
+ {
+ name: "list",
+ f: firstUniqueStringsList,
+ },
+ {
+ name: "map",
+ f: firstUniqueStringsMap,
+ },
+ }
+ const maxSize = 1024
+ uniqueStrings := make([]string, maxSize)
+ for i := range uniqueStrings {
+ uniqueStrings[i] = strconv.Itoa(i)
+ }
+ sameString := make([]string, maxSize)
+ for i := range sameString {
+ sameString[i] = uniqueStrings[0]
+ }
+
+ f := func(b *testing.B, imp func([]string) []string, s []string) {
+ for i := 0; i < b.N; i++ {
+ b.ReportAllocs()
+ s = append([]string(nil), s...)
+ imp(s)
+ }
+ }
+
+ for n := 1; n <= maxSize; n <<= 1 {
+ b.Run(strconv.Itoa(n), func(b *testing.B) {
+ for _, implementation := range implementations {
+ b.Run(implementation.name, func(b *testing.B) {
+ b.Run("same", func(b *testing.B) {
+ f(b, implementation.f, sameString[:n])
+ })
+ b.Run("unique", func(b *testing.B) {
+ f(b, implementation.f, uniqueStrings[:n])
+ })
+ })
+ }
+ })
+ }
+}