Administrator
Administrator
Published on 2024-11-19 / 2 Visits
0
0

基于并行的归并段生成优化+最优二路归并

基于并行的归并段生成优化+最优二路归并

一、基于并行的归并段生成优化

参考文章:基于并行的归并段生成优化.pdf

简易概括:

即通过一种类似二分法的算法找到归并后数组的中间索引以及对应的两个归并前数组的对应位置,从而将A,B两个归并前数组划分为A左,A右,B左,B右,从而划分为两个可以并行的归并,提高多线程效率。案例如下图:

image

二、最优二路归并

参考文章:最优二路归并树.pdf

	    [最优二路归并树](https://blog.csdn.net/qq_41587740/article/details/104389150)

简易概括:

image

要使归并的io操作最少,就是要令归并树的WPL最小,实现这一切的树就是哈夫曼树


Comment