快速排序方法及其改进策略
算法简介
是一种分治的排序算法,特点就是快,而且效率高。
基本思路
通过一趟排序将待排元素分隔成独立的两部分,其中一部分元素的关键字均比另一部分的关键字小,然后分别对这两部分元素继续进行排序,以达到整个序列有序。
Q:对比归并排序,有何异同?
A:快速排序和归并排序是互补的:归并排序是将数组分成两个子数组分别排序,并将有序的子数组归并以整个数组排序;而快速排序是当两个子数组都有序时,整个数组也就自然有序了。递归调用先后顺序不同:归并排序 ~ 递归调用发生在处理整个数组之前;快速排序 ~ 递归调用发生在处理整个数组之后。
切分数组的位置不同:归并 ~ 一个数组等分为两半;快速 ~ 切分的位置取决于数组的内容。
运行轨迹
快速排序递归的将子数组 arr[lo...hi] 排序,先用 partition() 方法将 arr[indexJ] 放到一个适合位置,然后再用递归调用将其他位置的元素排序
快速排序关键在于切分方法,我们就是通过递归地调用切分来排序的,因为切分过程总是能排定一个元素。
实现的一般策略:
①、随意地取 arr[lo] 作为切分元素(将会排定的元素);
②、从数组的左端开始,向右端扫描,直到找到一个 >= 切分元素的元素;
③、从数组的右端开始,向左端扫描,直到找到一个 <= 切分元素的元素;
④、交换他俩的位置(因为显然他俩没有被排定);
⑤、如此继续,可以保证左指针 indexI 的左侧元素都 <= 切分元素、右侧指针 indexJ 的右侧元素都 >= 切分元素;
⑥、当两个指针相遇时,交换切分元素 arr[lo] 和 arr[indexJ] 并返回 indexJ 即可。
代码实现
根据排序算法类的模板实现快速排序(提醒:点蓝字查看详情)
/**
* 标准的快速排序
*
* @author TinyDolphin
* 2017/11/13 14:20.
*/
public class Quick {
public static void sort(Comparable[] arr) {
shuffle(arr); // 打乱数组,避免切分不平衡,带来的低效
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
if (hi <= lo) return;
int indexJ = partition(arr, lo, hi); // 切分方法
sort(arr, lo, indexJ - 1);
sort(arr, indexJ + 1, hi);
}
// 打乱数组的方法
private static void shuffle(Comparable[] arr) {
int length = arr.length;
Random random = new Random(System.currentTimeMillis());
for (int index = 0; index < length; index++) {
int temp = random.nextInt(length);
exch(arr,index,temp);
}
}
/**
* 关键:切分方法
* 该过程使得数组满足下面两个条件:
* ①、对于某个 indexJ、arr[indexJ] 已经排定;
* ②、arr[lo...indexJ-1] <= arr[indexJ] <= arr[indexJ+1...hi]
*/
private static int partition(Comparable[] arr, int lo, int hi) {
int indexI = lo; // 左右扫描指针
int indexJ = hi + 1;
Comparable temp = arr[lo]; //切分元素
while (true) {
// 从数组的左端开始,向右端扫描,直到找到一个 >= 切分元素的元素;
while (less(arr[++indexI], temp)) {
if (indexI == hi) break;
}
// 从数组的右端开始,向左端扫描,直到找到一个 <= 切分元素的元素;
while (less(temp, arr[--indexJ])) {
if (indexJ == lo) break;
}
// 指针相遇,退出循环
if (indexI >= indexJ) break;
// 交换他俩的位置(因为显然他俩没有被排定)
exch(arr, indexI, indexJ);
}
exch(arr, lo, indexJ); // 将 temp = arr[indexJ] 放入正确的位置
return indexJ; // arr[lo...indexJ-1] <= arr[indexJ] <= arr[indexJ+1...hi] 达成
}
...
}
Q:打乱数组的方法(shuffle())消耗了大量的时间,这么做值得么?
A:值得,这样可以预防出现最坏情况并使时间可以预计。
实现细节必须注意
①、原地切分:如果使用一个辅助数组,我们可以很容易实现切分,但将切分后的数组复制回去的开销也许会使我们得不偿失。
②、别越界:如果切分元素是数组中最小或最大的那个元素,我们就要小心别让扫描指针跑出数组的边界。parttion() 实现可以进行明确的检测来预防。测试条件 ( indexJ==lo ) 是冗余的,因为切分元素就是 arr[lo],它不可能比自己小。数组右端也有相同的情况,他们都是可以去掉的。(练习 2.3.17)
③、保持随机性:数组元素的顺序是被打乱过的。保存随机性的另一种方法:在切分方法中随机选择一个切分元素。
④、终止循环:一个最常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。
⑤、处理切分元素值有重复的情况:左侧扫描最好遇到 >= 切分元素值 的元素时停下,右侧扫描则是遇到 <= 切分元素值的元素时停下。(尽管存在一些等值交换,但可以避免算法的运行时间变为平方级别)
⑥、终止递归:一定要保证将切分元素放入正确的位置,不然容易导致无限递归。
性能分析
最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(n²)
平均情况:T(n) = O(nlogn)
将长度为 N 的无重复数组排序,快排平均需要 ~2NlnN 次比较以及 1/6 的交换
快排最多需要约 N²/2 次比较,但随机打乱数组能够预防这种情况。
优化方案
①、切换到插入排序
对于小数组,快排比插入慢;因为递归,快排的 sort() 方法在小数组中也会调用自己。
②、三取样切分(用来选择切分元素)
使用子数组的一小部分元素的中位数来切分数组(取样大小为 3 并用大小居中的元素效果最好) || 将取样元素放在数组末尾作为去掉 partition() 中的数组边界测试。
优化代码 NO.1:插入排序+三取样切分
/**
* 快速排序优化
*
* 插入排序+三取样切分
*
* @author TinyDolphin
* 2017/11/14 13:41.
*/
public class QuickBar {
private static final int CUTOFF = 8;
public static void sort(Comparable[] arr) {
//shuffle(arr); // 让数组成为随机数组,避免切分不平衡,带来的低效
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
int n = hi - lo + 1;
// 当子数组的长度为 8 时,调用插入排序
if (n <= CUTOFF) {
insertionSort(arr, lo, hi);
return;
}
// 调用三取样切分
int m = median3(arr, lo, lo + n / 2, hi);
exch(arr, m, lo);
int indexJ = partition(arr, lo, hi); // 切分方法
sort(arr, lo, indexJ - 1);
sort(arr, indexJ + 1, hi);
}
// 插入排序
private static void insertionSort(Comparable[] arr, int lo, int hi) {
for (int indexI = lo; indexI <= hi; indexI++) {
for (int indexJ = indexI; indexJ > lo && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
exch(arr, indexJ, indexJ - 1);
}
}
}
// 选择切分元素:取 arr[i] arr[j] arr[k] 三个元素值的中间元素的下标
private static int median3(Comparable[] arr, int i, int j, int k) {
return (less(arr[i], arr[j]) ?
(less(arr[j], arr[k]) ? j : less(arr[i], arr[k]) ? k : i) :
(less(arr[k], arr[j]) ? j : less(arr[k], arr[i]) ? k : i));
}
// 切分方法
private static int partition(Comparable[] arr, int lo, int hi) {
int indexI = lo; // 左右扫描指针
int indexJ = hi + 1; // 切分元素
Comparable temp = arr[lo];
while (true) {
// 从数组的左端开始,向右端扫描,直到找到一个 >= 切分元素的元素;
while (less(arr[++indexI], temp)) {
if (indexI == hi) break;
}
// 从数组的右端开始,向左端扫描,直到找到一个 <= 切分元素的元素;
while (less(temp, arr[--indexJ])) {
if (indexJ == lo) break;
}
// 指针相遇,退出循环
if (indexI >= indexJ) break;
// 交换他俩的位置(因为显然他俩没有被排定)
exch(arr, indexI, indexJ);
}
exch(arr, lo, indexJ); // 将 temp = arr[indexJ] 放入正确的位置
return indexJ; // arr[lo...indexJ-1] <= arr[indexJ] <= arr[indexJ+1...hi] 达成
}
...
}
③、熵最优的排序
在应对大量重复元素的情况下,我们可以将数组切分为三部分,分别对应 小于、等于和大于 切分元素的数组元素。
三向切分的快速排序
Dijkstra 的解法如“三向切分的快速排序”中极为简洁的切分代码:它从左到右遍历数组一次,维护
一个指针 lt 使得 a[lo...lt-1] 中的元素都 < v;
一个指针 gt 使得 a[gt+1...hi] 中的元素都 > v ;
一个指针 i 使得 a[lt...i-1] 中的元素都 == v,a[i...gt] 中的元素都还未确定。
优化代码 NO.2:三向切分
对于存在大量重复元素的数组,这种方法比标准的快速排序的效率高得多。其他情况,可能不及优化方案 NO.1。
/**
* 快速排序优化:三向切分(用于解决大量重复元素)
*
* @author TinyDolphin
* 2017/11/14 14:12.
*/
public class Quick3way {
public static void sort(Comparable[] arr) {
shuffle(arr);
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
if (hi <= lo) {
return;
}
int lt = lo;
int gt = hi;
Comparable v = arr[lo];
int i = lo;
while (i <= gt) {
int cmp = arr[i].compareTo(v);
// arr[i] < v,交换 arr[lt] & arr[i],将 lt & i 加一
if (cmp < 0) {
exch(arr, lt++, i++);
}
// arr[i] > v,交换 arr[gt] & arr[i],将 gt 减一
else if (cmp > 0) {
exch(arr, i, gt--);
}
// arr[i] == v,将 i 加一
else {
i++;
}
}
// arr[lo...lt-1] < v = arr[lt...gt] < arr[gt+1...hi]
sort(arr, lo, lt - 1);
sort(arr, gt + 1, hi);
}
// 打乱数组的方法
private static void shuffle(Comparable[] arr) {
int length = arr.length;
Random random = new Random(System.currentTimeMillis());
for (int index = 0; index < length; index++) {
int temp = random.nextInt(length);
exch(arr, index, temp);
}
}
...
}
优化代码 NO.3:插入排序+三取样切分+三向切分
优化了三向切分代码,加快了处理大量重复元素的速度,但是其他情况下,速度还是不及NO.1
/**
* 快速排序优化
*
* 插入排序+三取样切分+三向切分
*
* @author TinyDolphin
* 2017/11/14 17:11.
*/
public class Quick3wayBar {
private static final int CUTOFF = 8;
public static void sort(Comparable[] arr) {
//shuffle(arr);
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] arr, int lo, int hi) {
int n = hi - lo + 1;
// 当子数组的长度为 8 时,调用插入排序
if (n <= CUTOFF) {
insertionSort(arr, lo, hi);
return;
}
// 调用三取样切分
int m = median3(arr, lo, lo + n / 2, hi);
exch(arr, m, lo);
int lt = lo;
int gt = hi;
Comparable v = arr[lo];
int i = lo;
while (i <= gt) {
int cmp = arr[i].compareTo(v);
// arr[i] < v,交换 arr[lt] & arr[i],将 lt & i 加一
if (cmp < 0) {
exch(arr, lt++, i++);
}
// arr[i] > v,交换 arr[gt] & arr[i],将 gt 减一
else if (cmp > 0) {
exch(arr, i, gt--);
}
// arr[i] == v,将 i 加一
else {
i++;
}
}
// arr[lo...lt-1] < v = arr[lt...gt] < arr[gt+1...hi]
sort(arr, lo, lt - 1);
sort(arr, gt + 1, hi);
}
// 插入排序
private static void insertionSort(Comparable[] arr, int lo, int hi) {
for (int indexI = lo; indexI <= hi; indexI++) {
for (int indexJ = indexI; indexJ > lo && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
exch(arr, indexJ, indexJ - 1);
}
}
}
// 取 arr[i] arr[j] arr[k] 三个元素值的中间元素的下标
private static int median3(Comparable[] arr, int i, int j, int k) {
return (less(arr[i], arr[j]) ?
(less(arr[j], arr[k]) ? j : less(arr[i], arr[k]) ? k : i) :
(less(arr[k], arr[j]) ? j : less(arr[k], arr[i]) ? k : i));
}
优化代码 NO.4:快速三向切分
优化:插入排序 + 三取样切分 + Tukey's ninther + Bentley-McIlroy 三向切分
Tukey's ninther 方法选择切分元素:选择三组,每组三个元素,分别取三组元素的中位数,然后去三个中位数的中位数作为切分元素。
原理:将重复元素放置于子数组两端的方式实现一个信息量最优的排序算法。
/**
* 三向切分-快速排序优化
*
* 插入排序 + 三取样切分 + Tukey's ninther + Bentley-McIlroy 三向切分
*
* @author TinyDolphin
* 2017/11/15 15:16.
*/
public class QuickX {
private static final int INSERTION_SORT_CUTOFF = 8;
private static final int MEDIAN_OF_3_CUTOFF = 40;
public static void sort(Comparable[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
int n = hi - lo + 1;
// 当子数组大小 <= 8 时,切换到插入排序
if (n <= INSERTION_SORT_CUTOFF) {
insertionSort(a, lo, hi);
return;
}
// 当子数组大小 <= 40 时,使用三取样切分(median-of-3)选择切分元素
else if (n <= MEDIAN_OF_3_CUTOFF) {
int m = median3(a, lo, lo + n / 2, hi);
exch(a, m, lo);
}
// 当子数组大小 > 40 时,使用 Tukey's ninther 方法选择切分元素
else {
int eps = n / 8;
int mid = lo + n / 2;
int m1 = median3(a, lo, lo + eps, lo + eps + eps);
int m2 = median3(a, mid - eps, mid, mid + eps);
int m3 = median3(a, hi - eps - eps, hi - eps, hi);
int ninther = median3(a, m1, m2, m3);
exch(a, ninther, lo);
}
// 使用 Bentley-McIlroy 三向切分
// 使数组 a[lo...p-1] & a[q+1...hi] == v ; a[p...i-1] < a[lo] < a[j+1...q]
int i = lo, j = hi + 1;
int p = lo, q = hi + 1;
Comparable v = a[lo];
while (true) {
// 移动指针,使得 a[p..i-1] < a[lo] == v,直到一个 >= v 的元素a[i]
while (less(a[++i], v))
if (i == hi) break;
// 移动指针,使得 a[lo] == v > a[j+1...q],直到一个 <= v 的元素a[j]
while (less(v, a[--j]))
if (j == lo) break;
// 指针交叉时,刚好 a[i] == v 的情况下,交换以将 a[i] 归位
if (i == j && eq(a[i], v))
exch(a, ++p, i);
// 排序完成,退出循环
if (i >= j) break;
// 交换 a[i] & a[j] 的值,使其归位
exch(a, i, j);
// 如果 a[i] == v,交换 a[p] & a[i],使其归位
if (eq(a[i], v)) exch(a, ++p, i);
// 如果 a[j] == v,交换 a[q] & a[i],使其归位
if (eq(a[j], v)) exch(a, --q, j);
}
// 在切分循环结束后,将和 v 相等的元素交换到正确位置
// 即使数组 a[lo...j-1] < v == a[j...i] < a[i+1...hi]
i = j + 1;
// 把 v == a[lo...p-1] 元素归位到 a[j...i] 中
for (int k = lo; k <= p; k++)
exch(a, k, j--);
// 把 v == a[q+1...hi] 元素归位到 a[j...i] 中
for (int k = hi; k >= q; k--)
exch(a, k, i++);
// 递归调用
sort(a, lo, j);
sort(a, i, hi);
}
// 插入排序
private static void insertionSort(Comparable[] arr, int lo, int hi) {
for (int indexI = lo; indexI <= hi; indexI++) {
for (int indexJ = indexI; indexJ > lo && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
exch(arr, indexJ, indexJ - 1);
}
}
}
// 取 arr[i] arr[j] arr[k] 三个元素值的中间元素的下标
private static int median3(Comparable[] arr, int i, int j, int k) {
return (less(arr[i], arr[j]) ?
(less(arr[j], arr[k]) ? j : less(arr[i], arr[k]) ? k : i) :
(less(arr[k], arr[j]) ? j : less(arr[k], arr[i]) ? k : i));
}
// 判断两个元素是否相等
private static boolean eq(Comparable v, Comparable w) {
return v.compareTo(w) == 0;
}
...
}
优化代码 NO.5:最简单的实现之一
但是碰到大量重复元素的话,可能会变成 O(n²)
/**
* 快速排序最简单的实现方式之一
*
* @author TinyDolphin
* 2017/11/15 16:38.
*/
public class QuickKR {
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
exch(a, lo, (lo + hi) / 2); // use middle element as partition
int last = lo;
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[lo])) exch(a, ++last, i);
exch(a, lo, last);
sort(a, lo, last-1);
sort(a, last+1, hi);
}
...
}
测试代码
public static void main(String[] args) {
int length = 1000000; // 百万数据量级别
Integer[] arr = new Integer[length];
for (int index = 0; index < length; index++) {
// 随机数组
arr[index] = new Random().nextInt(length) + 1;
// 大量重复元素的数组
// arr[index] = new Random().nextInt(100) + 1;
}
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("耗费时间:" + (end - start) + "ms");
}
测试结果
随机数组 | 重复数组 | 升序数组 | 降序数组 | |
---|---|---|---|---|
MergePlus.sort() | 1127ms | 827ms | 60ms | 401ms |
Array.sort() | 1706ms | 1096ms | 30ms | 94ms |
Quick | 1573ms | 900ms | 1343ms | 1242ms |
QuickBar | 846ms | 659ms | 251ms | 溢出 |
Quick3way | 2191ms | 543ms | 1635ms | 1606ms |
Quick3wayBar | 1513ms | 343ms | 11146ms | 11588ms |
QuickX | 1331ms | 553ms | 228ms | 528ms |
QuickKR | 1325m | 21270ms | 347ms | 423ms |
Merge:归并排序
MergePlus:表示快排的优化实现
QuickBar:插入排序+三取样切分
Quick3way:三向切分
Quick3wayBar:插入排序+三取样切分+三向切分
QuickX:快速三向切分(插入排序 + 三取样切分 + Tukey's ninther + Bentley-McIlroy 三向切分)
QuickKR:快速排序的最简单实现方式之一
Q:QuickBar 排序降序数组时,为什么报
java.lang.*Error 异常?*
A:因为调用层次过多
解决方案:排序之前调用 shuffle() 方法打乱数组即可,但是对效率有所影响。
总结
由上表可知:
①、在处理随机数组的时候,QuickBar(插入排序+三取样切分)速度较快
②、在处理大量重复元素数组的时候,Quick3wayBar(插入排序+三取样切分+三向切分)速度最快。
③、综合表现最好的是:QuickX(快速三向切分(插入排序 + 三取样切分 + Tukey's ninther + Bentley-McIlroy 三向切分)
注意:编译器默认不适用 assert 检测(但是junit测试中适用),所以要使用时要添加参数虚拟机启动参数-ea 具体添加过程,请参照eclipse 和 IDEA 设置虚拟机启动参数
下一篇: Spring学习笔记
推荐阅读
-
[排序算法] VII.快速排序补充:三指针 + 随机数方法
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
快速排序技巧:掌握高效的序列排列方法
-
逐步改进快速排序方法详解
-
三种快速排序方法及其效率提升技巧
-
加速排序新技巧:双路快速排序方法详解
-
几种改进快速排序的方法
-
三大改进策略优化快速排序算法
-
四款改进快速排序的方法
-
加速排序新技巧:三路快速排序方法详解