作者：Soroush Khanlou，原文链接，原文日期：2018-12-17
译者：RocZhang；校对：numbbbbb，WAMaker；定稿：Pancf

在 Dave Abraham 的 WWDC 演讲 Embracing Algorithms（拥抱算法）中，谈到了要发现通用的算法，并将其提取到通用且可测试的函数中。在这个方向上，我发现一些对集合类型的多次操作可以被聚齐起来，合并成单次操作。并且通常情况下，这些操作被合并之后还能带来性能上的收获。

第一个例子是 Swift 3 添加的一个方法:

// 当你看到:
myArray.filter({ /* some test */ }).first

// 你应该把它改成:
myArray.first(where: { /* some test */ })

这里两种写法的断言描述闭包和操作结果都完全相同，但下面的写法更简短，语义更清晰，而且性能更好。因为它不会进行新数组的分配，也不需要对数组中每一个元素是否能够通过测试都进行判断，只需要找出第一个就好了。

另一个例子是 我帮助添加到 Swift 5 中的 count(where:) 函数:

// 当你看到:
myArray.filter({ /* some test */ }).count

// 你应该把它改成:
myArray.count(where: { /* some test */ })

这又是一个更短、更清晰而且更快的例子。没有额外要被分配的数组，也没有多余的操作。

在我们的一个项目中，有一个通用的范式，需要先将集合进行 sort，随后再进行 prefix 操作。例如下述的示例代码，需要找出前 20 张最新创建的图像：

return images
    .sorted(by: { $0.createdAt > $1.createdAt })
    .prefix(20)

同样，也可以想象成在排行榜中找到前 5 位得分最高的用户，也需要使用这类范式。

我盯着这段代码直到我的眼睛开始流血，感到这段代码可能存在问题。我首先想到的是分析它的时间复杂度。如果把原始数组的长度用 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 和用于排序做比较的闭包：

