310
11
仔细检查表中最后两列数据,可以看到当
W
= 175
时,近似解是最优解的
60%
。随着
W
的增加,近似解越来越接近最优解,而且比最优解快近
1000
倍。
11
-
3
背包问题衍生算法的性能比较
W
无限背包算法时间 无限背包近似算法时间 最优解 近似解
175 0.00256 0.00011 175 103
351 0.00628 0.00011 351 309
703 0.01610 0.00012 703 618
1407 0.03491 0.00012 1407 1339
2815 0.07320 0.00011 2815 2781
5631 0.14937 0.00012 5631 5562
11263 0.30195 0.00012 11263 11227
22527 0.60880 0.00013 22527 22454
45055 1.21654 0.00012 45055 45011
11.3 并行算法
并行算法通过创建和管理线程,能够更好地利用已有资源。
11-4
给出了在第
4
章讨论过的
快速排序
Java
实现,这个实现假设
partition
方法
能够根据中枢点将数组分成两个子数组。回忆一下第
4
章,
pivotIndex
左边的值都小于
等于中枢点,而右边的都大于等于中枢点。
11-4
:快速排序的
Java
实现
public class MultiThreadQuickSort<E extends Comparable<E>> {
final E[] ar; /*
需要排序的元素。
*/
IPivotIndex pi; /*
切分函数。
*/
/**
*
构造一个实例来解决快速排序问题
*/
public MultiThreadQuickSort(E ar[]) {
this.ar = ar;
}
/**
*
设置分区方法
*/
public void setPivotMethod(IPivotIndex ipi) { this.pi = ipi; }
/**
*
单线程排序
ar[left, right]
新兴算法
311
新兴算法
*/
public void qsortSingle(int left, int right) {
if (right <= left) { return; }
int pivotIndex = pi.selectPivotIndex(ar, left, right);
pivotIndex = partition(left, right, pivotIndex);
qsortSingle(left, pivotIndex - 1);
qsortSingle(pivotIndex + 1, right);
}
}
两个子问题
qsortSingle(left, pivotIndex - 1)
qsortSingle(pivotIndex + 1,
right)
都是各自独立的,并且理论上可以同时解决。现在的问题就是如何使用多线程来
解决这个问题。不能简单地生成一个辅助线程,然后不断递归求解,这样会造成操作
系统的资源非常紧张。例
11-5
给出了新的实现
qsort2
11-5
:多线程
Java
快速排序实现
/**
*
多线程排序
ar[left, right]
*/
void qsort2(int left, int right) {
if (right <= left) { return; }
int pivotIndex = pi.selectPivotIndex(ar, left, right);
pivotIndex = partition(left, right, pivotIndex);
qsortThread(left, pivotIndex - 1);
qsortThread(pivotIndex + 1, right);
}
/**
*
生成新的或者使用已有的线程来排序
ar[left, right]
*
如果数据规模足够大
,
所有线程都会被使用到。
*/
private void qsortThread(final int left, final int right) {
//
是否所有线程都在工作?或者数据规模太大了?
//
如果是话,那么继续递归
int n = right + 1 - left;
if (helpersWorking == numThreads || n >= threshold) {
qsort2(left, right);
} else {
//
否则
,
在一个单独的线程中完成工作。
synchronized (helpRequestedMutex) {
helpersWorking++;
}
new Thread() {
public void run() {
//
启动单线程排序。
qsortSingle(left, right);
312
11
synchronized (helpRequestedMutex) {
helpersWorking--;
}
}
}.start();
}
}
在计算两个
qsortThread
子问题时,需要检查一下当前线程是否需要继续完成
qsortThread
函数。在有可用线程以及子问题的数据规模小于某个阈值的情况下,我们
需要启动一个单独的线程来计算。
setThreshodRatio(r)
方法会
将阈值设置为
n/r
,其
n
是数据的规模。
r
的默认值为
5
也就是说辅助线程只会在子问题的数据规模为原始数据规模的
1/5
时被创建。
helpersWorking
表示有多少正在工作的线程。当一个线程被创建时,
helpersWorking
变量会增加
1
,并且在线程完成之后自动减
1
。正因为这个变量会被多个线程修改,所
以需要一个信号量
helpRequestedMutex
来保证这个变量的修改和访问是线程安全的。
qsort2
会在其辅助线程中调用单线程的
qsortSingle
方法,所以当前线程只负责检
查是否需要启动辅助线程,而不需要做额外的排序工作。
这段实现中,辅助线程没有生成新的辅助线程。如果这样,一级辅助线程需要等待所
有生成的二级辅助线程执行完毕才能继续,而二级线程需要一级线程完成切分数组之后
才会开始执行,这就是死锁,即多线程编程中最应该避免的情况。
11-1
和图
11-2
对比了两种实现的性能,我们会生成介于
0~16777216
的整数,而且还
有如下参数:
数组长度
n
n
的范围是
65 536-1 048 576
阈值
n/r
这个值决定了什么时候需要启动一个辅助线程。我们尝试了
r
1~20
的情况,而且
还有
MAX-INT
,最后这种情况完全不会使用辅助线程。
可用的辅助线程数目
我们尝试了
0~9
个辅助线程。
切分函数
我们尝试了“随机选择元素”和“选择最右边元素”。
这些参数范围如此之广,以至于最终可以得到多达
2000
种参数组合。不过,在选择
切分函数上,我们发现使用随机选择算法会导致性能有
5%
左右的下降,因此我们
新兴算法
313
新兴算法
了随机选择,而仅仅选择“最右”的元素。不仅如此,多个辅助线程在
快速排序
实现中
并不会起到很大作用,因此我们也仅仅尝试了
1
个辅助线程。
ܠ၍ײ੺໏ಇႾሞփཞ
o
s
ኵူ჋ስፌᆸՉᇮ໎
Ⴀీ0nt
S
ڦൽኵ
11-1多线程排序在不同
n
r
值下的性能
从左到右看这张图,可以看出在不同
r
的情况下辅助线程的利用情况最左边的数据点
r
= 1
表示辅助线程马上开始使用,而最右边的点表示从未使用辅助线程。因此,我们需
要计算一个叫作
加速比
的指标(从
T
1
到更小的
T
2
,公式为
T
1
/
T
2
),以衡量多线程的影
响情况。由表
11-4
的数据可知,简单地改动代码就能带来不错的收益。

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.