共享内存

    // 创建共享文件句柄
    HANDLE hMapFile = CreateFileMapping(
        INVALID_HANDLE_VALUE,    // 物理文件句柄
        NULL,                    // 默认安全级别
        PAGE_READWRITE,          // 读写权限 
        0,                       // 文件映射的最大长度的高32位
        BUF_SIZE,                // 文件映射的最大长度的低32位
        buffname                 // 共享内存名称
        );
    // 内存读取指针 
    int*pBuff = (int*)MapViewOfFile(// 返回的是char*,转换成我们需要的int* 
        hMapFile,                // 共享文件的句柄 
        FILE_MAP_ALL_ACCESS,     // 读写权限 
        0,                         // 文件映射起始偏移的高32位
        0,                       // 文件映射起始偏移的低32位
        BUF_SIZE                 // 共享内存大小 
        );

信号量

// 创建一个信号量来统计当前进程个数,控制最大线程数量 
    HANDLE threadcount = CreateSemaphore(
         NULL,                     // 信号量安全参数 
         maxthread,                // 信号量初始值 
         maxthread,                // 信号量最大值 
        "threadcount"             // 信号量的名称 
        ); 
        WaitForSingleObject(Handle,time)
        ReleaseSemaphore(Handle,number,returnlast)

多线程快速排序

