Swift – 性能明智 – 比较两个数组，并在两者中获得每个和共同的差异

希望你有一个美好的一天。

我试图了解什么是最快的方法来做到以下几点：

假设我有这两个Arrays ：

 var firstArray = ["a","b","c"] var secondArray = ["a","d","e"] 

我想得到一个输出：

1） 在 firstArray 但在 secondArray 没有的对象Array 。
1） 在 secondArray 里面 但在 firstArray 里 没有的对象Array 。
3） firstArray和secondArray之间的公共对象secondArray 。

所以基本上输出将是：

1） ["b","c"]
2） ["d","e"]
3） ["a"]

这里的主要问题是要了解什么是最有效的方法。 非常感谢你！

Answer 1

如果你的数组是sorting的，而且每个数组中的项都是唯一的，最快的方法就是只处理一个项。 首先比较每个数组中的第一项; 如果它们相等，则将其放入常用数组中，然后转到第二项。 如果一个项目小于另一个项目，则进入较小项目的唯一arrays，然后转到较小arrays中的下一个项目。 继续这个过程，直到用完一个数组的项目，然后将第二个数组的其余项目放入该数组的唯一项目数组中。

 var i = 0 var j = 0 let a = ["a", "b", "c"] let b = ["a", "d", "e"] var aUnique = [String]() var bUnique = [String]() var common = [String]() while i < a.count && j < b.count { if a[i] == b[j] { common.append(a[i]) i += 1 j += 1 } else if a[i] < b[j] { aUnique.append(a[i]) i += 1 } else { bUnique.append(b[j]) j += 1 } } if i < a.count { // put remaining items into aUnique aUnique += a[i ..< a.count] } else if j < b.count { // put remaining items into bUnique bUnique += b[j ..< b.count] } print(common) // ["a"] print(aUnique) // ["b", "c"] print(bUnique) // ["d", "e"] 

---

分析

• 该algorithm每次通过循环将一个项目追加到其中一个数组。 如果两个数组相互独立，或者只有最后一个数组是相同的，那么它最多会循环a.count + b.count - 1次。
• 如果两个数组是相同的，它将只a.count一次。
• 如果数组b所有元素都大于数组b的元素，则它将只循环a.count次。 如果数组a所有元素都大于数组b的元素，则它将只循环b.count次。

Answer 2

我会假设你的数组的元素是Equatable 。

如果它们也是Hashable ，并且如果元素的顺序对您不重要，并且（如您的示例中）所有元素都是唯一的，那么您可能要考虑使用集合代数而不是有序集合types，例如Array 。 例如，在Swift中使用Set可以使用1）和2）的subtract(_:)或subtracting(_:)变异/非方法和3）的intersection(_:) / formIntersection(_:) ），全部使用O（1）（分期付款）查找来比较集合之间的元素（与例如使用O（n）包含（_ 🙂 Array（带有Equatable元素）来查找某个指定元素的存在）。

有关更多详细信息，请参阅Set的语言参考以及由vadian链接的主题：

• 在Swift数组上设置操作（联合，交集）？

---

如果每个数组中的元素不是唯一的，并且想要保持多个元素以及元素之间的顺序，则可以使用其中一个数组的Set表示，同时过滤另一个数组。

例如，对于：

 var firstArray = ["a","b","c"] var secondArray = ["a","d","e"] 

A）在O(n) ：

 let excludeElements = Set(secondArray) // O(n) secondArray = secondArray .filter { !excludeElements.contains($0) } // O(n) due to O(1) (amortized) .contains lookup 

B）在O(n) ：

 let excludeElements = Set(firstArray) // O(n) secondArray = secondArray .filter { !excludeElements.contains($0) } // O(n) due to O(1) (amortized) .contains lookup 

C）在O(n) ，使用顺序和重复，因为它们发生在firstArray ：

 let includeElements = Set(secondArray) // O(n) let commonElements = firstArray .filter(includeElements.contains) // O(n) due to O(1) (amortized) .contains lookup 

C）在O(n) ，使用顺序和重复，因为他们发生在secondArray ：

 let includeElements = Set(firstArray) // O(n) let commonElements = secondArray .filter(includeElements.contains) // O(n) due to O(1) (amortized) .contains lookup 

---

性能？

以上只看渐进时间复杂度，并没有考虑到任何实际的基准。 通常，诸如filter之类的函数方法比for或while循环要慢，所以如果性能成为您的应用程序的问题，那么您应该考虑执行性能分析以及自定义基准testing，以确定algorithm中可能出现的瓶颈。

此外，如果您的数组已知被sorting，则有更有效的方法来遍历它们并筛选出结果。 看例如下面的线程（C语言，但逻辑是重要的部分）：

• 在两个不同大小的数组中寻找共同的元素