算法时间复杂度：

在集合里数据量小的情况下时间复杂度对于性能的影响看起来微乎其微。但如果某个开发的功能是一个公共功能，无法预料调用者传入数据的量时，这个复杂度的优化显得非常重要了。

上图列出了各种情况的时间复杂度，比如高效的排序算法一般都是 O(n log n)。接下来看看下图：

图中可以看出 O(n) 是个分水岭，大于它对于性能就具有很大的潜在影响，如果是个公共的接口一定要加上说明，自己调用也要做到心中有数。当然最好是通过算法优化或者使用合适的系统接口方法，权衡内存消耗争取通过空间来换取时间。

下面通过集合里是否有某个值来举个例子：

那么 OC 里几种常用集合对象提供的接口方法时间复杂度是怎么样的。

NSArray / NSMutableArray

首先我们发现他们是有排序，并允许重复元素存在的，那么这么设计就表明了集合存储没法使用里面的元素做 hash table 的 key 进行相关的快速操作，。所以不同功能接口方法性能是会有很大的差异。

→ containsObject:，containsObject:，indexOfObject*，removeObject: 会遍历里面元素查看是否与之匹对，所以复杂度等于或大于 O(n)

→ objectAtIndex:，firstObject:，lastObject:，addObject:，removeLastObject: 这些只针对栈顶栈底操作的时间复杂度都是 O(1)

→ indexOfObject:inSortedRange:options:usingComparator: 使用的是二分查找，时间复杂度是 O(log n)

NSSet / NSMutableSet / NSCountedSet

这些集合类型是无序没有重复元素。这样就可以通过 hash table 进行快速的操作。比如 addObject:, removeObject:, containsObject: 都是按照 O(1) 来的。需要注意的是将数组转成 Set 时会将重复元素合成一个，同时失去排序。

NSDictionary / NSMutableDictionary

和 Set 差不多，多了键值对应。添加删除和查找都是 O(1) 的。需要注意的是 Keys 必须是符合 NSCopying。

containsObject 方法在数组和 Set 里不同的实现

在数组中的实现

可以看到会遍历所有元素在查找到后才进行返回.

接下来可以看看 containsObject 在 Set 里的实现：

找元素时是通过键值方式从 map 映射表里取出，因为 Set 里元素是唯一的，所以可以 hash 元素对象作为 key 达到快速获取值的目的。

用 GCD 来做优化

我们可以通过 GCD 提供的方法来将一些需要耗时操作放到非主线程上做，使得 App 能够运行的更加流畅响应更快。但是使用 GCD 时需要注意避免可能引起线程爆炸和死锁的情况，还有非主线程处理任务也不是万能的，如果一个处理需要消耗大量内存或者大量CPU操作 GCD 也没法帮你，只能通过将处理进行拆解分步骤分时间进行处理才比较妥当。

异步处理事件

上图是最典型的异步处理事件的方法

需要耗时长的任务

将 GCD 的 block 通过 dispatch_block_create_with_qos_class 方法指定队列的 QoS 为 QOS_CLASS_UTILITY。这种 QoS 系统会针对大的计算，I/O，网络以及复杂数据处理做电量优化。

避免线程爆炸

→ 使用串行队列

→ 使用 NSOperationQueues 的并发限制方法 NSOperationQueue.maxConcurrentOperationCount→

举个例子，下面的写法就比较危险，可能会造成线程爆炸和死锁

那么怎么能够避免呢？首先可以使用 dispatch_apply

或者使用 dispatch_semaphore

GCD 相关 Crash 日志

管理线程问题

线程闲置时

线程活跃时

主线程闲置时

主队列

I/O 性能优化

I/O 是性能消耗大户，任何的 I/O 操作都会使低功耗状态被打破，所以减少 I/O 次数是这个性能优化的关键点，为了达成这个目下面列出一些方法。

⒈将零碎的内容作为一个整体进行写入

⒉使用合适的 I/O 操作 API

⒊使用合适的线程

⒋使用 NSCache 做缓存能够减少 I/O

NSCache

达到如图的目的为何不直接用字典来做呢？

NSCache 具有字典的所有功能，同时还有如下的特性：

⒈自动清理系统占用内存

⒉NSCache 是线程安全

