你的位置:首页 > 软件开发 > 操作系统 > [转]一些NSArray,NSDictionary,NSSet相关的算法知识

[转]一些NSArray,NSDictionary,NSSet相关的算法知识

发布时间:2016-11-06 15:01:07
iOS编程当中的几个集合类:NSArray,NSDictionary,NSSet以及对应的Mutable版本,应该所有人都用过。只是简单使用的话,相信没人会用错,但要做到高效(时间复杂度)精确(业务准确性),还需要了解其中所隐藏的算法知识。在项目当中使用集合类几乎是不可避免的,集 ...

iOS编程当中的几个集合类:NSArray,NSDictionary,NSSet以及对应的Mutable版本,应该所有人都用过。只是简单使用的话,相信没人会用错,但要做到高效(时间复杂度)精确(业务准确性),还需要了解其中所隐藏的算法知识。

在项目当中使用集合类几乎是不可避免的,集合类的使用场景其实可以进行抽象的归类。大多数时候我们需要将若干个对象(object)暂时保存起来,以备后续的业务逻辑进行操作,「保存和操作」,或者说「存与取」,对应到计算机世界的术语就是读和写。最初保存的时候我们Insert,下次进行更新的时候我们再Get,不再需要的时候我们调用Delete,所以你看集合类的操作场景其实就那么多,关键在于我们存的方式,和取的方式不同。

最初我们学习数据结构和算法的时候,知道数据的组织方式不同,比如Array, List, Stack, Heap, Tree,其对应的读和取效率(时间复杂度)也不同。如果insert的效率高,下次get的时候效率就低,比如无序的Array,插入的时候O(1),查找的时候就变O(N)。如果想要查找的速度快,比如排序过的Array,查找的速度在O(logN),插入的时候就必须要保持Array有序这一特性O(N)。所以插入和查找是鱼与熊掌,想要下次快速的找到一本书,就必须在整理书架的时候多花些心思分门别类。或者我们跳出时间的维度,用更多的空间来做弥补,使用哈希表或者Dictionary来存储数据,查找的速度可以快至O(1),缺点是牺牲了更多的空间。

当我们预先存好Array之后,使用的时候大多是以下几种场景:

场景一

for (NSObject* obj in self.arr) {  //update each object}

场景二

if ([self.arr containsObject:obj] == false) {  [self.arr addObject:obj];}

场景三

if ([self.arr containsObject:obj] == true) {  [self.arr removeObject:obj];}

第一种场景没有多少可发掘的,一次干净利索的遍历费时O(N)。唯一需要注意的是切忌在遍历的时候改变集合对象,比如:

for (NSObject* obj in self.arr) {  if(obj.isInvalid){    [self.arr removeObject:obj];  }}

如果要在遍历的时候删除可以换种写法,比如:

for (int i = self.arr.count-1; i > 0; i --) {  NSObject* obj = self.arr[i];  if (obj.isInvalid) {    [self.arr removeObject:obj];  }}

所以当我们判断两个集合当中对象是否相等时,一定要心中明确是那种相等。当调用containsObject,removeObject的时候,如果我们重载了isEqual,系统就通过我们的isEqual方法来判断相等性,如果没有重载,那么系统就会通过判断内存地址来判断相等性了。

有些架构model layer的设计会允许同一个业务对象在应用层存在多份拷贝,此时在Array当中使用相等性的时候尤其要注意重载isEqual方法。当然有些mode layer只允许一份拷贝,一个业务对象永远只对应一个内存地址,isEqual方法就变得多余了。

和isEqual配套的另一个方法hash也经常被提起,官方文档甚至规定isEqual和hash必须被同时实现。学习过hash表之后,我们知道如果两个对象业务上相等,那么他们的hash值一定是相等的,hash方法的用处还是在于判断相等性,系统默认的hash方法实际上返回的就是对象的内存地址。问题是我们已经有isEqual方法来判断相等性了,为什么还需要一个hash呢?

答案是hash可以更加高效快速的判断一个对象是否存在集合当中,在NSArray当中我们需要遍历Array,调用N次isEqual才能知道对象是否存在集合当中,时间复杂度是O(N)。在调用isEqual之前,可以通过调用hash来判断是否相等,如果hash值不等就没有进一步调用isEqual的必要了,如果相等必须再调用一次isEqual来确认是否真正相等。但是hash为什么会比isEqual的效率要高呢?看下hash的声明就明白了。

- (NSUInteger)hash{  return [_name hash];}

hash方法的返回值是一个NSUInteger,这个值往往和对象在内存当中的存储位置直接相关,也就是说我们可以通过这个值以O(1)的复杂度快速读取到某个对象来判断相等性,和Array O(N)的复杂度相比快了太多了,Array显然不具备这种特性,Array当中的元素是在一片内存空间当中连续排放的,和hash的返回值没任何关系。

但这种使用hash的便捷性有一个前提:对象在集合当中是唯一的,也就是说集合当中不允许存在重复的元素,比如NSDictionary,NSSet。我们在使用下列方法的时候:

[dictionary objectForKey:key];[set addObject:object];

原标题:[转]一些NSArray,NSDictionary,NSSet相关的算法知识

关键词:array

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录