《快速排序问题》由会员分享,可在线阅读,更多相关《快速排序问题(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