拥抱算法 (Embracing Algorithms) 上

2019-02-19 本文已影响15人 FicowShen

Algorithm

算法:

在计算或其他解决问题的操作中要遵循的一个或一组规则，特别是通过计算机：一种基本的划分算法。

现在，请假设你正在构建这样一个App：

示例App

你可以选中画布中的某几个图形(view)，然后对这些图形所在的图层进行多种操作。
比如：将图层向前、向后移动、删除图层等等。

会导致数组越界错误的删除算法

你是否会这样删除数组中的元素呢？ (好吧，很早以前我确实这样写过...... -_-+)
事实上，上面的写法会导致数组越界错误（Fatal error: Index out of range）

为什么？
因为在0..<shapes.count处，for循环的range值就已经确定了。
所以当shapes的元素个数减少时，就会出现索引值超过数组元素容量个数的问题，最终导致越界错误。

不会导致数组越界错误，但是有bug的删除算法

改成while之后，可以避免崩溃问题。因为我们知道while在每次循环开始时，都会去判断循环开始的条件是否成立。
但是，这样做会产生bug，而且这个bug不容易立刻被发现！

删除两个连续的元素

因为每次循环i都会加1，所以删除连续的元素中的第一个元素时，i也会加1。
然而，这一次加1就会导致待删除的连续元素中的第二个元素被跳过。

没有bug，但是低效的删除算法

更改if部分的逻辑后，可以解决上述问题。

当然，你也可以这样写：

image.png

好像可以完美地完成删除多个元素的任务了。
但是，这个算法的效率(主要考虑时间复杂度)如何呢？

remove(at:)方法的文档

remove(at:)方法的时间复杂度

时间复杂度常用大O符号来表示，描述一个函数数量级的渐近上界。

首先，外层for在遍历数组时的时间复杂度是O(n)。
然后，根据文档可以知道remove(at:)方法的时间复杂度也是O(n)。
那么，这个方法整体的时间复杂度就是O(n^2)了！！！ Amazing!!!

O(n^2)

如果你的数组有1000、10000个元素，那么。。。结果完全可以想象！
你的程序将会变得很低效！

那么，你现在该怎么办？

removeAll(where:)方法

removeAll(where:)方法的文档

removeAll(where:)方法的时间复杂度

这也许就是你想要的，removeAll(where:)方法的时间复杂度仅为O(n) ！！！

我们来对比一下不同时间复杂度O(n)和O(n^2)之间的差别：

image.png

你现在一定很好奇removeAll(where:)方法内部的算法为什么能够如此高效？

removeAll(where:)方法的实现

需要注意的是，这个方法在MutableCollection的扩展中，而且方法被标记为mutating。
所以，待操作的集合一定是可变的！

接下来，看一下halfStablePartition(isSuffixElement:)的实现，这里才是高效率的关键部分：

halfStablePartition(isSuffixElement:)的实现

formIndex(after:)方法用于改变索引的值，将索引位置向后移动。
显然，halfStablePartition(isSuffixElement:)方法的复杂度仅为O(n)。

至此，你也知道了标准库的强大。
所以，可以多花点时间去了解一下Swift Standard Library。

参考文章：
Embracing Algorithms