算法晨光第一剑之 OC 的环形缓冲区

线性表 可是算是最基础的数据结构了,但是你不应该看不起他。实际上,线性表 相关的知识可以很基础,也可以很深入。我们平常编码工作可以说有 50% 的时间都在使用他,鉴于他的应用如此之广泛,我们不妨从身边最常应用的工具入手,扒一扒这个可爱且趁手的工具。

1 线性表与数组

对于线性表,众所周知常用的两种实现 – 数组链表。这两种实现的复杂度也是我们熟知的:

(时间复杂度) 头插 尾插 随机插 随机删除 随机访问
数组 O (n) O (1) O (n) O (n) O (1)
链表 O (1) O (1) O (1) O (1) O (n)

数组的 操作(插入与删除)效率较低,这是因为在数组中间位置插入与删除元素,都需要移动位置后面的所有元素。而链表的 操作效率低,因为访问链表元素得一个接一个访问,不能利用到内存的随机访问特性。所以这是我们平时采用哪种数据结构的依据,比如在使用 Java 中我们常要思考使用 ArrayList 还是 LinkedList

而在 Objective-C 编写中就没那么头疼了,只有一个选择就是 NSMutableArray(对于只读的 NSArray,必定是使用简单数组,这就不深扒了)。为啥 OC 中如此设计呢,想必是实际的编程过程中数组的使用要多于链表。

1.1 为什么用 array 多于 linkedList?

因为在实际项目中,对于数据成员我们使用 array [i] 索引读取的操作的情况一般来说总是较从数据中间插入数据更常见。

但是,使用普通的 array 还是许多局限,比如说,队列 是个很常用到的数据结构,其中涉及到许多从队尾入队列,从队头出队列的操作。这个很常用到的数据结构用简单的数组操作起来就会比较低效。经过分析我们可以知道,其主要复杂度在于从列表头出列,后面的元素都要逐个往前移一位,这样的操作会非常低较。

而采用环形缓冲区则可以优化这一块,整个缓冲区的头与尾在逻辑上是相连的,任一头的插入或删除元素都是自由的,无需整体移动。如下图:

1
2
3
4
5
6
7
8
9
10
11
# 原数组:
┌──────┬──────┬──────┬──────┐
| │ A │ B │ │
└──────┴──────┴──────┴──────┘
0 1 2 3

# 在队列尾插入 C,然后队列头出列 A:
┌──────┬──────┬──────┬──────┐
│ │ │ B │ C │
└──────┴──────┴──────┴──────┘
0 1 2 3

2 环形缓冲区的设计与实现

要实现这样一个环形缓冲区并不复杂,只需要下面几个变量:

1
2
3
4
list 缓冲区指针,指向缓冲区的首地址。
size 缓冲区大小,表示该缓冲区的大小,当缓冲区大小与实际存储的元素数量相同时,就需要动态地扩张缓冲区了。
used 缓冲区内实际存储元素的计数,表示缓冲区内实际上有多少个元素。
offset 缓冲区里的数组的第一个元素索引

我们可以看出,使用 class-dump 出来的 NSMutableArray 确实差不多就是这样的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
@interface __NSArrayM : NSMutableArray
{
unsigned long long _used;
unsigned long long _doHardRetain:1;
unsigned long long _doWeakAccess:1;
unsigned long long _size:62;
unsigned long long _hasObjects:1;
unsigned long long _hasStrongReferences:1;
unsigned long long _offset:62;
unsigned long long _mutations;
id *_list;
}
@end

去除一些与环形缓冲区不太相关的字段:

class-dump 出来的 NSMutableArray 私有数据结构(去掉了一些不相关的字段)
1
2
3
4
5
6
7
8
@interface __NSArrayM : NSMutableArray
{
id *_list; // 最重要的数据结构 -- 缓冲区的指针
unsigned long long _size; // 缓冲区大小
unsigned long long _used; // 缓冲区计数
unsigned long long _offset; // 缓冲区中第一个元素的索引
}
@end

