在RunLoop的Timer管理中，需要对每定时器进行有序管理——按照时间先后排序。这个必然会带来一个查找和排序。在RunLoop 中使用的是二分查找法，但是这个二分查找与平时的二分查找不太一样。
先上代码
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
| //利用二分法按照fireTSR的大小插入排序
static CFIndex __CFRunLoopInsertionIndexInTimerArray(CFArrayRef array, CFRunLoopTimerRef rlt) __attribute__((noinline));
static CFIndex __CFRunLoopInsertionIndexInTimerArray(CFArrayRef array, CFRunLoopTimerRef rlt) {
CFIndex cnt = CFArrayGetCount(array);
if (cnt <= 0) {
return 0;
}
if (256 < cnt) {//count 小于256个时候优先判断 第一个和最后一个
CFRunLoopTimerRef item = (CFRunLoopTimerRef)CFArrayGetValueAtIndex(array, cnt - 1);
if (item->_fireTSR <= rlt->_fireTSR) {
return cnt;
}
item = (CFRunLoopTimerRef)CFArrayGetValueAtIndex(array, 0);
if (rlt->_fireTSR < item->_fireTSR) {
return 0;
}
}
//开始二分查找
CFIndex add = (1 << flsl(cnt)) * 2;
CFIndex idx = 0;
Boolean lastTestLEQ;
do {
add = add / 2;
lastTestLEQ = false;
CFIndex testIdx = idx + add;
if (testIdx < cnt) {
CFRunLoopTimerRef item = (CFRunLoopTimerRef)CFArrayGetValueAtIndex(array, testIdx);
if (item->_fireTSR <= rlt->_fireTSR) {
idx = testIdx;
lastTestLEQ = true;
}
}
} while (0 < add);
return lastTestLEQ ? idx + 1 : idx;
}
|
这里不详细讲述普通二分查找算法了，直接看这个算法。
二分查找的时间复杂度是在O(log N)，也就是说，在log N次查询之内必然是可以有搜索结果的。
下图就是两次搜索的演示过程
传统的二分查找，是二分区间，每次从一个区间中去选择前半区或者后半区。而这里的二分分的是 add 的长度。代码中的idx是 区间查找法 中的区间 start，因为每次二分的 idx 是否需要指向 testIdx，这个判断就是 区间查找法中的前后半区选择，其中 end = idx + start 所以说，add 隐藏了区间的 end。
代码很简短，输入一个数组，一个定时器，返回这个定时器应该在这个数组中插入的Index。
先判断如果当前数组内的数量少于256个，优先判断最后一个和第一个。这个问题我想，是否是因为在大部分情况下，定时器都不会超过256个，并且，定时器一般..大部分情况下都是往后增加。所以算法在最开始的时候，通过一个if判断快速处理了，大部分的使用情况。避免了每次都要进行O(log n)时间的搜索。
按照上面的演示过程，执行二分查找。但是在二分查找之前还有一段代码:CFIndex add = (1 << flsl(cnt)) * 2; 为什么add的起始点不是cnt？flsl()函数是获得cnt用二进制表示时最大有效位数。例如，(flsl(256) 的结果是 9)。如果cnt是256，add的值将会变成1024。1左移9位是512，512再乘2，1024。向上取整：保证add是2的n次幂，这样就不用考虑奇偶问题了。
ps：上面那个例子，为什么需要左移9位再乘2？直接左移8位不行？