我盯着这段代码直到我的眼睛开始流血，感到这段代码可能存在问题。我首先想到的是分析它的时间复杂度。如果把原始数组的长度用 n 表示，再把最后想要得到的元素的数目用 m 表示，在分析代码之后可以得出，排序的复杂度是 O(nlogn)，取前子集合的操作则更快，时间复杂度为 O(1)（取前子集合操作本身最慢时可能会达到 O(m)，但对这里我们要处理的数组而言，由于它是可随机访问的集合，因此取前子集合操作能在常数时间中完成）。
这正是让我感到困惑的地方：获取一个序列的最小元素（使用 min() 函数）只需要单次遍历所有元素，或者说时间复杂度为 O(n)。将其所有元素进行完整排序需要的时间复杂度是 O(nlogn)。而从集合中获取 m 个数，当 m 比 n 小时，时间复杂度应该位于它们之间。且当 m 比 n 小非常多时，时间复杂度应该更接近 O(n)。
在我们的例子里，图片的数量会非常大（n 约为 55000），而我们想得到的元素数量却很小（m 为 20）。因此，这里应该存在有优化的空间。我们是否能够优化排序，使其仅排序出前 m 个元素？
答案是肯定的，我们能够在这个方向上进行一些优化。我将此函数命名为 smallest(_:by:)，它接收 sort 和 prefix 函数的所有参数，也就是上面提到的 m 和用于排序做比较的闭包：
一处唾手可得的优化是：我们是在 55000 个元素的数组中查找 20 个最小的元素，其中我们检查的大部分（几乎是全部）元素不会落入到最后的 result 数组中。因此我们可以去检查元素是否比 result 数组中的最后一个元素要大，如果是，它就完全可以被跳过。因为当元素比 result 中的最后一个还要大时，再去查找插入的索引就没有任何意义了。
iflet last = result.last, areInIncreasingOrder(last, e) { continue }
在测试中，此处增加的判断可以减少线性搜索 result 数组 99.5% 的时间，算法整体上又会加快十倍左右。感谢 Greg Titus 告诉我此处可以优化──之前我完全没有想到这一点。
如果想更近一步的话，还可以做另一处（稍微难实现一些）的优化。此优化基于两处事实：第一，我们使用 index(where:) 来找出应在 result 数组中进行插入的位置；第二，result 数组总是保持有序的。index(where:) 通常情况下是一项线性操作，但如果是在一个已经排好序的数组中进行搜索，我们可以将线性搜索替换成二分搜索。我对此进行了尝试。
var setE: Set = [1,2,3,4] setE.insert(5) setE.insert(5) setE.insert(5) print(setE) //[4,5,1,2,3]
和前面所说的一样，上面代码每次执行时输出的顺序可能不同，因为集合元素无序。
集合比较
集合间能进行比较。显然，可以比较两个集合是否相等：
let setA: = [“a”, “b”, “c”] let setB: = [“a”, “b”, “c”] if setA == setB { print(“the sets are equal”) }
这种情况下，集合是相等的。
比较两个集合的大小是没有明确的定义，但可以检查一个集合是否是另一个集合的子集：
let intSetA: Set = [1,2,3,4,5,6,7,8,9,0] let intSetB: Set = [1,2,3] intSetB.isSubset(of: intSetA) //true
也可以检查集合是否是另一个集合的真子集。这种情况就是该集合是另一个集合的子集但不想等。
let intSetA: Set = [1,2,3,4,5,6,7,8,9,0] let intSetB: Set = [1,2,3,4,5,6,7,8,9,0] let intSetC: Set = [3,4,5] intSetB.isSubset(of: intSetA) //true intSetB.isStrictSubset(of: intSetA) //false intSetC.isSubset(of: intSetA) // true intSetC.isStrictSubset(of: intSetA) //true
与之相对的概念就是超集：
let intSetA: Set = [1,2,3,4,5,6,7,8,9,0] let intSetC: Set = [3,4,5] intSetA.isSuperset(of: intSetC) //true intSetA.isStrictSuperset(of: intSetC) //true
如果两个集合没有相同的元素，那么就说这两个集合不相交
let intSetA: Set = [1,2,3,4,5,6,7,8,9,0] let intSetC: Set = [3,4,5] let intSetD: Set = [13,14,15] intSetA.isDisjoint(with: intSetC) //false intSetA.isDisjoint(with: intSetD) //true
集合结合
你可以将两个集合合并成为一个新集合，新的集合中包含两个集合中所有的元素：
let stringSetA: Set = ["a","b","c"] let stringSetB: Set = ["c","d","e"]
let unionSetAB = stringSetA.union(stringSetB) print(unionSetAB) //["d", "b", "c", "a", "e"]
另一方面，交集就是仅包含两个集合中共同的元素：
let stringSetA: Set = ["a","b","c"] let stringSetB: Set = ["c","d","e"] let intersectionAB = stringSetA.intersection(stringSetB) print(intersectionAB) //[“c”]
你也许注意到了，我们目前还没有实现队列的协议。当我们进行编码时，通常希望事物之间能保持相对分离。并且希望能创建出一个概览从而方便我们去进行查找。有些类可能会逐渐变得非常大，解决这种情况的方法之一是使用扩展作用域。这样，每一个扩展倾向于只做一个任务（比如去遵循一个协议，处理存储与初始化，又或是嵌套类的声明等），事后再去查找时就会容易很多。让我们在这里也尝试使用这种方式。首先，实现一个 Int 类型的私有扩展，这能够帮助我们执行一些预先定义好的索引计算:
privateextensionInt{ var leftChild: Int { return (2 * self) + 1 } var rightChild: Int { return (2 * self) + 2 } var parent: Int { return (self - 1) / 2 } }
这里的内容有点多，你也许会想多读上一两次。其中，最上面是我们先前在协议中所定义好的所有方法，下面则是一些私有的，仅在此类中可用的辅助方法。我已经为这些辅助方法加上了注释，以便你能快速的了解到它们是用来做什么的。此外，记得关注一下先前对 Int 的扩展在这里是如何被使用的。依我看来，这是非常简洁实用的设计。
登录