下面我们来看看利用这几个变量设计出的环形缓冲区的基本操作

2.1 索引

环形缓冲区的索引有两种情况:

  • 一种是整个数组刚好在缓冲区中间,头尾都还有空间的情况。此时 offset + use <= size.
  • 另一种是数组已达缓冲区末尾,另一部分复用了缓冲区头部区域,此时 offset + use > size.

2.1.1 数组刚好在缓冲区中间

1
2
3
4
5
6
7
8
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ A │ B │ C │ D │ E │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5 6 7 8

# size = 9
# use = 5
# offset = 2

比如上面这个例子,offset + use = 7 <= size (9),从而判断出整个都数组在缓冲区中间。
此时要访问数组中的元素 i,直接 list [offset + i] 就可以了。比如要访问队头元素 queue [0],就相当于访问 list [2 + 0] = list [2] = A;访问 queue [4] = list [2 + 4] = list [6] = E

2.1.2 数组复用了缓冲区头部空间

1
2
3
4
5
6
7
8
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ D │ E │ │ │ │ │ A │ B │ C │
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5 6 7 8

# size = 9
# use = 5
# offset = 6

而在上面这个例子中,offset + use = 11 > size (9),从而判断出数组已达缓冲区末尾并复用了缓冲区头部空间.
此时要访问数组中的元素 i,直接用 offset + i 就不行了,因为此索引已超出了缓冲区的大小。
值得关注的小技巧是这里一般需要对 offset + i 后的新索引取模,但是鉴于超出的部分不可以大于一个缓冲区 size 的大小,可以简单地减去缓冲区的大小即可 (既此时 (offset + i) % size == offset + i - size)。

因此,我们就需要判断 offset + i 是否大于 size, 大于的话就减去 size 得到模的部分。比如要访问队头元素 queue [0],此时 offset + i = 6 + 0 < size (9),因此相当于访问 list [6 + 0] = list [6] = A;访问 queue [4] = list [6 + 4 - 9](因为此时 offset + i > size) = list [1] = E。这看上去非常简洁、合理,多么优雅的设计啊!

写成 OC 代码如下:

objectAtIndex
1
2
3
4
5
6
7
8
9
10
11
- (id)objectAtIndex:(NSUInteger)index
{
if (_used <= index) {
goto ThrowException; // 超界
}
NSUInteger fetchOffset = _offset + index; // 就是我们上面分析的 offset + i
NSUInteger realOffset = fetchOffset - ( (_size > fetchOffset) ? 0 : _size);
return _list[realOffset];
ThrowException:
// exception throwing code
}

2.2 插入与删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 4
# offset = 0

--> 从头部删除元素 A ( use - 1, offset + 1 )
┌───┬───┬───┬───┬───┬───┐
│ │ B │ C │ D │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 3
# offset = 1

--> 从尾部删除元素 D ( use - 1 )
┌───┬───┬───┬───┬───┬───┐
│ │ B │ C │ │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 2
# offset = 1

--> 从头部插入元素 F ( use + 1, (offset - 1) < 0 ? (offset - 1 + size) : (offset - 1) )
┌───┬───┬───┬───┬───┬───┐
│ F │ B │ C │ │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 3
# offset = 0

--> 从头部插入元素 A ( use + 1, (offset - 1) < 0 ? (offset - 1 + size) : (offset - 1) )
┌───┬───┬───┬───┬───┬───┐
│ F │ B │ C │ │ │ A │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 4
# offset = 5

可见,环形缓冲区中数组的头插、尾插、头删、尾删,都不需要移动数组整体了,除去几个标志变量的修改忽略不计,就是 O (1) 的时间复杂度。

2.3 性能

经过上面的分析,我们基本知道了环形缓冲区的内存形态及工作方式。可以知道,头插尾插的时间复杂度为 O (1)。 但遗憾的是,数组毕竟是数组,如果在数组中间插入数据,或是我们常用的随机插入数据的情况,还是需要逐一移动后面的元素以给要插入的元素空出位置。

