专栏首页C/C++基础OpenMP并行加速笛卡尔乘积

OpenMP并行加速笛卡尔乘积

1.字典字符集的笛卡尔乘积

问题描述: 对于给定的由字典字符集组合而成的表达式,求该表达式构成的所有元素。例如表达式[0-9][a-z],其中0-9表示10个数字,a-z表示26个小写字母,构成的所有元素就是0a,0b,…,0z,1a,1b,…9z。字典字符集的笛卡尔乘积示意如下:

问题分析: 对于任意的一个字典字符集构成的表达式[dic0][dic1]...[dicn],从左至右可以看作按照高位到低位的一个由字典元素组成的一个“数”,这样比较符合我们日常表示数值的高低位的习惯。比如如果字典都是[0-9],那么表达式[0-9][0-9]表示的就是一个数值字符串00~99。笛卡尔乘积的空间是各个字典高度的乘积,给定其空间中的任意一个元素下标,就可以对应到每个字典中的元素下标。比如[0-9[0-9]的笛卡尔乘积的空间是各个字典高度的乘积10*10=100,空间中第0个元素就是00,第99个元素就是99。

每一个字典元素都有一个位权重。表达式[0-9[0-9] 从左至右第一个字典的位权重w=10,第二个字典的位权重w=1。我们平常所说的个位、十位、百位,就是根据数值位的位权重来称呼它。位权重的意义在于,数值是其位权重的多少倍,那么它就取第几个元素。比如第99个元素(下标从0开始),那么数值99是十位的位权重w=10的9倍,所以元素为字符‘9’,对数值99取w=10的余数得9,同理9是个位的位权重w=1的9倍,所以元素为字符’9’,所以构成了字符串99。

实现示例: 对表达式[0-9][a-z[A-Z],其实现笛卡尔乘积的具体过程可以描述如下: (1)对从左至右(高位到低位)将各个字典字符集的所在数位的计算单位计算出来,由当前字典右边的字典的高度相乘得到,如[0-9]的计数单位w=26*26=676,[a-z]的计数单位w=26*1=26,[A-Z]的计数单位w=1。 (2)给定笛卡尔乘积空间的元素下标i,根据i找到各个字典内的元素下标的过程如下,从高位开始查找,即从左开始查找。 (2.1)查找字典[0-9]中的元素下标:[0-9].index=i/[0-9].w; (2.2)查找字典[a-z]中的元素下标[a-z].index:i=i%[0-9].w; [a-z].index=i/[a-z].w; (2.3)查找字典[A-Z]中的元素下标[A-Z].index:i=i%[a-z].w;[A-Z].index=i/1=i。 (3)将i=0递增至笛卡尔乘积的空间大小减一,即10*26*26-1,重复步骤2,即可完成表达式[0-9][a-z[A-Z]的笛卡尔乘积。

例如给定第677个笛卡尔乘积的元素,那么[0-9].index=1,所以取[0-9]内的素‘1’,[a-z].index=671%676/26=0,所以取出元素‘a’,[a-z].index=1/1=1,所以取出元素‘B’,所以第677个元素就是“1aB”。

2.源码

以下代码在Linux平台编译运行,稍作修改可移植到Windows平台。其功能是完成多个字典字符集的笛卡尔乘积。并通过OpenMP并行加速。正确性已在实际项目中通过验证。

#include <pthread.h>
#include <omp.h>

#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef unsigned char uint8;

//字典字符集与段字符集
struct charset_mem{
    int high,width;                     //字符集的宽度和高度
    int mem_size;                       //字符集data所占用的内存,单位字节
    uint8 *data;                        //字符集的数据
    char name[128];                     //字符集名称
};

map<string,charset_mem*> dic_utf8_charset_map; //全局字典字符集缓存
map<string,charset_mem*> dic_ucs2_charset_map; //全局字典字符集缓存
map<string,charset_mem*> seg_charset_map;      //全局段字符集缓存

pthread_mutex_t charset_mutex; 

//功能:根据多个字典字符集生成相应的笛卡尔乘积
//参数:charsetID:笛卡尔乘积结果字符集名称,dicNum:字典字符集数目,dicName:字典字符集名称数组指针,encode:字典字符编码类型
//返回值:成功返回true,失败返回false
bool cartesianProduct(string charsetID,  int dicNum, char(*dicName)[128],uint8 encode)
{
        pthread_mutex_lock(&charset_mutex);    //对字符集的map关联容器修改需要加锁
        string charsetNewedID=charsetID;
        map<string,charset_mem*>::iterator iter;

        charset_mem* segNewedCharset=new charset_mem;
        memset(segNewedCharset,0,sizeof(charset_mem));
        strcpy(segNewedCharset->name,charsetNewedID.c_str());

        #define MAX_WORD_LEN 40
        #define MAX_DIC_NUM 32

        //笛卡尔乘积(cartesian product)准备工作
        map<string,charset_mem*>&  dic_charset_map=(0==encode)?dic_utf8_charset_map:dic_ucs2_charset_map;
        int high=1,width=0;
        int s[MAX_DIC_NUM]={0};                         //字典段进制位
        for(int i=dicNum-1; i>=0; --i){
            cout<<"dicName["<<i<<"]:"<<dicName[i]<<endl;
            iter=dic_charset_map.find(dicName[i]);
            if(iter==dic_charset_map.end()){
                cout<<dicName[i]<<"do not exist"<<endl;
                pthread_mutex_unlock(&charset_mutex);
                return false;
            }
            s[i]=high;
            high*=iter->second->high;
            width+=iter->second->width;
        }

        segNewedCharset->high=high;
        segNewedCharset->width=width;
        segNewedCharset->data=new uint8[high*width];    

        //笛卡尔乘积
        int thread_num=omp_get_max_threads();//获取处理器最大可并行的线程数
        #pragma omp parallel for num_threads(thread_num) 
        for(int i=0;i<high;++i){
            uint8 wordTmp[MAX_WORD_LEN]={0};
            map<string,charset_mem*>::iterator iterTmp;
            int offset=0;
            int charpos=i;          
            for(int j=0;j<dicNum;++j){
                iterTmp=dic_charset_map.find(dicName[j]);   
                int indexDic=charpos/s[j];
                int offsetDic=indexDic*iterTmp->second->width;
                memcpy(wordTmp+offset,iterTmp->second->data+offsetDic,iterTmp->second->width);
                charpos=charpos%s[j];
                offset+=iterTmp->second->width;
            }
            memcpy(segNewedCharset->data+i*segNewedCharset->width,wordTmp,segNewedCharset->width);
        }

        //将结果字符集添加到,map映射表
        seg_charset_map.insert(pair<string,charset_mem*>(charsetNewedID,segNewedCharset));
        pthread_mutex_unlock(&charset_mutex);
        return true;
}

3.优化

写毕业论文的时候,经实验室的小伙伴提醒,发现其实不用事先求出各个字典所在数位的计数单位,也可以根据给定的笛卡尔乘积的元素下标唯一的找到各个字典中对应的元素。为了避免与论文查重时重复,只贴出图片。具体实现已经抽象为如下算法:

算法中注释中的热词就是上文提到字典,其实现的原理是从表达式的低位到高位计算每一个字典的元素下标,上面未优化的方法是从高位到低位顺序计算。从低位到高位来计算的话,无需事先求出各个字典位的计数单位。因为:当字典位的计数单位的为w=1时,可以通过笛卡尔乘积的元素下标i对其高度h取余,即得到最低字典位字典内的元素下标。当对下一个字典求其元素下标时,需要将下一个字典位的计数单位w’变为1,具体做法就是i除以当前字典的高度向下取整。依次类推,就可以求出各个字典内的元素下标了。具体描述见上面的算法。

以表达式[0-9][a-z[A-Z],求笛卡尔乘积中第677个(从0开始)元素的各个字典内的元素下标的过程描述如下: (1)求字典[A-Z]的元素下标index=i%[A-Z].h=677%26=1,所以去元素’B’; (2)求字典[a-z]的元素下标index: (2.1)将[a-z]的计数单位变为1,做法是i=i/[A_Z].h=677/26=26; (2.2)求[a-z].index=i%[a-z].h=26%26=0。所以取元素’a’。 (3)求字典[0-9]的元素下标index: (3.1)将[0-9]的计数单位变为1,做法是i=i/[a_z].h=26/26=1; (3.2)求[a-z].index=i%[0-9].h=1%10=1。所以取元素’1’。 所以第677个笛卡尔乘积的元素就是“1aB”,与上面的算法殊途同归。

4.再优化

仔细阅读上面的算法描述,你会发现算法的内层循环存在重复的字典元素拷贝,比如笛卡尔乘积元素下标0~25对应的字典[0-9]和[a-z]内的元素下标始终是0,那么就重复拷贝了[0-9]和[a-z]中元素25次。针对该问题,可以对上面的算法做进一步的优化。

以一次字典元素拷贝作为基本操作, 那么第二小节和第三小节的时间复杂度是O(hn),h为笛卡尔乘积空间大小,n为字典个数。

再优化算法描述如下:

再优化步骤描述如下: (1)选取高度最高的字典SkS_k; (2)循环h次,h为其它字典高度的乘积; (2.1)将其它字典元素拼接在一起; (2.2)循环最高字典高度HkH_k次,k为最高字典的下标,将元素填充到临时字符串s中后,将s加入笛卡尔乘积集合。

时间复杂度为O(h0h_0(n-1)+h0h1h_0h_1)=O(h0h_0(h1+n−1h_1+n-1))。其中h0h_0为非最高字典高度乘积,h1h_1为最高字典高度,n为字典个数,n≥2n\ge2。上文中未优化的时间复杂度是优化后的倍数t=h0h1nh0(h1+n−1)=n1+n−1h1t=\frac{h_0h_1n}{h_0(h_1+n-1)}=\frac{n}{1+\frac{n-1}{h_1}},可见,n和h1h_1越大,优化效果越明显。假设h1h_1很大,那么优化的倍数大约为字典的个数。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux命令(67)——time 命令

    版权声明:感谢您对博文的关注!校招与社招,有需要内推腾讯的可以QQ(1589276509)or 微信(loui...

    Dabelv
  • shell编程知识点集锦

    shell脚本是按行分隔每一条shell语句。如果每一条shell语句写在单独一行,此时可以加分号,也可以不加,没有什么区别。如果多条shell写在同一行,那么...

    Dabelv
  • Linux 命令(116)—— tac 命令

    tac(cat 的反序)命令以行为单位反序输出文件内容,即第一行最后显示,最后一行先显示。功能和 cat 命令相反。

    Dabelv
  • head的内容被解析到了body里解决办法

    在搭建完服务器环境部署项目时出现一个奇葩问题,发现线上项目手机端head里的内容被解析到了body里,并且在body后面会出现了一片空白,一开始认为是实体空...

    素描
  • 深职院联合腾讯教育为教师打造企业级实训课 培养创新应用型人才

    ? 随着信息技术新时代的来临,基于互联网的知识获取方式,以及人工智能、大数据等技术的普及推广,教师队伍信息化素养的提高迫在眉睫。为应对新一代信息技术对教育提出...

    鹅老师
  • 顶级评委“天团”亮相,强势围观百万奖金争夺战

    2020腾讯广告算法大赛已于4月15日正式开启线上报名,自赛事开展以来受到了高等院校及一线企业等多领域技术人才的广泛关注。目前大赛报名火热进行中,欢迎各方技术...

    腾讯智能钛AI开发者
  • 夯实Java基础系列20:从IDE的实现原理聊起,谈谈那些年我们用过的Java命令

    那好,不如咱们先来了解一下IDE的实现原理,这样一来,即使离开IDE,我们还是知道如何运行Java程序了。

    Java技术江湖
  • 鹅厂这波青年用“云”监测云

    引言 “绿水青山,就是金山银山”,随着我国加强立法,大力投入环境治理,大家已经明显感觉到身边的大气环境在不断改善,那么除了国家气象局的城市级监测数据外,我们身...

    腾讯云数据库 TencentDB
  • 腾讯WeTest亮相—腾讯全球数字生态大会现场

    原文链接:https://wetest.qq.com/lab/view/460.html

    WeTest质量开放平台团队
  • SDN探索,互联网巨头在路上

    编者按:华三和腾讯在SDN方面达成了新的合作,双方优势互补必将能加速SDN的落地,SDN道路越走越宽了。 汹涌的下一代互联网发展热潮中,SDN步步紧逼,蓬勃兴起...

    SDNLAB

扫码关注云+社区

领取腾讯云代金券