linux kernel 中的二叉树搜索 与 stl 相应物的对比
Linux kernel 中也使用并实现了红黑树,但是查找算法没有自己实现,而是希望使用者去实现。如果只是实现一个精确查找的函数,这很简单,几乎每个人都能写出正确的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
struct page* rb_search_page_cache(struct inode* inode, unsigned long offset) { struct rb_node* n = inode->i_rb_page_cache.rb_node; struct page* page; while (n) { page = rb_entry(n, struct page, rb_page_cache); if (offset < page->offset) n = n->rb_left; else if (offset > page->offset) n = n->rb_right; else return page; } return NULL; } |
这是 kernel 中 rbtree.h 中给出的示例代码,几乎所有的 kernel search 代码都遵循了这个模式。然而,这个代码的效率有问题,虽然仍是 O(logn) 的。
再看看 stl 中的实现(这只是个简化示例,不完全等同于 stl 中的实际代码):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Node* rb_tree::lower_bound(const Key& k) { Node* y = NULL; Node* x = root; while (x != 0) if (k <= x->key) y = x, x = x->left; else x = x->right; return y; } Node* rb_tree::find(const Key& k) { Node* y = lower_bound(k); return y == NULL || k < y->key ? NULL : y; } |
分析
kernel 代码的每个循环中有两个条件判断,而 lower_bound 中只有一个条件判断,虽然在 stl 中,即使在找到相应结点后,可能还需要再继续搜索,然而,鉴于二叉树(平衡树)的结构,深度越深的结点,其数目越多,对于满二叉树,深度增一倍,结点数目就增一倍,最底层(深度最深的那层)结点的数目比所有其它层的总数还要多1。假定满二叉树的高度为k(仅一个结点时定义该高度为0),则结点总数=2^(k+1)-1,针对查找成功的情况,假定每个结点被查找的概率相同,在这两种算法中,满二叉树的平均查找长度为:
linux kernel 的实现
(1*1+2*2+…+(k+1)*2^k))/(2^(k+1)-1) = (1 + k*2^(k+1))/(2^(k+1)-1) = k +(k+1)/(2^(k+1)-1)
(k+1)/(2^(k+1)-1) 在 k 较大时会非常快地趋近于 0,我们可以忽略这一项,结果就是k。
从而,最坏情况下,循环内的判断总次数为 2*k,平均次数是
1.5*k
stl::rb_tree::lower_bound
每个结点的查找都一直到最底层,所以平均查找长度为 k+1,只多 1,然而,循环内的判断次数是 1,所以总的判断次数是 k+1,rb_tree::find 在 lower_bound 找到后需要再判断一次与key 是否相等,总的判断次数就是 K+2 了,但这仍然比 kernel 的判断次数少(k>2 的时候)。虽然这是针对满二叉树的分析,但这可以延伸至平衡的二叉树(log 的底数不再是 2,要比 2 稍微小一点)。
结论
现在应该看到了,虽然 std::lower_bound 没有在找到目标的第一时间就返回,看上去似乎比较傻,但实际上要更快,鉴于现在 CPU 有缓存,分支预测(这个例子循环内的分支预测无法起作用,但CPU还有 speculation,就是同时执行两个分支,然后丢弃错误的那个分支),指令预取等高级功能,lower_bound 比 kernel 快的没有分析的那么多。经过实测,stl 的 rb_tree::find 要比 kernel 的大约快 10% 。
范围查找
如果要范围查找, kernel 的那个实现就不行了,而 lower_bound 是专干这个的(当然,还有个对应的 upper_bound)!
另外,毋庸置疑,stl 的这个代码更简洁,但稍微费脑子一点。