linux kernel 中的二叉树搜索 与 stl 相应物的对比

Linux kernel 中也使用并实现了红黑树,但是查找算法没有自己实现,而是希望使用者去实现。如果只是实现一个精确查找的函数,这很简单,几乎每个人都能写出正确的代码:

这是 kernel 中 rbtree.h 中给出的示例代码,几乎所有的 kernel search 代码都遵循了这个模式。然而,这个代码的效率有问题,虽然仍是 O(logn) 的。

再看看 stl 中的实现(这只是个简化示例,不完全等同于 stl 中的实际代码):

分析

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 的这个代码更简洁,但稍微费脑子一点。

 

作者:
该日志由 csdn-whinah 于2011年11月26日发表在C++分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: linux kernel 中的二叉树搜索 与 stl 相应物的对比
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。