⒊-(void)cache:(NSCache *)cache willEvictObject:(id)obj; 缓存对象将被清理时的回调

⒋evictsObjectsWithDiscardedContent 可以控制是否清理

那么 NSCache是如何做到这些特性的呢？

接下来学习下 NSCache 是如何做的。首先 NSCache 是会持有一个 NSMutableDictionary。

需要设计一个 Cached 对象结构来保存一些额外的信息

在 Cache 读取的时候会对 _accesses 数组的添加删除通过 isEvictable 布尔值来保证线程安全操作。使用 Cached 对象里的 accessCount 属性进行 +1 操作为后面自动清理的条件判断做准备。具体实现如下：

在每次 Cache 添加时会先去检查是否自动清理，会创建一个 Cached 对象将 key，object，cost 等信息记录下添加到 _accesses 数组和 _objects 字典里。

那么上面提到的自动清理内存的方法是如何实现的呢？

既然是自动清理必定需要有触发时机和进入清理的条件判断，触发时机一个是发生在添加 Cache 内容时，一个是发生在内存警告时。条件判断代码如下：

所以 NSCache 的 totalCostLimit 的值会和每次 Cache 添加的 cost 之和对比，超出限制必然触发内存清理。

清理时会对经常访问的 objects 不清理，主要是通过 _totalAccesses 和总数获得平均访问频率，如果那个对象的访问次数是小于平均值的才需要清理。

在清理之前还需要一些准备工作，包括标记 Cached 对象的 isEvictable 防止后面有不安全的线程操作。将满足条件的清理 objects 放到清理数组里，如果空间释放足够就不用再把更多的 objects 加到清理数组里了，最后遍历清理数组进行逐个清理即可。

在清理时会执行回调内容，这样如果有些缓存数据需要持续化存储可以在回调里进行处理。

完整的实现可以查看 GNUstep Base 的 NSCache.m 文件。

下面可以看看 NSCache 在 SDWebImage 的运用是怎么样的：

可以看出利用 NSCache 自动释放内存的特点将图片都放到 NSCache 里这样在内存不够用时可以自动清理掉不常用的那些图片，在读取 Cache 里内容时如果没有被清理会直接返回图片数据，清理了的话才会执行 I/O 从磁盘读取图片，通过这种方式能够利用空间减少磁盘操作，空间也能够更加有效的控制释放。

控制 App 的 Wake 次数

通知，VoIP，定位，蓝牙等都会使设备从 Standby 状态唤起。唤起这个过程会有比较大的消耗，应该避免频繁发生。通知方面主要要在产品层面多做考虑。定位方面，下面可以看看定位的一些 API 看看它们对性能的不同影响，便于考虑采用合适的接口。

连续的位置更新

[locationManager startUpdatingLocation]

这个方法会使设备一直处于活跃状态。

延时有效定位

[locationManager allowDeferredLocationUpdatesUntilTraveled: timeout:]

高效节能的定位方式，数据会缓存在位置硬件上。适合于跑步应用应该都采用这种方式。

重大位置变化

[locationManager startMonitoringSignificantLocationChanges]

会更节能，对于那些只有在位置有很大变化的才需要回调的应用可以采用这种，比如天气应用。

区域监测

[locationManager startMonitoringForRegion:(CLRegion *)]

也是一种节能的定位方式，比如在博物馆里按照不同区域监测展示不同信息之类的应用比较适合这种定位。

经常访问的地方

// Start monitoring

locationManager.startMonitoringVisits()

// Stop monitoring when no longer needed

locationManager.stopMonitoringVisits()

总的来说，不要轻易使用 startUpdatingLocation() 除非万不得已，尽快的使用 stopUpdatingLocation() 来结束定位还用户一个节能设备。

内存对于性能的影响

首先 Reclaiming 内存是需要时间的，突然的大量内存需求是会影响响应的。

如何预防这些性能问题，需要刻意预防么

坚持下面几个原则争取在编码阶段避免一些性能问题。

⒈优化计算的复杂度从而减少 CPU 的使用.

⒉在应用响应交互的时候停止没必要的任务处理.

⒊设置合适的 QoS.

⒋将定时器任务合并，让 CPU 更多时候处于 idle 状态.