利用多线程可以快一倍左右

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#include<atomic>
#include<thread>
#include<mutex>
#include<condition_variable>
#include<windows.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
// 数据量比较大,利用getchar读入优化加快程序读入数据的速度 
int readint(){
    int ans=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return f*ans;
}
// 数据量比较大,利用putchar输出优化加快程序输出数据的速度 
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
#define maxn (5000000)
#define BUFF_SIZE (20000000+8)
#define minlen (100000)
#define countcontrol (1)
int a[maxn];
// 单线程快速排序 
// 排序从l到r的一段int(闭区间) 
void Singlethread_Qsort(int*l,int*r){
    int mid=*(l+((r-l)>>1)),*L=l,*R=r;
    while(R-L>=0){
        while(*(L)<mid) L++;
        while(*(R)>mid) R--;
        if(R-L>=0) swap(*(L++),*(R--));
    }
    if(L-r<0) Singlethread_Qsort(L,r);
    if(l-R<0) Singlethread_Qsort(l,R);
}
// 用于进程传递参数的结构体 
struct info{
    int*l,*r,*cnt;// 当前排序段的范围 
    HANDLE threadcount;// 信号量 
    info(int*L=NULL,int*R=NULL,int*Cnt=NULL,HANDLE Threadcount=NULL)
        :l(L),r(R),cnt(Cnt),threadcount(Threadcount){}
};
// 多线程快速排序 
void Multithread_Qsort(LPVOID Notype_pPara){
    info*pPara = (info*)Notype_pPara;// 从无类型指针转为我们需要的info* 
    int*l = pPara->l,*r = pPara->r,*cnt = pPara->cnt;
    HANDLE threadcount = pPara->threadcount;
    // 输出当前处理区间 
    //cout<<"now:"<<(l+maxn-cnt)<<' '<<(r+maxn-cnt)<<endl;
    int mid=*(l+((r-l)>>1)),*L=l,*R=r;
    while(R-L>=0){
        while(*(L)<mid) L++;
        while(*(R)>mid) R--;
        if(R-L>=0) swap(*(L++),*(R--));
    }
    HANDLE L_thread = NULL,R_thread = NULL;
    info new_Para_L(NULL,NULL,cnt,threadcount),new_Para_R(NULL,NULL,cnt,threadcount);
    info*new_pPara_L = &new_Para_L,*new_pPara_R = &new_Para_R;
    if(L-r<0){
        if(r-L+1>minlen){// 数据超过minlen个才创建子进程 
            new_pPara_L->l = L;
            new_pPara_L->r = r; // 修改传递参数的结构体    
            WaitForSingleObject(threadcount, INFINITE);// 等待线程数,减少信号量的值
            (*cnt)++;
            (*(cnt+1)) = max((*(cnt+1)),(*cnt));
            ReleaseSemaphore(threadcount,1,NULL);// 释放线程数,增加信号量的值 
            R_thread = CreateThread(
                NULL,                     // 线程安全相关属性,一般置为NULL 
                0,                       // 初始栈大小 
                (LPTHREAD_START_ROUTINE)Multithread_Qsort,       // 线程执行函数,需要转换格式 
                new_pPara_L,               // 传入线程的参数结构体指针 
                0,                       // 线程创建属性,0即创建后马上激活 
                NULL                     // 是否返回线程ID,NULL不返回 
                );
        }else Singlethread_Qsort(L,r);// 数据小于等于minlen个直接调用单线程排序即可 
    }
    if(l-R<0){
        if(R-l+1>minlen){// 数据超过minlen个才创建子进程
            new_pPara_R->l = l;
            new_pPara_R->r = R; // 修改传递参数的结构体    
            WaitForSingleObject(threadcount, INFINITE);// 等待线程数,减少信号量的值
            (*cnt)++;
            (*(cnt+1)) = max((*(cnt+1)),(*cnt));
            ReleaseSemaphore(threadcount,1,NULL);// 释放线程数,增加信号量的值 
            L_thread = CreateThread(
                NULL,                     // 线程安全相关属性,一般置为NULL 
                0,                       // 初始栈大小 
                (LPTHREAD_START_ROUTINE)Multithread_Qsort,       // 线程执行函数,需要转换格式 
                new_pPara_R,               // 传入线程的参数结构体指针 
                0,                       // 线程创建属性,0即创建后马上激活 
                NULL                     // 是否返回线程ID,NULL不返回 
                );
        }else Singlethread_Qsort(l,R);// 数据小于等于minlen个直接调用单线程排序即可     
    }
    if(L_thread != NULL){
        WaitForSingleObject(L_thread,INFINITE);
        WaitForSingleObject(threadcount, INFINITE);// 等待线程数,减少信号量的值
        (*cnt)--;
        ReleaseSemaphore(threadcount,1,NULL);// 释放线程数,增加信号量的值 
    }
    if(R_thread != NULL){
        WaitForSingleObject(R_thread,INFINITE);
        WaitForSingleObject(threadcount, INFINITE);// 等待线程数,减少信号量的值
        (*cnt)--;
        ReleaseSemaphore(threadcount,1,NULL);// 释放线程数,增加信号量的值 
    }
}
bool flag = 1;//0 single or 1 multi
int main(){
    clock_t start,finish;
    
    //std::ios::sync_with_stdio(false);// 关闭流同步,加快速度 
    // 读入数据 
    freopen("#test.in","r",stdin);
    rep(i,0,maxn-1)
        a[i] = readint();
    
    if(flag == 0){// 单线程排序 
        start = clock();
        Singlethread_Qsort(a,a+maxn-1);
        finish = clock();
        printf("single thread time cost: %d ms\n",(int)(finish-start));
        
        // 向文件输出结果
        printf("Now output...\nIt may cost some time\nPlease wait\n");
        freopen("#test.out","w",stdout);
        rep(i,0,maxn-1){
            printint(a[i]);
            putchar('\n');
        }
        
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    // 多线程快速排序 
    start = clock();
    // 创建共享文件句柄
    HANDLE hMapFile = CreateFileMapping(
        INVALID_HANDLE_VALUE,    // 物理文件句柄
        NULL,                    // 默认安全级别
        PAGE_READWRITE,          // 读写权限 
        0,                       // 文件映射的最大长度的高32位
        BUFF_SIZE,               // 文件映射的最大长度的低32位
        "shared_buff"            // 共享内存名称
        );
    // 内存读取指针 
    int*pBuff = (int*)MapViewOfFile(// 返回的是char*,转换成我们需要的int* 
        hMapFile,                // 共享文件的句柄 
        FILE_MAP_ALL_ACCESS,     // 读写权限 
        0,                         // 文件映射起始偏移的高32位
        0,                       // 文件映射起始偏移的低32位
        BUFF_SIZE                // 共享内存大小 
        );
    memcpy(pBuff,a,BUFF_SIZE-8);// 将数据复制到共享内存中
    pBuff[maxn] = 1;// 倒数第二位记录当前线程数
    pBuff[maxn+1] = 1;// 倒最后一位记录线程数最大值 
    // 在屏幕上输出共享内存中内容 
    //rep(i,0,maxn-1)
    //    printf("%d ",pBuff[i]);
    //putchar('\n');
    // 创建一个信号量来统计当前进程个数,控制最大线程数量 
    HANDLE threadcount = CreateSemaphore(
         NULL,                     // 信号量安全参数 
         countcontrol,                // 信号量初始值 
         countcontrol,                // 信号量最大值 
        "count"             // 信号量的名称 
        ); 
    // 创建主进程
    info Para(pBuff,pBuff+maxn-1,pBuff+maxn,threadcount); // 传递参数的结构体
    info* pPara = &Para;
    HANDLE main_thread = CreateThread(
        NULL,                     // 线程安全相关属性,一般置为NULL 
        0,                       // 初始栈大小 
        (LPTHREAD_START_ROUTINE)Multithread_Qsort,       // 线程执行函数,需要转换格式 
        pPara,                   // 传入线程的参数结构体指针 
        0,                       // 线程创建属性,0即创建后马上激活 
        NULL                     // 是否返回线程ID,NULL不返回 
        );
    // 等待排序结果 
    WaitForSingleObject(main_thread,INFINITE);
    finish = clock();
    // 在屏幕上输出排序结果,调试用 
    //rep(i,0,maxn-1)
    //    printf("%d ",pBuff[i]);
    //putchar('\n');
    printf("multi thread time cost: %d ms\n",(int)(finish-start));
    printf("max thread used: %d\n",pBuff[maxn+1]);
        
    // 向文件输出结果 
    printf("Now output...\nIt may cost some time\nPlease wait\n");
    freopen("#test.out","w",stdout);
    rep(i,0,maxn-1){
        printint(pBuff[i]);
        putchar('\n');
    }
    
    // 取消共享内存,关闭句柄 
    UnmapViewOfFile(pBuff);
    CloseHandle(hMapFile);
    CloseHandle(threadcount);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
Last modification:June 8th, 2020 at 12:13 am
如果觉得我的文章对你有用,请随意赞赏