《快速排序问题》由会员分享，可在线阅读，更多相关《快速排序问题（6页珍藏版）》请在金锄头文库上搜索。
1、page 1 of 6 作 2015速 张 1 有1,000,000个乱 数据 数据 执行速 。2 fl 本 在Windows 8.1fl 下 。3 步(1) 先生包含1,000,000个 机数（数据类 选整 或者浮 ） 数据 ；(2) 次数据分割后生两个 程（或程）处理分割后 数据，个 程（程）处理数据小 1000 后不 分割（制生 程在20个 ）；(3) 程（或 程）之 通 选下 机制之一 行：道（ 名道或命名道）息队列共 存(4) 通适当 数调用创上 IPC象，通调用适当 数调用 数据 与 入；(5) 需 考虑程（或 程） 同步；(6) 程（或 程）行 束，通适当 调用 束程（或 程）4
2、 思 由 速 具有 分 特，通多程并 行 到 速 效。 先一个程 数据 行划分（Partition）， 到两个区 分别两个程 行处理， 到数据数小 1000 不 划分，而是 成 。 遇到 一个 ，就是 制程数在20个 。考虑到数据 大， 按上 需 同 20个程，用20个程则 为各程均未到 长小 1000 区 而生死锁。故需 入程 分配机制。1page 2 of 6 作 2015考虑静态20个程，同 一个队列unsorted，队列中 元素为 区 尾 。为队列元素 置一个资 ，表示队中元素个数，初值为0。初 将整个数据 尾 入队列。个程执行 数队中 元素， 区 长小 1000，则 成 ，否则 划分
3、，并将 到 两个区 入队列， 样 使程数制在20个并且不生死锁。 判 束， 置一个共 sortedNum 录 好 数据 数，一次划分sortedNum 1，次 sortedNum r p + 1，当 到总数据个数 ，将标 End置为true，即 通 各程止。个程执行 程 伪码 下：CODE 1: Function for each threadvoid Parallel_Quicksort(char* shrmem)/ shrmem is the name of shared memoryHANDLE hMapSrc;hMapSrc = OpenFileMapping(shrmem);/ ge
4、t the starting address of the mapped view.int *pBuf = (int *)MapViewOfFile(hMapSrc, BUF_SIZE);/* Waiting to get sorting job fromthe unsorted queue while sort not finished*/while (!End & P(N_unsorted)P(queue);/ fetch job from unsortedParam param0 = unsorted.front();unsorted.pop();V(N_unsorted);/ fini
5、sh the sort itself when number p = param0.p; param1-r = q - 1; / interval to sortparam2-p = q + 1; param2-r = param0.r; / interval to sortP(queue);/ add two jobs to queueunsorted.push(*param1);unsorted.push(*param2);ReleaseSemaphore(N_unsorted, 2, NULL);V(queue);主 数 下：CODE 2: Main Function#define AM
6、OUNT 1000000 / total amount of data#define BUF_SIZE 4000000 / total size of data#define MAX_THREAD_NUM 20 / max number of threadssemaphore Nsorted = 1; / for sortedNumsemaphore queue = 1; / for unsorted queuesemaphore N_unsorted = 0; / semaphore for jobs in queuesemaphore finished = 0; / for Endint
7、sortedNum = 0; / indicating the number of sorted databool End = false; / indicating the accomplishment of sortchar* srcMapName = Global/srcMap; / name of the mapped fileclass Param / Parameter for the sorting jobpublic:int p; / frontint r; / tail;queue unsorted; / containing the jobvoid Parallel_Qui
8、cksort(char* shrmem);int main()/ Create file mappingHANDLE hSrc = CreateFile(source.dat);HANDLE hMapSrc = CreateFileMapping(hSrc, srcMapName);int* pBuf = (int *)MapViewOfFile(hMapSrc, BUF_SIZE);HANDLE hThreadMAX_THREAD_NUM;/ Initialization/ Creating MAX_THREAD_NUM threads to process the datafor (int
9、 i = 0; i p = 0;param0-r = AMOUNT - 1;P(queue);unsorted.push(*param0);V(N_unsorted);V(queue);P(finished); / waiting for the job to finish/ writes all contents in the mapped view to the diskFlushViewOfFile(pBuf, BUF_SIZE)return 0;5 行 程 够正确行，效 下：1: 程 行 4page 5 of 6 作 20152: 入 （转换成 本 后）分别使用多程 单程 行 ， 数据
10、 机生成， 下表 1: 两 效 单程/s 多程/s1 1.116 0.5812 1.067 0.5493 1.219 0.6214 1.068 0.6175 0.537 1.104表中 ，多程 够 。 上 ，程 够正常 作。5page 6 of 6 作 20156 思考 1. 你用 你选 机制而不是 外 两机制 ， 你做 选 理由。答： 为本次 是 行速 ，多个 程同 一个数 行作。使用共 存 共数据，一 一个 程向共 存中 入数据，其 程 刻看到 一 化。而 使用道或 息队列 行 ，需 有子 程向主 程传 处理后 数据， 样效 低。2. 你为 外 两机制是否同样 ？ 你 思 ； 不 ， 理由。答： 。一个主 程，负责创子 程 将数据通道或 息队列传 子 程 行处理。子 程处理 后将数据 分割息通道或 息队列传 主 程，然后主 程 两个子 程 处理数据。7 体会上次同步 习，我 够 为 使用 、 等机制 程（程） 同步 。本次 我选 共 存 行 程 通，通在MSDN上 学习，我 够正确 使用 式 行 程 通，同 我共 存 理也有 理。本 我一个引 ，即 使用多程 术 速 ，虽然 是个挺 程 术，但在 处理器向多核、并行化处理 展 下，并行 是 有意义 。6
