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/paths.go b/android/paths.go
index 8b373da..c4b1073 100644
--- a/android/paths.go
+++ b/android/paths.go
@@ -470,6 +470,14 @@
// FirstUniquePaths returns all unique elements of a Paths, keeping the first copy of each. It
// modifies the Paths slice contents in place, and returns a subslice of the original slice.
func FirstUniquePaths(list Paths) Paths {
+ // 128 was chosen based on BenchmarkFirstUniquePaths results.
+ if len(list) > 128 {
+ return firstUniquePathsMap(list)
+ }
+ return firstUniquePathsList(list)
+}
+
+func firstUniquePathsList(list Paths) Paths {
k := 0
outer:
for i := 0; i < len(list); i++ {
@@ -484,6 +492,20 @@
return list[:k]
}
+func firstUniquePathsMap(list Paths) Paths {
+ k := 0
+ seen := make(map[Path]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]
+}
+
// LastUniquePaths returns all unique elements of a Paths, keeping the last copy of each. It
// modifies the Paths slice contents in place, and returns a subslice of the original slice.
func LastUniquePaths(list Paths) Paths {