coding with objc & swift

Objective-C遍历技术的对比

| Comments

欢迎回来,这里是新的一期Friday Q&A。Preston Sumner建议我讲解一下在Cocoa中遍历集合的不同方法以及如果实现快速遍历。因此这个讨论会分成两个部分:这个周,我将讨论一下不同遍历技术的优缺点;下个周,会详细的介绍如何在一个自定义对象上实现快速遍历。

基本遍历方式

我们以遍历C数组的方式作为讨论的参考标准:

1
2
3
4
id *array = ...;
NSUInteger length = ...;
for(NSUInteger i = 0; i < length; i++)
	// do something with array[i]

这个语法很得体,但是还不够好。有点冗长,容易出错。

对于单线程来说,这大概是遍历对象的最快方式了。只有循环中有一点小开销,几乎也是最小的开销了。(如果你实在是想解决这点开销,你可以试试手动展开循环。但是那样就显得有点疯狂了,而且实际上反而可能影响性能。)

当然,这种遍历方式在Cocoa中并不常用。因为在Cocoa中,装对象的C数组并不常见,通常见到的都是一个容器类对象。

NSEnumerator

以前,在Cocoa中遍历一个集合的标准方式是用NSEnumerator:

1
2
3
4
NSEnumerator *enumerator = [collection objectEnumerator];
id obj;
while((obj = [enumerator nextObject]))
   // do something with obj

这个语法及其繁琐,写起来真麻烦。对比前面的方式,它也有相当多的开销。首先,不得不创建一个新对象来管理遍历操作。然后,每次遍历都会给枚举器发一个消息。 相当多的活动发生在循环内,开销要大得多。

objectAtIndex:

对于那些更偏爱传统方式或者不喜欢为了一次遍历就创建一个新对象的人来说,还有另一种遍历的方法:基本的C遍历方式,然后在每次循环中调用objectAtIndex:方法

1
2
3
4
5
6
NSUInteger length = [array count];
for(NSUInteger i = 0; i < length; i++)
{
    id obj = [array objectAtIndex: i];
    // do something with obj
}

这种方式,每次循环仍然要产生一次调用,但不用创建NSEnumerator对象,所以可能会好一点点。但是也取决于objectAtIndex:这个方法有多快。(objectAtIndex:的性能并不总是比枚举器明显,特别是当数组很大的时候,就要取决于NSArray内部是如何实现objectAtIndex方法的了。)

除了语法冗长,容易出错外,这个方法还有一个很大的缺点:它不能用在NSSet或者NSDictionary上。

它也有一个很大的优点:只要仔细的处理循环索引值,在循环内部能够很安全对数组进行修改。 其他遍历方法就无法做到这一点(除非你遍历数组的一个复本)。

NSFastEnumeration

在10.5中,苹果终于解决了这个问题。他们引入for/in语法,解决了语法冗长的问题。并且依靠建立在NSFastEnumeration协议上的for/in语法,也解决了速度问题。

1
2
for(id obj in collection)
    // do something with obj

NSFastEnumeration在需要的时候成批的获取对象。编译器生成调用集合的代码,从中返回尽可能多的对象。对于对象是连续存储的那种集合,集合可以返回直接指向对象的内部指针。 如果数组中的每个对象都是连续存储的,循环就会变成类似于前面基本方式的那种方式,并且整体性能一样。如果有多段连续存储的对象, NSFastEnumerationr让集合一个接一个地返回内部指针,可以快速的从一段循环到另一段。从一段跳到另一段的时候,只需要获取一下下一段的内部指针就可以了。对于没有连续存储结构的集合,NSFastEnumeration可以成批的将集合中的对象拷贝到临时存储空间中,这样可以获得同样的效率。除此之外的任何类型的集合,NSFastEnumeration仍然可以让集合高效的遍历对象。

漂亮的语法,良好的性能,非常棒的组合,对吧。

基于Blocks的遍历

10.6开始,苹果在Objective-C加入了block的支持,同样也加入的基于Blocks的遍历方式。Blocks天生适合于创建类似于遍历的这种新的控制结构,并且苹果也在他们自己的集合对象上加上了基于block的遍历方式:

1
2
3
[array enumerateObjectsUsingBlock: ^(id obj, NSUInteger index, BOOL *stop) {
    // do something with obj
}];

对于简单的遍历,block的语法并不比快速遍历和for/in语法有什么优势。这种语法显得更加笨拙,并且遍历速度也稍微慢些。每次遍历都去调一下你的block代码。虽然这个开销比NSEnumerator那种方式中发送一次objc消息要小,但是要比NSFastEnumeration那种基本的C遍历方式开销大的多。这种block语法的遍历方式主要有两个可以用到的地方。

第一种情况,遍历的时候你想做更多的控制。苹果提供了并发遍历和反向遍历两种遍历方式。这两种方式,for/in语法都不直接支持。其他任何方式都很难实现并发遍历,所以如果你的遍历想充分利用多线程的优势,这个语法会非常有用。给数组发送一个reverseObjectEnumerator消息,再用for/in遍历,可以实现反向遍历,但是这样要创建一个NSEnumerator对象用于遍历,仍然有开销,所以使用基于Blocks的遍历方法大概也会更好些。

第二种情况是,遍历字典时既要访问键也要访问对象的情况。for/in语法一次只能给你一个对象。这样你就只能先遍历键,然后再加一步操作才能获得对应的对象:

1
2
3
4
5
for(id key in dictionary)
{
    id obj = [dictionary objectForKey: key];
    // do something with key and obj
}

这个比起for/in语法来说,就不用说语法繁琐的问题了,它还要慢很多。额外的操作直接影响了NSFastEnumeration的性能。

NSDictionary提供了一个基于block的,可以传递处理键和对象的遍历方法:

1
2
3
[dictionary enumerateKeysAndObjectsUsingBlock: ^(id key, id obj, BOOL *stop) {
    // do something with key and obj
}];

这个写法更漂亮,遍历速度也更快。字典可以在它的内部数据结构中直接遍历键/值队,就不需要额外的用for/in循环去遍历键了。

总结

写任何代码的时候,你都应该更偏爱那些易读易于维护的技术。除非你明确的知道它有速度上的问题,想通过其他困难点的方式解决。特别是在遍历集合的时候,你在循环内部做的任何操作几乎必然会影响到循环本身的性能。

幸好苹果解决了这个问题,因此大多数情况下我们都不需要再纠结于到底选择哪种方式。在绝大多数情况下,for/in语法都即是最漂亮也是最快速的遍历一个集合的方式。即便对于有些它不是最佳方式的情况,在10.6中也提供了基于block的遍历方式。你几乎不再用写一个NSEnumerator循环来遍历集合了,除非你要支持10.4的系统。如果需要在遍历的过程中修改数组,objectAtIndex:这个方式很有用。除此之外,没有比for/in更好的方式了。

以上是这周的所有内容。下周回来,到时候我会谈谈如何自己实现NSFastEnumeration协议

原文:Friday Q&A 2010-04-09: Comparison of Objective-C Enumeration Techniques

Comments