func smallest(_ m: Int, by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element] {

首先从排序前 m 个元素开始（因为 m 比序列的总长度要小很多，所以此操作会进行的很快）：

var result = self.prefix(m).sorted(by: areInIncreasingOrder)

然后我们再遍历所有剩下的元素：

for element in self.dropFirst(m) {

对集合中剩下的每一个元素，我们需要找到 result 中第一个比它大的项的索引。通过 areInIncreasingOrder 函数，我们把 element 作为第一个参数传入，再把 result 中的元素作为第二个参数传入。

if let insertionIndex = result.index(where: { areInIncreasingOrder(element, $0) }) { // 译者注：此方法在 Swift 4.2 后已更名为 `firstIndex(where:)`

如果能够找到符合条件的索引值，这就表示存在有比我们 result 数组中的元素更小的值。我们把新的值插入到计算出的索引的位置，它便会被正确的排序：

result.insert(element, at: insertionIndex)

再将最后一个元素移除（因为我们只需要 m 个元素）：

result.removeLast()

如果没有找到满足条件的索引，我们就可以忽略这个值。最后，当 for 循环完成，便可将 result 返回。

完整的函数如下所示：

extension Sequence {
    func smallest(_ m: Int, by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element] {
        var result = self.prefix(m).sorted(by: areInIncreasingOrder)
        
        for e in self.dropFirst(n) {
            if let insertionIndex = result.index(where: { areInIncreasingOrder(e, $0) }) {
                result.insert(e, at: insertionIndex)
                result.removeLast()
            }
        }
        
        return result
    }
}

如果这让你想起了之前在计算机科学中学过的课程，那就再好不过了。实际上这里的算法就类似于选择排序的过程（但它们并非完全相同，因为这里会预先排序一部分元素，而选择排序则不同，是可变序列算法（mutating algorithm））。

这里的时间复杂度分析起来可能会有些困难，但是我们还是可以尝试进行分析。初始部分的排序是 O(mlogm)，外层的循环是 O(n)。每次的循环中，会分别调用时间复杂度都为 O(m) 的 index(where:) 和 insert(_:at:)（插入操作的时间复杂度是 O(m) 的原因在于，它可能需要将所有的元素后移，为新元素腾出空间）。因此，总时间复杂度应为 O(mlogm + n * (m + m))，或者说 O(mlogm + 2nm)。常数项被移除后，留下的则是 O(mlogm + nm)。

当 m 比 n 小得多时，m 项会接近于常数，最终我们得到的会是 O(n)。相较于之前的 O(nlogn) 而言，这是一个巨大的改进。对应到之前提到的 55000 张图片的例子，这可能会是多达 5 倍的性能提升。

大体上来说，这里的函数是对 prefix + sort 函数的优化。但我还想要再讨论两处更细小一些的优化。

一处唾手可得的优化是：我们是在 55000 个元素的数组中查找 20 个最小的元素，其中我们检查的大部分（几乎是全部）元素不会落入到最后的 result 数组中。因此我们可以去检查元素是否比 result 数组中的最后一个元素要大，如果是，它就完全可以被跳过。因为当元素比 result 中的最后一个还要大时，再去查找插入的索引就没有任何意义了。

if let last = result.last, areInIncreasingOrder(last, e) { continue }

在测试中，此处增加的判断可以减少线性搜索 result 数组 99.5% 的时间，算法整体上又会加快十倍左右。感谢 Greg Titus 告诉我此处可以优化──之前我完全没有想到这一点。

如果想更近一步的话，还可以做另一处（稍微难实现一些）的优化。此优化基于两处事实：第一，我们使用 index(where:) 来找出应在 result 数组中进行插入的位置；第二，result 数组总是保持有序的。index(where:) 通常情况下是一项线性操作，但如果是在一个已经排好序的数组中进行搜索，我们可以将线性搜索替换成二分搜索。我对此进行了尝试。

为了能够更好的理解这些优化会如何影响算法的性能，Nate Cook 帮助我了解了 Karoy Lorentey 的 Attabench 工具，它能够对这些解决方案进行基准测试。因为截止目前，我们对复杂度的分析都是停留在理论层面的，在真正对代码进行实际测试之前（最理想的情况应该是在真实的设备上），所有的结论都只是有根据的推测。例如，通常来说排序的复杂度为 O(nlogn)，但不同的算法处理不同类型的数据时，其表现也会有所不同。具体来说，已经排好序的数据在特定的算法中可能会变得更快或更慢。

Attabench 的执行结果如下：

（我还添加了一个 由 Time Vermuelen 所写的优先队列/堆解决方案，因为有些人好奇它与其他方案比较起来表现如何。）

首先，我对在数组中进行单次搜索比对数组进行完整排序要快的猜测是正确的。尤其是在实际问题中序列可能会很长，排序的性能则会变得更差，但我们的“简单优化”（图中的 “Naive Optimization”）却能保持在常数水平上（Y 轴表示的是单个元素上所花的时间，而不是总时间。这意味着 O(n) 的算法在图中会是一条直线）。

第二，对最后一个元素的检查（图中的 “Last Check”）和二分搜索优化在独立运行时具有几乎完全相同的性能表现（实际上你可能没法看到橘色和黄色的线，因为它们被绿线挡住了），把它们放在一起使用时也是一样。但是由于二分搜索难以编写，甚至更难把它写对，你也可以说把它加上是不值得的。

对我而言，这里传递出的关键信息是测量和优化很难。虽然分析复杂度这件事听起来有些学术：“我什么时候会在自己的职业生涯上用到这个？” 有人会问。但理解你的算法的时间和空间复杂度能够帮助你决定向哪个方向进行探索。在这个例子中，理解排序的时间复杂度引导我们对问题产生了概括性的认知，得到成果。最后，通过使用各种数据进行的进一步的基准测试与分析，能告诉我们代码在生产环境下将如何运作的最准确的信息。

下一次再看到 sort 后面紧跟着一个 prefix 时，不妨考虑将它替换成 smallest(_: by:)？

本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问 http://swift.gg。

作者：Soroush Khanlou，原文链接，原文日期：2018-11-14
译者：郑一一；校对：numbbbbb，pmst；定稿：Forelax

Foundation 框架中的 URL 类提供了非常全面的功能，此后还在 iOS 7 中新增了 URLSession 类。尽管如此，基础库中仍然缺少 multipart 文件上传的功能。

什么是 multipart 请求？

Multipart 编码实际上就是在网络中上传大型文件的方法。在浏览器中，有时候你会选择一个文件作为表单提交内容的一部分。这个文件便是以 multipart 请求的方式实现上传的。

乍一看，multipart 请求和一般请求差不多。不同之处是 multipart 请求额外为 HTTP 请求体指定了唯一编码。同 JSON 编码（{"key": "value"}）或者 URL 字符编码 (key=value) 相比，multipart 编码干的事略微有所不同。因为 multipart 请求体实际上只是一串字节流，接收端实体在解析数据时，需要知道字节流中各个部分之间的界限。所以 multipart 请求需要使用 “boundaries” 来解决这个问题。在请求首部的 Content-Type 中，可以定义 boundary：

Accept: application/json
Content-Type: multipart/form-data; boundary=khanlou.comNczcJGcxe

Boundary 的具体内容并不重要，唯一需要注意的是：在请求体中，boundary 是不能重复出现（这样才能体现 boundary 的作用）。你可以使用 UUID 作为 boundary。

请求的每一部分可以是普通数据（比如图片）或者元数据（一般是文本，对应一个名字，组成一个键值对）。如果数据是图片的话，那它看起来应该是这样的：

--<boundary>
Content-Disposition: form-data; name=<name>; filename=<filename.jpg>
Content-Type: image/jpeg

<image data>

如果是普通文本，则是这样：

--<boundary>
Content-Disposition: form-data; name=<name>
Content-Type: text/plain

<some text>

请求结尾会有一个带着两个连字符的 boundary，--<boundary>--。（此处需要注意，所有新行必须是回车换行。）

以上就是关于 multipart 请求的所有内容，并不是特别复杂。事实上，当在写第一个有关 multipart 编码的客户端实现时，我有些抵触阅读 multipart/form-data 的 RFC。可是在开始阅读之后，我对这个协议的理解更深了。整个文档可读性很强，很轻易就能直达知识的源头。

我在开源的 Backchannel SDK 实现了上述功能。BAKUploadAttachmentRequest 和 BAKMultipartRequestBuilder 类包含了处理 mulitipart 的方法。在这个项目中，仅仅包含了处理单个文件的情况，并且没有包括元数据。但是作为范例，依旧很好地展示了 mulitipart 请求是如何构建的。可以通过添加额外的实现代码，来支持元数据和多文件的功能。

无论是使用一个请求上传多个文件，还是多个请求分别对应上传一个文件，来实现多文件上传功能，都会碰到一个问题。这个问题就是，如果你尝试一次性上传很多文件的话，app 将会闪退。这是因为使用 该版本的代码，加载的数据会直接进入内存，在内存暴涨的情况下，即使使用当下性能最强的旗舰手机也会有闪退发生。

将硬盘中数据以流的形式读取

最常见的解决方法是将硬盘中的数据以流的形式读取出来。其核心思想是文件的字节数据会一直保存在硬盘里，直到被读取并发往网络。内存中只保留了很小一部分的镜像数据。

目前，我想出两种方法可以解决这个问题。第一个方法，把 multipart 请求体中的所有数据写到硬盘的一个新文件中，并使用 URLSession 的 uploadTask(with request: URLRequest, fromFile fileURL: URL) 方法将文件转化为流。这个方法可以奏效，但我并不想为每一个请求新建一个新文件保存到硬盘中。因为这意味着在请求发出后，还需要删除这个文件。

第二种方法是将内存和硬盘的数据合并在一起，并通过统一的接口向网络输出数据。

如果你觉得第二种方法听起来像是 类簇，恭喜你，完全正确。很多常用 Cocoa 类都允许创建子类，并实现一些父类方法，使其和父类表现一致。回想一下 NSArray 的 -count 属性和 -objectAtIndex: 方法。因为 NSArray 的所有其它方法都是基于 -count 属性和 -objectAtIndex: 方法实现的，你可以非常轻易地创建优化版本的 NSArray 子类。

你可以创建一个 NSData 子类，它无需真正从硬盘读取数据，而只是创建一个指针直接指向硬盘中的数据。这样做的好处是是不需要把数据载入内存中进行读取。这种方法称为内存映射，基于 Unix 方法 mmap。你可以通过 .mappedIfSafe 或者 alwaysMapped 选项，来使用 NSData 的这项特性。因为 NSData 是一个类簇，我们将创建一个 ConcatenatedData 子类（就像 FlattenCollection 在 Swift 中的工作方式），该子类会将多个 NSData 对象视作一个连续的 NSData。完成创建以后，我们就做好所有准备来解决这个问题啦。

通过查看 NSData 所有原生方法，可以发现，需要实现的是 -count 和 -bytes。实现 -count 并不难，我们可以把所有 NSData 对象的大小相加得到；但在实现 -bytes 时则会有个问题。 -bytes 需要返回一个指向一段连续缓冲区的指针，而目前我们并没有这个指针。

在基础库中，提供了 NSInputStream 类用于处理不连续的数据。非常幸运，NSInputStream 同样是一个类簇。我们可以创建一个子类，将多条流合并。在使用子类时，感觉上就像是一条流。通过使用 +inputStreamWithData: 和 +inputStreamWithURL: 方法，可以轻易地创建一条输入流，用来代表硬盘中的文件和内存中的数据（比如 boundaries）。

通过阅读最好的第三方网络库源代码，你会发现 AFNetworking 采用了这种方法。（Alamofire，Swift 版本的 AFNetworking，则采用了第一种方法，将数据全部加载到内存中，但如果数据量太大，就会写到硬盘的一个文件中。）

将所有部分拼接起来

你可以在 这里 看看我的串行输入流的实现（是用 Objective-C 实现的，以后我可能还会写一个 Swift 版本的）。

通过 SKSerialInputStream 类，可以将流组合在一起。下面展示了前缀和后缀属性：

extension MultipartComponent {
    var prefixData: Data {
        let string = """
        \(self.boundary)
        Content-Disposition: form-data; name="\(self.name); filename="\(self.filename)"
        """
        return string.data(using: .utf8)
    }
    
    var postfixData: Data {
        return "\r\n".data(using: .utf8)
    }
}

将元数据和文件的 dataStream 组合在一起，得到一条输入流：

extension MultipartComponent {
    var inputStream: NSInputStream {
        
        let streams = [
            NSInputStream(data: prefixData),
            self.fileDataStream,
            NSInputStream(data: postfixData),
        ]
    
        return SKSerialInputStream(inputStreams: streams)
    }
}

创建好每一部分输入流之后，就可以把所有流组合在一起，得到一条完整输入流。此外，在请求结尾还需要添加一个 boundary：

extension RequestBuilder {
    var bodyInputStream: NSInputStream {
        let stream = parts
            .map({ $0.inputStream })
            + [NSInputStream(data: "--\(self.boundary)--".data(using: .utf8))]
    
        return SKSerialInputStream(inputStreams: streams)
    }
}

最后，将 bodyInputStream 赋值给 URL 请求的 httpBodyStream 属性：

let urlRequest = URLRequest(url: url)

urlRequest.httpBodyStream = requestBuilder.bodyInputStream;

注意，httpBodyStream 和 httpBody 两个属性是互斥的——两个属性不会同时生效。设置 httpBodyStream 会使得 Data 版本 httpBody 失效，反之亦然。

流文件上传的关键是能够将多条输入流合并成一条流。SKSerialInputStream 类完成了整个工作。尽管说子类化 NSInputStream 有一些困难，可一旦解决这个问题，我们就离成功不远啦。

子类化过程中需要注意的问题

子类化 NSInputStream 的过程不会太轻松，甚至可以说很困难。你必须实现 9 个方法。其中的 7 个方法，父类只有一些微不足道的默认实现。而在文档中只提到了 9 个方法中的 3 个，所以你还得实现 6 个 NSStream （NSInputStream 的父类）的方法，其中有 2 个是 run loop 方法，并允许空实现。在这之前，你还需要额外 实现 3 个私有方法，不过现在不必实现了。此外，还需要定义 3 个只读属性：streamStatus，streamError，delegate。

在处理完上述子类化相关的细节后，接下来的挑战是创建一个 NSInputStream 子类，其行为应该和 API 使用者所期望的保持一致。然而，这个类状态的重度耦合是不容易被人发现的。

有一些状态需要保证行为一致。举个例子，hasBytesAvailable 是不同于其它状态的，但还是存在细微的联系。在我最近发现的一个 bug 里，hasBytesAvailable 属性会返回 self.currentIndex != self.inputStreams.count，但是这会造成一个 bug，流会一直处于开启的状态，并最终造成请求超时。修复这个 bug 的办法是改为返回 YES，但我一直没有找到这个 bug 的根源所在。

另外一个状态 streamStatus，存在许多可能的值，其中比较重要的两个值是 NSStreamStatusOpen 和 NSStreamStatusClosed。

最后一个比较有意思的状态是字节数，从 read 方法中返回值。这个属性除了会返回正整型数之外，还会返回 -1，-1 代表有错误产生，需要进一步检查非空属性 streamError 来获取更多信息。字节数还可以返回 0，根据文档描述，这是标明流结尾的另外一种方式。

文档并不会告诉你哪些状态的组合是有意义的。比如说流产生一个 streamError，但状态却是 NSStreamStatusClosed，而不是 NSStreamStatusError，在这种情况下是否会有问题？想要管理好所有的状态非常难，不过到最后终究还是能解决的。

对于 SKSerialStream 类，是否可以在所有情况下都能正常工作，我还不是特别有信心。但看起来，SKSerialStream 通过使用 URLSession 能很好地支持上传 multipart 数据。如果你在使用这份代码的时候发现任何问题，请务必联系我，我们可以一起不断优化这个类。

本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问 http://swift.gg。

作者：Soroush Khanlou，原文链接，原文日期：2018-09-07
译者：Nemocdz；校对：Yousanflics，pmst；定稿：Forelax

回想 Crusty 教我们使用面向协议编程之前的日子，我们大多使用继承来共享代码的实现。通常在 UIKit 编程中，你可能会用 UIView 的子类去添加一些子视图，重写 -layoutSubviews，然后重复这些工作。也许你还会重写 -drawRect。但当你需要做一些特别的事情时，就需要看看 UIView 中其他可以被重写的方法。

UIKit 有个十分古怪的地方，那是它的触摸事件处理系统。它主要包括两个方法，-pointInstide:withEvent: 和 -hitTest:withEvent:。

-pointInside: 会告诉调用者给定点是否包含在指定的视图区域中。而 -hitTest: 用 pointInside: 这个方法来告诉调用者哪个子视图（如果有的话）是当前触摸在给定点的接收者。现在我比较感兴趣的是后面这个方法。

苹果的文档勉强能够让你理解怎么重新实现这个方法。在你学会怎么重新实现方法之前，你都不能改变它的功能。接下来让我们看一遍 文档，并尝试重写这个函数。

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {
// ...
}

首先，让我们从文档的第二段开始吧：

这个方法会忽略那些隐藏的视图，禁用用户交互视图和 alpha 等级小于 0.01 的视图。

让我们通过一些 gurad 语句来快速预处理这些前提条件。

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {

guard isUserInteractionEnabled else { return nil }

guard !isHidden else { return nil }

guard alpha >= 0.01 else { return nil }

// ...

相当简单吧。那接下来是？

这个方法调用 pointInside:withEvent: 方法来遍历接收视图层级中每一个子视图，来决定哪个子视图来接收该触摸事件。

逐字阅读文档后，感觉 -pointInside: 会在每一个子视图里被调用（用一个 for 循环），但这并不是完全正确的。

感谢这个 读者。通过他在 -hitTest: 和 -pointInside: 中放置了断点的试验，我们知道 -pointInside: 会在 self 中调用（在有上面那些 guard 的情况下），而不是在每一个子视图中。 所以应该添加另外的 guard 语句，像下面这行代码一样：

guard self.point(inside: point, with: event) else { return nil }

-pointInside: 是 UIView 另一个需要重写的方法。它的默认实现会检查传入的某个点是否包含在视图的 bounds 中。如果调用 -pointInside 返回 true，那么意味着触摸事件发生在它的 bounds 中。

理解完这个小小的差别后，我们可以继续阅读文档了：

如果 -pointInside:withEvnet: 返回 YES，那么子视图的层级也会进行类似的遍历直到找到包含指定点的最前面的视图。

所以，从这里知道我们需要遍历视图树。这意味着循环遍历所有的视图，并调用 -hitTest: 在它们每一个上去找到合适的子视图。在这种情况下，这个方法是递归的。

为了遍历视图层级，我们需要一个循环。然而，这个方法其中一个更反人类的是需要反向遍历视图。子视图数组中尾部的视图反而会处在 Z 轴中更高的位置，所以它们应该被最先检验。（如果没有这篇 文章，我可记不起这个点。）

// ...
for subview in subviews.reversed() {

}
// ...

传入的坐标点会转换到当前视图的坐标系中，而非我们关心子视图中。幸运的是，UIKit 给了一个处理函数，去转换坐标点的参考系到其他任何的视图的 frame 的参考系中。

// ...
for subview in subviews.reversed() {
let convertedPoint = subview.convert(point, from: self)
// ...
}
// ...

一旦有了转换后的坐标点，我们就可以很简单地询问每一个子视图该点的目标视图。需要注意的是，如果点处于该视图外部（也就是说，-pointInside: 返回 false），-hitTest 会返回 nil。这时就应该检查层级里的下一个子视图。

// ...
let convertedPoint = subview.convert(point, from: self)
if let candidate = subview.hitTest(convertedPoint, with: event) {
return candidate
}
//...

一旦我们有了合适的循环语句，最后一件需要做的事是 return self。如果视图是可被点击（被我们的 guard 语句断言过的情况），但却没有子视图想要处理这个触摸的话，意味着当前视图，也就是 self，是这个触摸正确的目标。

这是完整的算法：

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {

guard isUserInteractionEnabled else { return nil }

guard !isHidden else { return nil }

guard alpha >= 0.01 else { return nil }

guard self.point(inside: point, with: event) else { return nil }

for subview in subviews.reversed() {
let convertedPoint = subview.convert(point, from: self)
if let candidate = subview.hitTest(convertedPoint, with: event) {
return candidate
}
}
return self
}

现在我们有了一个参考的实现，可以开始修改它来实现具体的行为。

在之前的这篇播客《Changing the size of a paging scroll view》中，我就已经讨论过其中一种行为。我谈到一种“落后并该被废弃”的方法来产生这种效果。本质上，你必须：

1. 关掉 clipsToBounds
2. 在滑动区域中放一个非隐藏视图
3. 在非隐藏视图上重写 -hitTest: 来传递所有触摸到 scrollview 中

-hitTest: 方法是这种技术的基石。因为在 UIKit 中，hitTest 方法会代理给每一个视图去实现，决定触摸事件传递给哪个视图接收。这可以让你去重写默认的实现（期望和普通的实现）并替换它为你想做的，甚至返回一个不是原始视图的子视图。多么疯狂。

让我们看一下另一个例子。如果你已经用过 Beacon 今年的版本，你会注意到滑动删除事件行为的物理效果感觉上和其他用原生系统实现的效果有点不一样。这是因为用系统的途径不能完全获得我们想要的表现，所以需要自己重新实现这个功能。

如你所想，重写滑动和反弹物理效果不需要那么复杂，所以我们用一个 UIScrollView 和将 pagingEnabled 设为 true 来获得尽可能自由的反弹力。用和这篇旧博客里说的类似的技术，将滑动的视图的 bounds 设置得更小一些并将 panGestureRecognizer 移到事件的 cell 顶层的一个覆盖视图中，来设置一个自定义页面大小。

然而，当覆盖视图正确的传递触摸事件到 scroll view 时，那里会有覆盖视图不能正确拦截的其他事件。cell 包含着按钮，像 “join event” 按钮和 “delete event” 按钮，都需要接收触摸。有几种自定义实现在 -hitTest: 中可以处理这种情况，其中一种实现就是直接检查这两个按钮的子视图：

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {

guard isUserInteractionEnabled else { return nil }

guard !isHidden else { return nil }

guard alpha >= 0.01 else { return nil }

guard self.point(inside: point, with: event) else { return nil }

if joinButton.point(inside: convert(point, to: joinButton), with: event) {
return joinButton
}

if isDeleteButtonOpen && deleteButton.point(inside: convert(point, to: deleteButton), with: event) {
return deleteButton
}
return super.hitTest(point, with: event)
}

这种方法会正确地传递正确的点击事件到正确的的按钮中，而且不用打断显示删除按钮的滑动表现。（你可以尝试只忽略 deletionOverlay，不过它不会正确的传递滑动事件。）

-hitTest: 是视图中一个很少重写的地方，但是在需要时，可以提供其他工具很难做到的行为。理解如何自己实现有助于随意替换它。你可以用这个技术去扩大点击的目标区域，去除触摸处理中的某些子视图，而不用把它们从可见的层级中去掉，又或是用一个视图作为另一个将响应触摸的视图的兜底。所有东西都是可能的。

本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问 http://swift.gg。

作者：Soroush Khanlou，原文链接，原文日期：2018-09-19
译者：WAMaker；校对：numbbbbb，小铁匠Linus；定稿：Forelax

Swift 4.2 为哈希的实现带来了一些新的变化。在此之前，哈希交由对象本身全权代理。当你向对象索取 哈希值（hashValue）时，它会把处理好的整型值作为哈希值返回。而现在，实现了 Hashable 协议的对象则描述了它的参数是如何组合，并传递给作为入参的 Hasher 对象。这样做有以下几点好处：

• 写出好的哈希算法很难。Swift 的使用者不需要知道如何组合参数来获得更好的哈希值。
• 出于不提倡用户以任何形式存储哈希值，以及 一些安全方面因素 的考虑，哈希值在程序每次运行的时候都应该有所不同。描述性的哈希允许哈希函数的种子在每次程序运行的时候发生改变。
• 能实现更多有意思的数据结构，这也是我们这篇文章接下来会聚焦的。

我之前写过一篇关于 如何使用 Swift 的 Hashable 协议从零实现 Dictionary 的文章（先阅读它会帮助你阅读本文，但这不是必须的）。今天，我想谈论一种不同类型的，基于概率性而非明确性的数据结构：布隆过滤器（Bloom Filters）。我们会使用 Swift 4.2 的新特性，包括新的哈希模型来构建它。

布隆过滤器很怪异。想象这样一种数据结构：

• 你能够往里插入数据
• 你能够查询一个值是否存在
• 只需要少量存储资源就能存储大量对象

但是：

• 你不能枚举其中的对象
• 它有时会出现误报（但不会出现漏报）
• 你不能从中移除数据

什么时候会想要这种数据结构呢？Medium 使用它们来 跟踪博文的阅读状态。必应使用它们做 搜索索引。你可以使用它们来构建一个缓存，在无需访问数据库的情况下就能判断用户名是否有效（例如在 @-mention 中）。像服务器这样可能拥有巨大的规模，却不一定有巨大资源的场景中，它们会非常有用。

（如果你之前做过图形方面的工作，可能好奇它是如何与 高光过滤器) 产生联系的。答案是没有联系。高光过滤器（bloom filters）是小写的 b，而布隆过滤器（Bloom Filters）是由一个叫布隆的人命名的。完全是个巧合。）

那它们是如何运作的呢？

将对象放入布隆过滤器如同将它放入集合或字典：计算对象的哈希值，并根据存储数组的大小对哈希值求余。就这点而言，使用布隆过滤器只需要修改该索引处的值：将 false 改为 true，而不用像使用集合或字典那样，把对象存放到索引位置。

我们先通过一个简单的例子来理解过滤器是如果运作的，之后再对它进行扩展。想象一个拥有 8 个 false 值的布尔数组（或称之为 比特数组）：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   |   |   |   |

它代表了我们的布隆过滤器。我想要插入字符串“soroush”。它的哈希值是 9192644045266971309，当这个值余 8 时得到 5。我们修改那一位的值。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   | * |   |   |

接下来我想要插入字符串“swift”，它的哈希值是 7052914221234348788，余 8 得 4，修改索引 4 的值。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   | * | * |   |   |

要测试布隆过滤器是否包含“soroush”，我再次计算它的哈希值并求余，仍旧得到余数 5，对应值是 true。“soroush”确实在布隆过滤器中。

然而仅仅测试能够通过的用例是不够的，我们需要写一些会导致失败的用例。测试字符串“khanlou”取余得到的索引值是 2，因此我们知道它不在布隆过滤器中。到此为止一切都好。接下去一个测试：对“hashable”字符串取余得到的索引值是 5，这就发生了一次冲突！即使这个值从来没有被加入过，过滤器仍返回了 true。这便是布隆过滤器会发生误报的例子。

有两个主要的策略可以尽可能减少误报。第一个策略，也是两个策略中相对有趣的：我们可以使用不同的哈希函数计算两次或三次哈希值而非一次。只要它们都是表现良好的哈希函数（均匀分布，一致性，最小的碰撞几率），我们就能为每个值生成多个索引改变布尔值。这次，我们计算两次“soroush”的哈希值，生成 2 个索引并改变布尔值。这时，当我们检查“khanlou”是否在布隆过滤器中，其中一个哈希值可能会和“soroush”的一个哈希值冲突，但两个值同时发生冲突的可能性就会变得很小。你可以把这个数字扩大。在下面的代码我会做 3 次哈希计算，但你可以做更多次。

当然，如果你计算更多次哈希值，每个元素在布尔数组中会占据更多的空间。事实上，现在的数据几乎不占用空间。8 个布尔值的数组对应 1 字节。所以第二个减小误报的策略是扩大数组的规模。我们能将数组变得足够大而不用担心它的空间消耗。下面的代码中我们会默认使用 512 比特大小的数组。

现在，即使同时使用这些策略，你依然会得到冲突，即误报，但冲突的几率会减小。这是布隆过滤器的一个缺陷，但在合适的场景用它来节省速度与空间是一笔不错的交易。

在开始具体的代码之前我有另外三点想要谈谈。首先，你不能改变布隆过滤器的大小。当你对哈希值取余时，这是在破坏信息，在不保留原始哈希值的情况下你不能回溯之前的信息 —— 保留原始值相当于否决了这个数据结构节约空间的优势。

其次，你能看到想要枚举布隆过滤器所有的值是多么异想天开。你不再拥有这些值，只是它们以哈希形式存在的替代品。

最后，你同样能看到想要从布隆过滤器中移除元素是不可能的。如果想将布尔值变回 false，你并不知道是哪些值将它变为 true。是准备移除的值还是其它值？这样做会造成漏报和误报。（这对你来说可能是值得权衡的）你可以在每个索引上保留计数而非布尔值来解决这个问题，虽然保留计数还是会带来存储问题，但根据使用场景的不同，这样做或许是值得的。

废话不多说，让我们开始着手编码。我在这里做的一些决策和你可能会做的有所不同，第一个不同就是要不要让对象支持范型。我认为让对象包含更多关于它需要存储内容的元数据是有意义的，但如果你发现这样做限制太多，你可以改变它。

struct BloomFilter<Element: Hashable> {
// ...
}

我们需要存储两种主要的数据。第一个是 data，用于表示比特数组。它存储了所有和哈希值有关的标记：

private var data: [Bool]

接下来，我们需要不同的哈希函数。一些布隆过滤器确实会使用不同的方法计算哈希值，但我觉得使用相同的算法，同时混入一个随机生成的值会更简单。

private let seeds: [Int]

当初始化布隆过滤器时，我们需要初始化这两个实例变量。比特数组会简单的重复 false 值来初始化，而种子值则使用 Swift 4.2 的新 API Int.random 来生成我们需要的种子值。

init(size: Int, hashCount: Int) {
data = Array(repeating: false, count: size)
seeds = (0..<hashCount).map({ _ in Int.random(in: 0..<Int.max) })
}

同时，创建一个带有默认值的便利构造器。

init() {
self.init(size: 512, hashCount: 3)
}

我们要实现两个主要的方法：insert 和 contains。它们都需要接收元素作为参数并为每一个种子值计算出对应的哈希值。私有的帮助方法会很有用。由于种子值代表了“不同的”哈希函数，我们就需要为每一个种子生成对应的哈希值。

private func hashes(for element: Element) -> [Int] {
return seeds.map({ seed -> Int in
// ...
})
}

要实现函数主体，我们需要创建一个 Hasher 对象（Swift 4.2 新特性），将想要进行哈希计算的对象传给它。带上种子确保了生成的哈希值不会冲突。

private func hashes(for element: Element) -> [Int] {
return seeds.map({ seed -> Int in
var hasher = Hasher()
hasher.combine(element)
hasher.combine(seed)
let hashValue = abs(hasher.finalize())
return hashValue
})
}

同时，注意哈希值的绝对值。哈希计算有可能产生负数，这会导致我们的数组访问崩溃。取绝对值操作减少了 1 比特的信息熵，对我们来说是有益的。

理想的情况是你能够使用种子来初始化 Hasher 而不是把它混合进去。Swift 的 Hasher 会在每次程序启动的时候被分配一个不同的种子（除非你 设置固定的环境变量 让种子在不同启动间保持一致，而这样做通常是一些测试目的），意味着你不能把这些值写到磁盘上。如果我们控制了 Hasher 的种子，我们就能将这些值写到磁盘上了。而就像这个布隆过滤器展示的那样，它应该只被用于内存缓存。

hashes(for:) 方法完成了很多繁重的工作，让 insert 方法非常简洁：

mutating func insert(_ element: Element) {
hashes(for: element)
.forEach({ hash in
data[hash % data.count] = true
})
}

生成所有的哈希值，分别余上 data 数组的长度，并设置对应索引位的值为 true。

contains 方法也同样简单，同时也给了我们使用 Swift 4.2 另一个新特性 allSatisfy 的机会。这个新方法可以判断序列中的所有对象是否都通过了某项用 block 表示的测试：

func contains(_ element: Element) -> Bool {
return hashes(for: element)
.allSatisfy({ hash in
data[hash % data.count]
})
}

因为 data[hash % data.count] 的结果已经是布尔值了，它与 allSatisfy 十分契合。

你也可以添加 isEmpty 方法用来检测 data 中的所有值是否都是 false。

布隆过滤器是一种奇怪的数据结构。我们接触的大多数数据结构都是明确性的。当把一个对象放入字典中时，你知道那个值之后一直在那儿。而布隆过滤器是概率性的，牺牲确定性来换取空间和速度。布隆过滤器不是你会每天用的数据结构，但当你确实需要它时，就会感受到有它真好。

本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问 http://swift.gg。