基于这个分析,我们写下如下测试代码:

性能评估代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//-- 头插耗时
NSMutableArray *array = [NSMutableArray array];
// 创建一个有一定规模的数组
for (int i = 0; i < 1000 * 1000; i++) {
[array addObject:@(i)];
}
// 头插耗时
CFAbsoluteTime startTime =CFAbsoluteTimeGetCurrent();
for (int i = 0; i < 1000 ; i++) {
[array insertObject:@(i) atIndex:0]; // 头插
}
CFAbsoluteTime consumeTime = (CFAbsoluteTimeGetCurrent() - startTime) * 1000.0;
NSLog (@"头插耗时 % f ms", consumeTime);

//-- 中间插耗时
NSMutableArray *array2 = [NSMutableArray array];
// 创建一个有一定规模的数组
for (int i = 0; i < 1000 * 1000; i++) {
[array2 addObject:@(i)];
}
// 中间插耗时
startTime = CFAbsoluteTimeGetCurrent();
for (int i = 0; i < 1000 ; i++) {
[array2 insertObject:@(i) atIndex:5 * 1000]; // 中间插耗时
}
consumeTime = (CFAbsoluteTimeGetCurrent() - startTime) * 1000.0;
NSLog (@"中间插耗时 % f ms", consumeTime);

//-- 尾插耗时
NSMutableArray *array3 = [NSMutableArray array];
// 创建一个有一定规模的数组
for (int i = 0; i < 1000 * 1000; i++) {
[array3 addObject:@(i)];
}
// 尾插耗时
startTime = CFAbsoluteTimeGetCurrent();
for (int i = 0; i < 1000 ; i++) {
[array3 insertObject:@(i) atIndex:array3.count]; // 尾插耗时
}
consumeTime = (CFAbsoluteTimeGetCurrent() - startTime) * 1000.0;
NSLog (@"尾插耗时 % f ms", consumeTime);

运行上述代码,下面的输出也印证了我们的分析,中间插入耗时显高于头尾插入:

1
2
3
头插耗时:  0.023961 ms
中间插耗时: 0.724912 ms
尾插耗时: 0.025988 ms

2.4 优化

作为对环形缓冲区的分析,本文要说的基本就结束了,最后从 参考文章 1 中,我们又学到了一些 OC 中对环形缓冲区的优化操作。

2.4.1 增长因子

当缓冲区空间满了的时候,NSMutableArray 会动态地扩充自己的缓冲区大小,从 参考文章 1 中我们知道大概是 1.625

2.4.2 一旦增长,不再缩小

此外,缓冲区的空间只会增长,不会缩小。也就是即使你 remove 了其中的元素,缓冲区的大小并不会随之改变。

2.4.3 初始化容量几乎完全不重要

这个其实大多数 iOS developer 应该都知道了,就是 initWithCapacity 中指定的 Capacity 其实并没有什么卵用。

2.4.4 在删除的时候不会清除指针

这个特性挺有趣的,其实就是当我们从 NSMutableArray 中 remove 元素时,并不需要真正将之从数组移除,只要移动引用指针即可。这样可以省去清除空间的时间,但是当然,因为数组中存的是对象引用,所以 ARC 还是要隐式插入相应的 retain/release 操作。

remove 并没有清空元素的空间,只是改变了引用指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 源数组
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 4
# offset = 0

--> 从头部删除元素 A (并不需要将 A 元素当前内存清空)
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ │ │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5
# size = 6
# use = 3
# offset = 1

像上面,实际删除 A 并没将之单元清空,只是移动的 offset + 1.

3 参考

  1. 《NSMutableArray原理揭露》 - Joying Xie 本文主要参考之一,其实这是一篇译文。此文不仅仅是揭露NSMutableArray的原理,还手把手介绍了通过反编译来窥探Objective-C源码的技巧和思想,作者非常地厚道,非常地推荐。
坚持原创技术分享,您的支持将鼓励我继续创作!