7.7.3 多路平衡归并与败者树

归并趟数S=[logm R](向下取整)。从而增加归并路数m可以减少归并趟数S,进而减少访问外存的次数(I/O次数)。然而,当增加归并路数m时,内部归并时间将增加。做内部归并时,在m个元素中选择关键字最小的记录需要比较m-1次。每趟归并n个元素最多需要作(n-1)*(M-1)次比较,S趟归并总共需要的比较次数为:

S*(n-1)*(m-1)=[logmR]*(n-1)*(m-1)=[log2R]*(n-1)*(m-1)/[log2M]

其中的【log2R】*(n-1)在初始归并段个数R于记录个数n一定时是常数。而(m-1)/[log2M]随m增长而增长,则内部归并时间亦随m的增长而增长。这将抵消由于增大m而减少外存访问次数所得到的效益。因此不能使用普通的内部归并排序算法。

为了使内部归并并不受m的增大的影响,引入了败者树。败者树是对树形选择排序的一种变形,可以看作一棵完全二叉树。每个叶结点存放各归并段在归并过程中当前参加比较的记录,内部结点用来记忆左右子树中的“失败者”,而让胜者往上继续比较,一直到根结点。如果比较两个数,大的为失败者,小的为胜利者,则根结点指向的树为最小数。

因此m路归并的败者树深度为【log2M】,因此m个记录中选择最小关键字最多需要[log2M]次比较。所以总的比较次数为:

S*(n-1)*【log2 M】=【logm R】*(n-1)*【log2 M】=(n-1)*【log2 R】

因此,只要内存空间允许,增大归并路数m将有效地减少归并树的高度,从而减少I/O次数d,提高外部排序的速度。

值得说明的是,归并路数m的选择并不是越大越好。归并路数m增大时,相应地需要增加输入缓冲区个数。如果可供使用的内存空间不变,势必要减少每个输入缓冲区的容量,使得内外存交换数据的次数增大。当m值过大时,虽然归并趟数会减少,但读写外存的次数会增加。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI2ML人工智能to机器学习

易图秒懂の神经网络潜行-CNN前生

在“易图秒懂の神经网络诞生"里面,简述了神经网络诞生,它诞生后,火爆了, 但后来又被打入了冷宫。 这里开始解释神经网络受冷之后,如何慢慢发展的。

12220
来自专栏AI2ML人工智能to机器学习

一个奇异值的江湖 -- 机器学习观

前面我们熟悉了经典统计处理outlier的方法。 这里会说明常见的机器学习的方法。

10120
来自专栏AI2ML人工智能to机器学习

非均衡数据处理--如何学习?

Sampling技术比较直观,就是怎么把样本变成均衡的。 我们知道不均衡数据, 最重要的还是收集minority数据。 但是一般这是一个长期的过程。 那么, ...

16620
来自专栏AI2ML人工智能to机器学习

攒说 Geoff Hinton

大家都知道深度学习的鼻祖Geoff Hinton, 传说, 他安静的办公室, 经常会突然传出一句很大声的自言自语, 就是 我现在终于理解大脑怎么工作的啦(I u...

11110
来自专栏码洞

一个Raft开源项目的结构分析

Raft声称是一种易于理解的分布式一致性算法。有不少工程师们翻了它的论文,参考了很多资料,最后只好怀疑自己是不是智商有问题。

21720
来自专栏华章科技

大数据入门,你需要懂这四个常识

大数据分析的使用者有大数据分析专家,同时还有普通用户,但是他们二者对于大数据分析最基本的要求就是可视化分析,因为可视化分析能够直观的呈现大数据特点,同时能够非常...

10230
来自专栏华章科技

云栖大会南京峰会精彩看点之天池数据可视化创新大赛

通过2D瓦片图层的3D化,能够在经度维度、量级、时间多个维度上真实还原城市3D空间。例子中为模拟的轨迹数据和旧金山食物供应商分布。

13730
来自专栏AI2ML人工智能to机器学习

收敛率概述 (Overview of Rates of Convergence)

在算法优化过程中经常会遇到收敛(Convergence)问题, 尤其目前的深度学习盛行, 如何设计更高效的收敛算法, 是个极大的挑战。

27150
来自专栏云瓣

从 0 到 1 实现 React 系列 —— 4.setState优化和ref的实现

看源码一个痛处是会陷进理不顺主干的困局中,本系列文章在实现一个 (x)react 的同时理顺 React 框架的主干内容(JSX/虚拟DOM/组件/生命周期/d...

12120
来自专栏华章科技

凯文·凯利:大数据时代没有旁观者

日前,互联网教父、科技商业预言家的凯文·凯利在斯坦福大学进行长达3小时的分享,畅谈他对未来20年重大科技商业潮流的见解。以下为演讲内容整理干货。

9620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励