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.go b/android/util.go
index ade851e..e74b64e 100644
--- a/android/util.go
+++ b/android/util.go
@@ -193,6 +193,14 @@
// FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
// each. It modifies the slice contents in place, and returns a subslice of the original slice.
func FirstUniqueStrings(list []string) []string {
+ // 128 was chosen based on BenchmarkFirstUniqueStrings results.
+ if len(list) > 128 {
+ return firstUniqueStringsMap(list)
+ }
+ return firstUniqueStringsList(list)
+}
+
+func firstUniqueStringsList(list []string) []string {
k := 0
outer:
for i := 0; i < len(list); i++ {
@@ -207,6 +215,20 @@
return list[:k]
}
+func firstUniqueStringsMap(list []string) []string {
+ k := 0
+ seen := make(map[string]bool, len(list))
+ for i := 0; i < len(list); i++ {
+ if seen[list[i]] {
+ continue
+ }
+ seen[list[i]] = true
+ list[k] = list[i]
+ k++
+ }
+ return list[:k]
+}
+
// LastUniqueStrings returns all unique elements of a slice of strings, keeping the last copy of
// each. It modifies the slice contents in place, and returns a subslice of the original slice.
func LastUniqueStrings(list []string) []string {