算法晨光第一剑之 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源码的技巧和思想，作者非常地厚道，非常地推荐。