精华内容
下载资源
问答
  • 串行算法并行化处理的数学模型与算法描述
  • 凸壳串行算法

    千次阅读 2006-12-20 19:46:00
    关于凸壳的串行算法,可以说有好多种,有时间复杂度O(n^2)的,也有O(nlogn)的,下面依次介绍几种算法:1,我认为最土的一种方法,时间复杂度为O(n^2) 叫做 卷包裹法由Chand 和 Kapur 于1970年提出,基本思想:...

    关于凸壳的串行算法,可以说有好多种,有时间复杂度O(n^2)的,也有O(nlogn)的,下面依次介绍几种算法:

    1,我认为最土的一种方法,时间复杂度为O(n^2) 叫做 卷包裹法

    由Chand 和 Kapur 于1970年提出,基本思想:首先过y坐标最小的点p1画一条水平直线L,显然该点是凸壳的一个顶点。然后L绕p1按逆时针方向旋转,碰到S(顶点集合)中的第二个点p2时,直线绕p2按逆时针旋转而在p1,p2之间留下一条线,该线段为凸壳的一条边。继续旋转下去,最后直线L旋转360度回到p1,便得到所求的凸壳

    直线L绕点pi旋转式通过一下方法实现的:首先连接Pi与非凸壳顶点Pj,j = i+1,...,n,得到线段PiPj,然后求这些线段与L(线段Pi-1Pi)的夹角,组成最小夹角的另一端点Pi+1就是凸壳顶点

    这个很显然时间复杂度为O(n^2),伪代码在此就省略了!

    注意一点:就是当有三点或者以上的点共线时,如果只能算两个端点上的点,中间的其他点不计,在算法执行中要另外判断,当最小角度有好几个的时候,要选一个距离最远的一个点

    2,最优的求凸壳算法:格雷厄姆方法

      1972年,格雷厄姆发表的一篇题为"An efficient algorithm for determining the convex hull of a finite planar set"的著名论文中所提出的方法

      主要依据是凸边的定义:凸多边形的各顶点必在该多边形的任意一条边的同一侧。

      此方法步骤如下:

      1,设凸集中y坐标最小的点为p1,把p1同凸集中其他各点用线段连接,并计算这些线段与水平线的夹角。然后按夹角大小及到p1的距离进行词典分类(先按夹角的大小排序,当夹角一样时,按到p1的距离进行排序),得到一个序列p1,p2,...,pn,依次连接这些点,便得到一个多边形。p1点是凸壳边界的起点,p2与pn也必是凸壳的顶点。Pn+1 = P1!还不知道如何插入图片,现在先用如下简陋的图表示一下,按顶点编号连成一个多边形

                 。6

            7 。      。4  

                 。5    

                                8 。     。3

                            。9          。2

                                                   。1

        大概判断过程:

        k=4,向前倒查,p1与p4在Pk-1Pk-2两侧,所以p3不在凸壳边界上,删去p3,原p4成为p3,之后p1和p4在Pk-1Pk-2同侧,p3暂时在边界上,继续查下去,最后可以得到凸壳的6个顶点

      2,删去p3,p4,...,pn-1中不是凸壳上的点,方法如下:

     begin

    1  k = 4

    2  j = 2

    3 if P1 和 Pk 分别在线段Pk-j+1 Pk-j两侧 then 删去 Pk-1,后继顶点编号减1,k = k-1,j = j-1

       else Pk-1暂为凸壳顶点,并记录

    4 j = j+1 ,go to 3,直到 j = k-1

    5 k = k+1,go to 2,直到 k = n+1//注意,因为节点编号随着节点的删除是在不断减少的,所以在算法过程中n也是在不断减少的

    end

    3,顺序输出凸壳顶点

    其中:判断两点在某一个线段两侧还是同侧,用向量叉乘就行了

    比如说有两点p,q,线段AB则计算向量pA,pB,qA,qB;在计算叉乘pA*pB,qA*qB如果同号说明在线段同侧,否则在异侧!另外如果计算出现零,则说明那一点在那个线段上,即出现多点共线的情况

    算法分析:由于点集有n个点,步骤2中转移到2的次数不会超过n,每一个顶点至多删去1次,删去顶点的个数也不可能超过n。因此步骤2是线性时间复杂度;步骤1很显然涉及到角度的排序问题,为O(nlogn)复杂度;所以总共需要O(nlogn)时间,此算法为最优算法!因为可以证明凸壳的最优算法的下界就是OMIGA(nlogn)

    3 分治算法

     Preparata 和 Hong 1977年 把分治算法首先应用于凸壳问题,为了描述问题方便,还是假定没有3点共线(其实共线的处理方法也很简单)

    算法:

      输入: n个点集合

      输出:返回凸壳的顶点列表

      Procedure SEQUENTIAL CONVEX HULL(S,CH(S))

     Begin

        if |S|<= 3 then  CH(S) = S

       else  /*把S分为两组大小近似的S1,S2,递归调用*/

                 1    SEQUENTIAL CONVEX HULL(S1,CH(S1))

                 2    SEQUENTIAL CONVEX HULL(S2,CH(S2))

                 3    ./*归并*/ O(n)

                   Merge CH(S1) and CH(S2) into CH(S)

        end if

    end

    t(n) = O(nlogn)

    下面介绍归并算法:

    1,在S1内部找一个点p,必须是S中的点

    2,if p 不在 S2的内部 then goto 4

    3,p在S2内部,S1,S2的各顶点与p连接,并按夹角大小进行分类,得到S1,S2顶点的一个分类表,goto 5

    //O(n)!相当于把2个按夹角分类的有序的顶点合并成一个按夹角有序的顶点

    4,计算p与S2的正切线,得到正切点u,v。相当于通过删除若干条边使得把p添加到多边形S2中,再根据类似4的做法,得到一个按夹角分类的顶点分类表  //O(n)

    5, 在顶点分类表上执行格雷厄姆方法的第二个步骤,就可以得到一个合并的凸壳了// O(n)

    还有其他几种方法,包括实时凸壳算法,近似凸壳算法,在此就不介绍了,有可能会在其他环境下介绍

    以上内容主要参考了 周培德 著的 计算几何-算法设计与分析 第二版的相关内容

    展开全文
  •  串行算法描述是:找出集中点x坐标值的最小值和最大值的两个极限点pmin和pmax,显然此二值极点位于土包边界上。用直线连接pmin和pmax,则点集中的点部分位于上方部分位于下方,显然点集的最小凸包右这两部分组成...

           对简单多边形P而言,其小凸包pc是这样一个多边形,如果存在包含p的另一多边形p0,则pc是p0的子集,因此pc是包含p的最小的凸多边形。

    1. 硬币算法

    首先介绍的算法称为硬币算法,具有逻辑简单,容易实现,并且效率较高的优点。其描述如下:

    1.找一个必在凸包上的点,通常取纵坐标最小的点,记为P0。
    2.连结 P0 与其他点,按照顺时针方向对这些线排序。(左转判定:这是经典的计算几何学问题,判断向量 p1=(x1,y1)到 p2=(x2,y2)是否做左转,只需要判断 x1*y2-x2*y1 的正负,如果结果为正,则从 p1 到 p2 做左转。)
       现在就看看斯卡兰斯奇三硬币算法:
       1.预处理:将各点排序。 
       2.在 P0、P1、P2 上分别放置一枚硬币;
        把这三枚硬币分别命名为“后” 、 “中” 、 “前”。
       3.反复
        如果三枚硬币按“后-中-前”的顺序“做左转”
          拿起“后”,放在“前”的前面;
            将原先的“后”改名为“前” ;
            将原先的“前”改名为“中” ;
            将原先的“中”改名为“后” ;
          否则
            拿起“中”,放在“后”的后面;
            移除刚才“中”所在的点;
            将原先的“中”改名为“后” ;
            将原先的“后”改名为“中” ;
        直到“前”盖在 P0 上,且三枚硬币“做左转”
    4.按照编号大小顺此连结剩下的点(编号最大的点连回 P0),
      得到的多边形就是给定点集的凸包。
    算法实现:
    private void coin()//硬币算法实现
            {
                myar.Clear();//每次进行对myar的数据进行清零,myar为存储硬币算法的点数据的ArrayList
                int p = 0;
                for (int i = 0; i < thear.Count; i++)
                {
                    if (((zuobiao)thear[p]).y > ((zuobiao)thear[i]).y)
                    //找出y最小的极限点,zuobiao为一个包含int x和int y字段的类
                        p = i;
                }
                myar.Add((zuobiao)thear[p]);
                //将这个点最先存储进myar中,thear为从文件中读取的点数据的Arraylist
                foreach (zuobiao zb in thear)
                {
                    myar.Add(zb);//将其他数据加入myar中
                }
                canshu.p0x = ((zuobiao)thear[p]).x;//记录极限点的数据,canshu为记录参数的公共变量
                canshu.p0y = ((zuobiao)thear[p]).y;
                myar.RemoveAt(p + 1);//将极限点被重复存储的删去
                CoinSort coinsort = new CoinSort();//对点按顺时针方向排序
                myar.Sort(coinsort);
                int hou, zhong, qian;//hou,zhong,qian代表硬币“后”,“中”,“前”
                hou = 0;
                zhong = 1;
                qian = 2;
                while (qian < myar.Count)//“前”达到最末则停止
                {
                    if (isright(myar[hou], myar[zhong], myar[qian]))
                    //判断是否在“前”是否与“后”“中”形成右拐
                    {
                        hou++;//形成则全部向前移动
                        zhong++;
                        qian++;
                    }
                    else
                    {
                        myar.RemoveAt(zhong);
       //否则删除“中”,因为队列中少了一项,因此原先“前”所表示的次序成为现在“前”的下一个,需要减回来
                       zhong--;//“后”“中”向后退
                        qian--;
                        hou--;
                    }
                }
                zuobiao temp = new zuobiao();
                zuobiao temp2 = new zuobiao();
                temp.x = canshu.p0x;
                temp.y = canshu.p0y;
                myar.Add(temp);
                temp2.x = ((zuobiao)myar[0]).x;
                temp2.y = ((zuobiao)myar[0]).y;
                myar.Add(temp2);//将极限点和最终点写在myar最后使绘图时构成闭合图形
           }
    

    为了判断能否形成“右拐”,既“前”点是否在由“中”“后”两点形成的向量的右侧。
    我提供的方法如下:
    private bool isright(object a, object b, object c)//判断点是否在右侧
            {
                if (((((zuobiao)b).x - ((zuobiao)a).x) * (((zuobiao)c).y - ((zuobiao)a).y) - (((zuobiao)c).x - ((zuobiao)a).x) * (((zuobiao)b).y - ((zuobiao)a).y)) < 0)
                    return true;
                else
                    return false;
            }
    


    2.串行算法

            串行算法的描述是:找出集中点x坐标值的最小值和最大值的两个极限点pmin和pmax,显然此二值极点位于土包边界上。用直线连接pmin和pmax,则点集中的点部分位于上方部分位于下方,显然点集的最小凸包右这两部分组成,既从pmin到pmax的上下凸壳。将两者相加就是点集的最小凸包。
            以计算上凸壳为例,下凸包算法相同。只考虑直线以上的点。上凸壳必然包含距离直线最远的居于直线上方的点,如果所有点都不在直线上方,则上凸壳由pmin和pmax直接确定。设位于直线上距离直线距离最大的点为pm,则类似的用直线连接pmin和pm以及pm和pmax,再次进行寻找线上距离最远点,若pmin到pm和pm到pmax都找不到,则凸壳由pmin,pm,pmax直接确定,否则,再重复以上步骤进行划分,直到所有直线上都不在有点,上凸壳就可以由这些点唯一确定。

    上凸包算法如下:

     private void serialup(int a, int b)//计算上凸包
            {
                double maxdistence = -1;//初始化点到直线的最小距离为-1
                int maxnum = 0;//到直线距离最大点的编号
                int upnumber = 0;//在直线上的点数
                for (int i = 1; i < b - a; i++)
                {
                    if (!(((zuobiao)myar[a + i]).y < ((zuobiao)myar[a]).y && ((zuobiao)myar[a + i]).y < ((zuobiao)myar[b]).y) && !isright(myar[a], myar[b], myar[a + i]))
                        //若点不在起终点下方并且在直线上方
                    {
                        upnumber++;//计数器+1
                        double k = 1.0 * (((zuobiao)myar[b]).y - ((zuobiao)myar[a]).y) / (((zuobiao)myar[b]).x - ((zuobiao)myar[a]).x);//计算斜率
                        double nowdis = System.Math.Abs((((zuobiao)myar[a + i]).x) * k - ((zuobiao)myar[a + i]).y + ((zuobiao)myar[a]).y - k * ((zuobiao)myar[a]).x) / Math.Sqrt(k * k + 1);
                        //计算点到直线距离距离
                        if (nowdis > maxdistence)//记录最大距离和最远点编号
                        {
                            maxdistence = nowdis;
                            maxnum = a + i;
                        }
                    }
                }
                if (upnumber > 1)//直线上不止一个点,则分割
                {
                    serialup(a, maxnum);
                    serialup(maxnum, b);
                }
                else if (upnumber == 1)//若直线上只有一个点,直接存储该点和终点
                {
                    newar.Add((zuobiao)myar[maxnum]);
                    newar.Add((zuobiao)myar[b]);
                    return;
                }
                else//若直线上没有点,则直接存储终点
                {
                    newar.Add((zuobiao)myar[b]);
                    return;
                }
            }

     private void serialdown(int a, int b)//下凸包计算类似上凸包
            {
                double maxdistence = -1;
                int maxnum = 0;
                int upnumber = 0;
                for (int i = 1; i < b - a; i++)
                {
                    if (!(((zuobiao)myar[a + i]).y > ((zuobiao)myar[a]).y && ((zuobiao)myar[a + i]).y > ((zuobiao)myar[b]).y) && isright(myar[a], myar[b], myar[a + i]))
                    {
                        double k = 1.0 * (((zuobiao)myar[b]).y - ((zuobiao)myar[a]).y) / (((zuobiao)myar[b]).x - ((zuobiao)myar[a]).x);
                        double nowdis = System.Math.Abs((((zuobiao)myar[a + i]).x) * k - ((zuobiao)myar[a + i]).y + ((zuobiao)myar[a]).y - k * ((zuobiao)myar[a]).x) / Math.Sqrt(k * k + 1);
                        upnumber++;
                        if (nowdis > maxdistence)
                        {
                            maxdistence = nowdis;
                            maxnum = a + i;
                        }
                    }
                }
                if (upnumber > 1)
                {
                    serialdown(maxnum, b);//存点顺序同上凸包相反
                    serialdown(a, maxnum);
                }
                else if (upnumber == 1)
                {
                    newar.Add((zuobiao)myar[b]);
                    newar.Add((zuobiao)myar[maxnum]);
                    return;
                }
                else
                {
                    newar.Add((zuobiao)myar[b]);
                    return;
                }
            }


    完整代码下载:http://pan.baidu.com/s/1i3kmjZn

    展开全文
  • 点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线...实验证明,串行算法是一个稳定的最优算法。
  • AdaBoost基本原理与算法描述

    万次阅读 多人点赞 2018-08-21 19:59:33
    最近在看集成学习方法,前面已经对XGBoost的原理与简单实践做了介绍,这次对AdaBoost算法做个学习笔记,来巩固自己所学的知识,同时也希望对需要帮助的人有所帮助。 关于集成学习主要有两大分支,一种是bagging方法...

    一. 前言

    最近在看集成学习方法,前面已经对XGBoost的原理简单实践做了介绍,这次对AdaBoost算法做个学习笔记,来巩固自己所学的知识,同时也希望对需要帮助的人有所帮助。

    关于集成学习主要有两大分支,一种是bagging方法,一种是boosting方法。

    bagging方法的弱学习器之间没有依赖关系,各个学习器可以并行生成,最终通过某种策略进行集成得到强学习器(比如回归问题用所有弱学习器输出值的平均值作为预测值;分类问题使用投票法,即少数服从多数的方法来得到最终的预测值;也可以使用学习法,即每个弱学习器的输出值作为训练数据来重新学习一个学习器,而该学习器的输出值作为最终的预测值,代表方法有stacking方法,感兴趣的同学可以自己去了解一下)。bagging方法采用自助采样法,即在总样本中随机的选取m个样本点作为样本m1,然后放回,继续随机选取m个样本点作为样本m2,如此循环下去直到选取的样本个数达到预设定值n,对这n个样本进行学习,生成n个弱学习器。随机森林算法就是bagging方法的代表算法。

    boosting方法的若学习器之间有强的依赖关系,各个弱学习器之间串行生成。它的工作机制是初始给每个样本赋予一个权重值(初始权重值一般是1/m,m表示有m个样本),然后训练第一个弱学习器,根据该弱学习器的学习误差率来更新权重值,使得该学习器中的误差率高的训练样本点(所有的训练样本点)的权重值变高,权重值高的训练样本点在后面的弱学习器中会得到更多的重视,以此方法来依次学习各个弱学习器,直到弱学习器的数量达到预先指定的值为止,最后通过某种策略将这些弱学习器进行整合,得到最终的强学习器。boosting方法的代表算法有AdaBoost和boosting tree算法,而AdaBoost算法就是本文接下来要介绍的算法。

    在介绍AdaBoost之前,要先搞清楚boosting系列算法主要解决的一些问题,如下:

    • 弱学习器的权重系数\alpha如何计算?
    • 样本点的权重系数w如何更新?
    • 学习的误差率e如何计算?
    • 最后使用的结合策略是什么?

    下面我们就来看看AdaBoost是如何解决以上问题的。

    二. AdaBoost基本原理介绍

    2.1 AdaBoost分类问题

    以二分类为例,假设给定一个二类分类的训练数据集\chi = \left \{ (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n})\right \},其中x_{i}表示样本点,y_{i}表示样本对应的类别,其可取值为{-1,1}。AdaBoost算法利用如下的算法,从训练数据中串行的学习一系列的弱学习器,并将这些弱学习器线性组合为一个强学习器。AdaBoost算法描述如下:

    输入:训练数据集\chi = \left \{ (x_{1}, y_{1}), (x_{2}, y_{2}),...,(x_{n}, y_{n})\right \}

    输出:最终的强分类器G(x)

    (1) 初始化训练数据的权重分布值:(D_{m} 表示第m个弱学习器的样本点的权值)

                   D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2) 对M个弱学习器,m=1,2,...,M:

    (a)使用具有权值分布D{_{m}}的训练数据集进行学习,得到基本分类器 G{_{m}}(x) ,其输出值为{-1,1};

    (b)计算弱分类器G{_{m}}(x)在训练数据集上的分类误差率e{_{m}},其值越小的基分类器在最终分类器中的作用越大。

                            

                            其中,I(G{_{m}}(x{_{i}})\neq y{_{i}})取值为0或1,取0表示分类正确,取1表示分类错误。

    (c)计算弱分类器G{_{m}}(x)的权重系数\alpha {_{m}}:(这里的对数是自然对数)

                   \alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}

    一般情况下e{_{m}}的取值应该小于0.5,因为若不进行学习随机分类的话,由于是二分类错误率等于0.5,当进行学习的时候,错误率应该略低于0.5。当e{_{m}}减小的时候\alpha {_{m}}的值增大,而我们希望得到的是分类误差率越小的弱分类器的权值越大,对最终的预测产生的影响也就越大,所以将弱分类器的权值设为该方程式从直观上来说是合理地,具体的证明\alpha {_{m}}为上式请继续往下读。

    (d)更新训练数据集的样本权值分布:

                            

    对于二分类,弱分类器G{_{m}}(x)的输出值取值为{-1,1},y{_{i}}的取值为{-1,1},所以对于正确的分类 y{_{i}}G{_{m}}(x)>0,对于错误的分类y{_{i}}G{_{m}}(x)<0,由于样本权重值在[0,1]之间,当分类正确时w{_{m+1,i}}取值较小,而分类错误时w{_{m+1,i}}取值较大,而我们希望得到的是权重值高的训练样本点在后面的弱学习器中会得到更多的重视,所以该上式从直观上感觉也是合理地,具体怎样合理,请往下读。

                      其中,Z{_{m}}是规范化因子,主要作用是将W{_{mi}}的值规范到0-1之间,使得\sum_{i=1}^{N}{W{_{mi}}} = 1

                           

    (3) 上面我们介绍了弱学习器的权重系数α如何计算,样本的权重系数W如何更新,学习的误差率e如何计算,接下来是最后一个问题,各个弱学习器采用何种结合策略了,AdaBoost对于分类问题的结合策略是加权平均法。如下,利用加权平均法构建基本分类器的线性组合:

                   f(x)=\sum_{m=1}^{M}{\alpha {_{m}}G{_{m}}(x)}

         得到最终的分类器:

                  G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha {_{m}}G{_{m}}(x))

    以上就是对于AdaBoost分类问题的介绍,接下来是对AdaBoost的回归问题的介绍。

    2.2 AdaBoost回归问题

    AdaBoost回归问题有许多变种,这里我们以AdaBoost R2算法为准。

    (1)我们先看看回归问题的误差率问题,对于第m个弱学习器,计算他在训练集上的最大误差:

                           E{_{m}}=max|y{_{i}}-G{_{m}}(x{_{i}})|    i=1,2,...,N

    然后计算每个样本的相对误差:(计算相对误差的目的是将误差规范化到[0,1]之间)

                          e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}  ,  显然 0\leq e{_{mi}}\leq 1

    这里是误差损失为线性时的情况,如果我们用平方误差,则e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}^2}^2,如果我们用指数误差,则e{_{mi}}=1-exp(\frac{-y{_{i}}+G{_{m}}(x{_{i}})}{E{_{m}}})

    最终得到第k个弱学习器的误差率为:

                        e{_{m}}=\sum_{i=1}^{N}{w{_{mi}}e{_{mi}}},表示每个样本点的加权误差的总和即为该弱学习器的误差。

    (2)我们再来看看弱学习器的权重系数α,如下公式:

                       \alpha {_{m}}=\frac{e{_{m}}}{1-e{_{m}}}

    (3)对于如何更新回归问题的样本权重,第k+1个弱学习器的样本权重系数为:

                      w{_{m+i,i}}=\frac{w{_{mi}}}{Z{_{m}}}\alpha {_{m}}^{1-e{_{mi}}}

    其中Z{_{k}}是规范化因子:Z{_{m}}=\sum_{i=1}^{N}{w{_{mi}}\alpha {_{m}}^{1-e{_{mi}}}}

    (4)最后是结合策略,和分类问题不同,回归问题的结合策略采用的是对加权弱学习器取中位数的方法,最终的强回归器为:

                      G(x)=\sum_{m=1}^{M}{g(x)ln\frac{1}{\alpha {_{m}}}},其中g(x)是所有\alpha {_{m}}G{_{m}}(x)的中位数(m=1,2,...,M)。

    这就是AdaBoost回归问题的算法介绍,还有一个问题没有解决,就是在分类问题中我们的弱学习器的权重系数\alpha {_{m}}是如何通过计算严格的推导出来的。

    2.3 AdaBoost前向分步算法

    在上两节中,我们介绍了AdaBoost的分类与回归问题,但是在分类问题中还有一个没有解决的就是弱学习器的权重系数\alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}是如何通过公式推导出来的。这里主要用到的就是前向分步算法,接下来我们就介绍该算法。

    从另一个角度讲,AdaBoost算法是模型为加法模型,损失函数为指数函数,学习算法为前向分步算法时的分类问题。其中,加法模型表示我们的最终得到的强分类器是若干个弱分类器加权平均得到的,如下:

            f(x)=\sum_{m=1}^{M}{\alpha {_{m}}G{_{m}}(x)}

    损失函数是指数函数,如下:

           L(y,f(x))=exp(-yf(x))

    学习算法为前向分步算法,下面就来介绍AdaBoost是如何利用前向分布算法进行学习的:

    (1)假设进过m-1轮迭代前向分布算法已经得到f{_{m-1}}(x)

              f{_{m-1}}=f{_{m-2}}(x)+\alpha {_{m-1}}G{_{m-1}}(x)

                        =\alpha {_{1}}G{_{1}}(x)+...+\alpha {_{m-1}}G{_{m-1}}(x)

    在第m轮的迭代得到\alpha {_{m}}G{_{m}}(x)f{_{m}}(x).

              f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x)

    目标是使前向分布算法得到的\alpha {_{m}}G{_{m}}(x)使f{_{m}}(x)在训练数据集T上的指数损失最小,即

             (\alpha {_{m}},G{_{m}}(x))=arg \underset{\alpha ,G}{min}\sum_{i=1}^{N}exp(-y{_{i}}(f{_{m-1}}(x{_{i}})+\alpha G(x{_{i}})))

                                   =arg\underset{\alpha ,G}{min}\sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha G(x{_{i}}))          {\color{Red} (1)}

    上式即为我们利用前向分步学习算法得到的损失函数。其中,\bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))。因为\bar{w}{_{mi}}既不依赖\alpha也不依赖于G,所以在第m轮迭代中与最小化无关。但\bar{w}{_{mi}}依赖于f{_{m-1}}(x),随着每一轮的迭代而发生变化。

    上式达到最小时所取的\alpha ^{_{*}}{_{m}}G ^{_{*}}{_{m}}(x)就是AdaBoost算法所得到的\alpha {_{m}}G{_{m}}(x)

    (2)首先求分类器G ^{_{*}}{_{m}}(x)

    我们知道,对于二分类的分类器G(x)的输出值为-1和1,y{_{i}}\neq G{_{m}}(x{_{i}})表示预测错误,y{_{i}}= G{_{m}}(x{_{i}})表示正确,每个样本点都有一个权重值,所以对于一个弱分类器的输出则为:G{_{m}}(x)=\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(X{_{i}})),我们的目标是使损失最小化,所以我们的具有损失最小化的第m个弱分类器即为:

    G^{_{*}}{_{m}}(x)=arg \underset{G}{min}\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G(x{_{i}}))   其中,\bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x{_{i}}))

    为什么用I(y{_{i}}\neq G(x{_{i}}))表示一个弱分类器的输出呢?因为我们的AdaBoost并没有限制弱学习器的种类,所以它的实际表达式要根据使用的弱学习器类型来定。

    此分类器即为Adaboost算法的基本分类器G{_{m}}(x),因为它是使第m轮加权训练数据分类误差率最小的基本分类器。

    (3)然后就是来求\alpha ^{_{*}}{_{m}}

    G ^{_{*}}{_{m}}(x)代入损失函数(1)式中,得:

          \alpha {_{m}}=\sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))

    我们的目标是最小化上式,求出对应的\alpha ^{_{*}}{_{m}}

                  \sum_{i=1}^{N}\bar{w}{_{mi}}exp(-y{_{i}}\alpha{_{m}} G^{_{*}}{_{m}}(x{_{i}}))

             =\sum_{y{_{i}}=G{_{m}}(x{_{i}})}\bar{w{_{mi}}}e^{_{-\alpha }}+\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w{_{mi}}}e^{_{\alpha }}

            =e^{_{-\alpha }}\sum_{y{_{i}}=G{_{m}}(x{_{i}})}\bar{w}{_{mi}}+e^{_{\alpha }}\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}

            =e^{_{-\alpha }}(\sum_{i=1}^{N}\bar{w}{_{mi}}-\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}})+e^{_{\alpha }}\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}

            =(e^{_{\alpha }}-e^{_{-\alpha }})\sum_{y{_{i}}\neq G{_{m}}(x{_{i}})}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

            =(e^{_{\alpha }}-e^{_{-\alpha }})\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}        {\color{Red} (2)}

    由于,e{_{m}}=\frac{\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))}{\sum_{i=1}^{N}\bar{w}{_{mi}}}

    注意:这里我们的样本点权重系数\bar{w}{_{mi}}并没有进行规范化,所以\sum_{i=1}^{m}\bar{w}{_{mi}}\neq 1

    (2)式为:   (e^{_{\alpha }}-e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

    则我们的目标是求:

             \alpha {_{m}}=arg\underset{\alpha }{min}(e^{_{\alpha }}-e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}+e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}

    上式求\alpha偏导,并令偏导等于0,得:

           (e^{_{\alpha }}+e^{_{-\alpha }})e{_{m}}\sum_{i=1}^{N}\bar{w}{_{mi}}-e^{_{-\alpha }}\sum_{i=1}^{N}\bar{w}{_{mi}}=0,进而得到:

           (e^{_{\alpha }}+e^{_{-\alpha }})e{_{m}}-e^{_{-\alpha }}=0,求得:\alpha ^{_{*}}{_{m}}=\frac{1}{2}ln\frac{1-e{_{m}}}{e{_{m}}},其中e{_{m}}为误差率:

           e{_{m}}=\frac{\sum_{i=1}^{N}\bar{w}{_{mi}}I(y{_{i}}\neq G{_{m}}(x{_{i}}))}{\sum_{i=1}^{N}\bar{w}{_{mi}}}=\sum_{i=1}^{N}w{_{mi}}I(y{_{i}}\neq G(x{_{i}}))

    (4)最后看样本权重的更新。

    利用前面所讲的f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x),以及权值 \bar{w}{_{mi}}=exp(-y{_{i}}f{_{m-1}}(x))

    可以得到如下式子:

           \bar{w}{_{m+1,i}}=\bar{w}{_{mi}}exp(-y{_{i}}\alpha {_{m}}G{_{m}}(x{_{i}}))

    这样就得到了我们前面所讲的样本权重更新公式。

    2.4 AdoBoost算法的正则化

    为了防止过拟合,AdaBoost算法中也会加入正则化项,这个正则化项我们称之为步长也就是学习率。定义为v,对于前面的弱学习器的迭代有:

                     f{_{m}}(x)=f{_{m-1}}(x)+\alpha {_{m}}G{_{m}}(x)

    加入正则化项,就变成如下:

                    f{_{m}}(x)=f{_{m-1}}(x)+v\alpha {_{m}}G{_{m}}(x)

    v的取值范围为(0,1]。对于同样的训练集学习效果,较小的v意味着我们需要更多的弱学习器的迭代次数。通常我们用学习率和迭代最大次数一起来决定算法的拟合效果。

    到这里,我们的AdaBoost算法介绍完毕。

    三. AdaBoost算法流程描述

    3.1 AdaBoost分类问题的算法流程描述

    关于AdaBoost的分类问题,sklearn中采用的是SAMME和SAMME.R算法,SAMME.R算法是SAMME算法的变种。sklearn中默认采用SAMME.R,原因是SAMME.R算法比SAMME算法收敛速度更快,用更少的提升迭代次数实现了更低的测试误差。接下来我们先介绍AdaBoost的分类算法流程,可以将二元分类算法视为多元分类算法的一个特例。

    3.1.1 SAMME算法流程描述:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

           (a)使用带有权重的样本来训练一个弱学习器G{_{m}}(x);

           (b)计算弱分类器G{_{m}}(x)的分类误差率:

                        

           (c)计算弱分类器的系数:

                          \alpha {_{m}}=\frac{1}{2}ln{\frac{1-e{_{m}}}{e{_{m}}}}+ln(K-1)

             其中,K表示K元分类,可以看出当K=2时,ln(K-1)=0,余下的\alpha {_{m}}与我们二元分类算法所描述的弱分类器系数一致。

           (d)更新样本的权重分布:

                     

    (3)构建最终的强分类器:

                         G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha {_{m}}G{_{m}}(x))

    3.1.2 SAMME.R算法流程描述:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

           (a)使用带有权重的样本来训练一个弱学习器G{_{m}}(x);

           (b)获得带有权重分类的概率评估:

                      P{_{mk}}(x{_{i}})=Prob{_{w}}(c=k|x{_{i}})

                   其中P{_{mk}}(x{_{i}})表示第m个弱学习器将样本x{_{i}}分为第k类的概率。k=1,2,...,K,K表示分类的类别个数。

           (c) 使用加权概率推导出加法模型的更新,然后将其应用于数据:

                       h{_{mk}}(x)=(K-1)(logP{_{mk}}(x)-\frac{1}{K}\sum_{\bar{k}=1}^{K}logP{_{m\bar{k}}}(x))k=1,2,...,K

           (d)更新样本点权重系数:

                      w{_{m+1,i}}=w{_{mi}}exp(-\frac{K-1}{K}y{_{i}}logP{_{m}}(x{_{i}}))

           (e)标准化样本点权重w;

    (3)构建最终的强分类器:

                       G(x)=sign(arg\underset{K}{max}\sum_{m=1}^{M}h{_{mk}}(x)),表示使\sum_{m=1}^{M}h{_{mk}}(x))最大的类别即为我们所预测的类别。

    3.2 AdaBoost回归问题的算法流程描述

    在sklearn中,回归使用的算法为 AdaBoost.R2算法,具体的流程描述如下:

    输入:样本集T=\left \{ (x{_{1}},y{_{1}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},输出为\left \{ -1,1 \right \},弱分类器的迭代次数为M,样本点的个数为N。

    输出:最终的强分类器G(x)

    (1)初始化样本点的权重为:

                       D_{1}=(w_{11},...,w_{1i},...,w_{1N}),       w_{1i}=1/N,     i=1,2,...,N

    (2)对于m=1,2,..,M

    (a)使用具有权重D{_{m}}的样本集来训练数据,得到弱学习器G{_{m}}(x)

    (b)计算训练集上的最大误差

                 E{_{k}}=max|y{_{i}}-G{_{m}}(x{_{i}})|i=1,2,...,N

    (c)计算每个样本点的相对误差:

             如果是线性误差:则e{_{mi}}=\frac{|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}}

             如果是平方误差,则e{_{mi}}=\frac{(y{_{i}}-G{_{m}}(x{_{i}}))^2}{E{_{m}}^2}

             如果是指数误差,则e{_{mi}}=1-exp(\frac{-|y{_{i}}-G{_{m}}(x{_{i}})|}{E{_{m}}})

    (d)计算回归误差率:

            e{_{m}}=\sum_{i=1}^{N}w{_{mi}}e{_{mi}}

    (c)计算弱学习器的系数:

            \alpha {_{m}}=\frac{e{_{m}}}{1-e{_{m}}}

    (d)更新样本集的权重分布:

            w{_{m+1,i}}=\frac{w{_{mi}}}{Z{_{m}}}\alpha {_{m}}^{1-e{_{mi}}},其中Z{_{m}}是规范化因子,Z{_{m}}=\sum_{i=1}^{N}w{_{mi}}\alpha {_{m}}^{1-e{_{mi}}}

    (3)构建最终的强学习器:

                       G(x)=\sum_{m=1}^{M}{g(x)ln\frac{1}{\alpha {_{m}}}},其中g(x)是所有\alpha {_{m}}G{_{m}}(x)的中位数(m=1,2,...,M)。

    四. AdaBoost算法的优缺点

    4.1 优点

    (1)不容易发生过拟合;

    (2)由于AdaBoost并没有限制弱学习器的种类,所以可以使用不同的学习算法来构建弱分类器;

    (3)AdaBoost具有很高的精度;

    (4)相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重;

    (5)AdaBoost的参数少,实际应用中不需要调节太多的参数。

    4.2 缺点

    (1)AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定。

    (2)数据不平衡导致分类精度下降。

    (3)训练比较耗时,每次重新选择当前分类器最好切分点。

    (4)对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

    五. 参考文献/博文

    (1)李航,《统计学习方法》 第八章

    (2)Multi-class AdaBoost 论文

    (3)Boosting for Regression Transfer AdaBoost回归论文

    (4)https://www.cnblogs.com/pinard/p/6133937.html

    展开全文
  • 关于CRC校验码的详尽分析和描述,对串行和并行的原理进行了阐述,然后利用Quartus软件绘制出电路原理图,有设计的总结以及详细的仿真过程。
  • 点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线的正负...实验证明,串行算法是一个稳定的最优算法。
  •   本次实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算,实验采用同一个样本,即矩阵大小为512个元素,元素值为由时间生成的随机数,每个算法对此样本运行十次,并记录每次运行...

    1 问题描述

      本次实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算,实验采用同一个样本,即矩阵大小为512个元素,元素值为由时间生成的随机数,每个算法对此样本运行十次,并记录每次运行时间和十次运算的平均运行时间。实验环境:计算机apple macbook pro2015、系统macOS High Sierra10.13.5、编辑器vscode&C/C++ Extension、gcc编译。

    2 算法设计与实现

      首先在矩阵样本设计方面,考虑大越大规模的数据越能体现不同算法在运行上的差距,因而将矩阵大小设置为512个元素,并且为了减少元素数据对实验的影响,采取了随机数赋值的方法。

     srand((unsigned)time(NULL));
     float a[maxN][maxN];
     float b[maxN][maxN];
     for(int i = 0; i < n; i++)
     {
       for(int j=0; j < n; j++){
         a[i][j] = rand();
         b[i][j] = rand();
       }
     }
    

    ​ 其次考虑每个算法的具体实现:

    2.1 串行算法

    ​ 由于矩阵乘法规则为乘积AB的第i个分量等于矩阵A的第i个行向量与列向量B的对应分量乘积之和,因而对矩阵A的每一行的元素,矩阵B的每一列的元素都要与之相乘并相加,所以需要先遍历矩阵A一行中的元素的同时遍历矩阵B一列中的元素,再遍历矩阵B中的每一列,再遍历矩阵A中的每一行,三层遍历嵌套,时间复杂度O(n) = n^3,用clock_t记录时间。

    ​ 具体代码如下:

    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]){ //串行算法 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                c[i][j]= 0.0;
                for(int k = 0; k < n; k++){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
    
        end = clock();
        time = (double)(end-start);
        cout<<"串行算法耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    2.2 Cache优化

    ​ 由于寄存器从内存中取值时,需要从内存中寻址,上述串行算法b[k][j]需要先对矩阵B的行进行遍历,又因为在c++中,二维数组相邻的元素地址相近,因而先对行进行遍历造成了地址跳跃,需要更长的寻址时间。将矩阵B转置,就能够实现对连续的地址进行读写操作,节省大量寻址时间。算法时间复杂度O(n) = n^3。

    ​ 具体代码如下:

    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ // Cache优化 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < n; ++j) { 
                c[i][j] = 0.0;
                for (int k = 0; k < n; ++k) { 
                    c[i][j] += a[i][k] * b[j][k];
                    }
                }
        } // transposition
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"Cache优化耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    2.3 SSE版本

    ​ 基于SIMD编程,将多个元素同时进行寄存器加载和存储器存值等操作能够提高并行效率。使用SSE指令能够实现该功能。时间复杂度为O(n) = (n^3)/4,同样对矩阵B进行转置。

    ​ 具体代码如下:

    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //SSE版本 O(n) = (n^3)/4
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;  //__m128 == float
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i){ 
            for (int j = 0; j < n; ++j){ 
                c[i][j] = 0.0;
                sum = _mm_setzero_ps();  //Initialize
                for (int k = n - 4; k >= 0; k -= 4){ // sum every 4 elements 
                    t1 = _mm_loadu_ps(a[i] + k); 
                    t2 = _mm_loadu_ps(b[j] + k); 
                    t1 = _mm_mul_ps(t1, t2);
                    sum = _mm_add_ps(sum, t1);
                }
                sum = _mm_hadd_ps(sum, sum); 
                sum = _mm_hadd_ps(sum, sum); 
                _mm_store_ss(c[i] + j, sum);
                for (int k = (n % 4) - 1; k >= 0; --k){ // handle the last n%4elements
                    c[i][j] += a[i][k] * b[j][k];
                }
            }
        } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"SSE版本耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    

    ​ 其中_mm_loadu_ps为同时加载四个单精度浮点数值的指令,因而循环每次跳跃四个元素,再将四个元素的乘积相加。对于矩阵n不能被4整除的情况,对剩余元素做类似Cache优化算法的操作。

    2.4 分片策略

    ​ 先针对cpu线程数设置分片数,将矩阵分为多个小矩阵,对每个小矩阵进行SSE指令计算。时间复杂度为O(n) = n^3,同样对矩阵B进行转置。

    ​ 具体代码如下:

    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //分片策略  O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;
        float t;
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int r = 0; r < n / T; ++r) 
            for (int q = 0; q < n / T; ++q) { 
                for (int i = 0; i < T; ++i) 
                    for (int j = 0; j < T; ++j) 
                        c[r * T + i][q * T +j] = 0.0;
                for (int p = 0; p < n / T; ++p) { 
                    for (int i = 0; i < T; ++i) 
                        for (int j = 0; j < T; ++j) { 
                            sum = _mm_setzero_ps();
                            for (int k = 0; k < T; k += 4){ //sum every 4th elements
                                t1 = _mm_loadu_ps(a[r * T + i] + p * T + k); 
                                t2 = _mm_loadu_ps(b[q * T + j] + p * T + k);
                                t1 = _mm_mul_ps(t1, t2); 
                                sum = _mm_add_ps(sum, t1);
                            }
                            sum = _mm_hadd_ps(sum, sum); 
                            sum = _mm_hadd_ps(sum, sum); 
                            _mm_store_ss(&t, sum);
                            c[r * T + i][q * T + j] += t;
                        }
                }
            } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"分片策略耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    

    3 实验结果及结果分析

    ​ 每个算法的十次运行时间结果如下:

    第1次运行结果:
    串行算法耗时: 0.753588s
    Cache优化耗时: 0.453238s
    SSE版本耗时: 0.230628s
    分片策略耗时: 0.279179s
    
    第2次运行结果:
    串行算法耗时: 0.77117s
    Cache优化耗时: 0.465396s
    SSE版本耗时: 0.239504s
    分片策略耗时: 0.293299s
    
    第3次运行结果:
    串行算法耗时: 0.746869s
    Cache优化耗时: 0.451797s
    SSE版本耗时: 0.228981s
    分片策略耗时: 0.282906s
    
    第4次运行结果:
    串行算法耗时: 0.696163s
    Cache优化耗时: 0.453274s
    SSE版本耗时: 0.233736s
    分片策略耗时: 0.277309s
    
    第5次运行结果:
    串行算法耗时: 0.878417s
    Cache优化耗时: 0.490044s
    SSE版本耗时: 0.271495s
    分片策略耗时: 0.378412s
    
    第6次运行结果:
    串行算法耗时: 1.08664s
    Cache优化耗时: 0.491328s
    SSE版本耗时: 0.243387s
    分片策略耗时: 0.291609s
    
    第7次运行结果:
    串行算法耗时: 0.777393s
    Cache优化耗时: 0.470352s
    SSE版本耗时: 0.233467s
    分片策略耗时: 0.285942s
    
    第8次运行结果:
    串行算法耗时: 0.689719s
    Cache优化耗时: 0.450596s
    SSE版本耗时: 0.224129s
    分片策略耗时: 0.284757s
    
    第9次运行结果:
    串行算法耗时: 0.692528s
    Cache优化耗时: 0.450607s
    SSE版本耗时: 0.229762s
    分片策略耗时: 0.282219s
    
    第10次运行结果:
    串行算法耗时: 0.708097s
    Cache优化耗时: 0.45446s
    SSE版本耗时: 0.223255s
    分片策略耗时: 0.28649s
    
    平均耗时:
    串行算法耗时:0.780058s
    Cache优化耗时:0.463109s
    SSE版本耗时:0.235834s
    分片策略耗时:0.294212s
    

    ​ 图表展示如下:

    算法 1 2 3 4 5
    串行算法(s) 0.75 0.77 0.75 0.69 0.88
    Cache优化(s) 0.45 0.47 0.45 0.45 0.49
    SSE版本(s) 0.23 0.24 0.23 0.23 0.27
    分片策略(s) 0.28 0.29 0.28 0.28 0.38
    算法 6 7 8 9 10
    串行算法(s) 1.09 0.77 0.69 0.69 0.71
    Cache优化(s) 0.49 0.47 0.45 0.45 0.45
    SSE版本(s) 0.24 0.23 0.22 0.23 0.22
    分片策略(s) 0.29 0.29 0.28 0.28 0.29

    在这里插入图片描述

    ​ 从图中可以明显看出,耗时最多的算法时串行算法,也是最原始的算法,Cache优化对串行算法有很明显的优化效果,时间减短大约40% ,但用时仍比SSE编程要长,SSE版本算法运行时间最短,采用分片策略后时间反而有点增长。

    ​ 由于串行算法没做任何优化,因而运行时间最长。Cache优化算法对串行算法的取址时间进行了压缩。而想要更短的运行时间就需要用到SIMD编程。分片策略比SSE版本用时较长的原因大概是分片数量不理想,并行成本消耗过高。

    4 源码

    ​ 本次实验代码如下:

    #include<iostream>
    #include<stdlib.h>
    #include <pmmintrin.h>
    #include <stdio.h>
    #include <algorithm>
    #include<cmath>
    
    using namespace std;
    
    const int maxN = 512;
    const int T = 64; // tile size
    
    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]);
    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]);
    
    int main(){
        int n = 512;
        srand((unsigned)time(NULL));
        float a[maxN][maxN];
        float b[maxN][maxN];
        float c[maxN][maxN];
        double mul_sum = 0;
        double trans_mul_sum = 0;
        double sse_mul_sum = 0;
        double sse_tile_sum = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j=0; j < n; j++){
                a[i][j] = rand();
                b[i][j] = rand();
            }
        }
        for(int i=0;i<10;i++){
            cout<<"第"<<i+1<<"次运行结果:"<<endl;
            mul_sum += mul(n,a,b,c);
            trans_mul_sum += trans_mul(n,a,b,c);
            sse_mul_sum += sse_mul(n,a,b,c);
            sse_tile_sum += sse_tile(n,a,b,c);
            cout<<endl;
        }
        cout<<"平均耗时:"<<endl;
        cout<<"串行算法耗时:"<<mul_sum/10<<"s"<<endl;
        cout<<"Cache优化耗时:"<<trans_mul_sum/10<<"s"<<endl;
        cout<<"SSE版本耗时:"<<sse_mul_sum/10<<"s"<<endl;
        cout<<"分片策略耗时:"<<sse_tile_sum/10<<"s"<<endl;
    }
    
    double mul(int n,float a[][maxN],float b[][maxN],float c[][maxN]){ //串行算法 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                c[i][j]= 0.0;
                for(int k = 0; k < n; k++){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
    
        end = clock();
        time = (double)(end-start);
        cout<<"串行算法耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double trans_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ // Cache优化 O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < n; ++j) { 
                c[i][j] = 0.0;
                for (int k = 0; k < n; ++k) { 
                    c[i][j] += a[i][k] * b[j][k];
                    }
                }
        } // transposition
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"Cache优化耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //SSE版本 O(n) = (n^3)/4
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;  //__m128 == float
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int i = 0; i < n; ++i){ 
            for (int j = 0; j < n; ++j){ 
                c[i][j] = 0.0;
                sum = _mm_setzero_ps();  //Initialize
                for (int k = n - 4; k >= 0; k -= 4){ // sum every 4 elements 
                    t1 = _mm_loadu_ps(a[i] + k); 
                    t2 = _mm_loadu_ps(b[j] + k); 
                    t1 = _mm_mul_ps(t1, t2);
                    sum = _mm_add_ps(sum, t1);
                }
                sum = _mm_hadd_ps(sum, sum); 
                sum = _mm_hadd_ps(sum, sum); 
                _mm_store_ss(c[i] + j, sum);
                for (int k = (n % 4) - 1; k >= 0; --k){ // handle the last n%4elements
                    c[i][j] += a[i][k] * b[j][k];
                }
            }
        } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"SSE版本耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    double sse_tile(int n, float a[][maxN], float b[][maxN], float c[][maxN]){ //分片策略  O(n) = n^3
        double time;
        clock_t start,end;
        start = clock();
    
        __m128 t1, t2, sum;
        float t;
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]); 
        for (int r = 0; r < n / T; ++r) 
            for (int q = 0; q < n / T; ++q) { 
                for (int i = 0; i < T; ++i) 
                    for (int j = 0; j < T; ++j) 
                        c[r * T + i][q * T +j] = 0.0;
                for (int p = 0; p < n / T; ++p) { 
                    for (int i = 0; i < T; ++i) 
                        for (int j = 0; j < T; ++j) { 
                            sum = _mm_setzero_ps();
                            for (int k = 0; k < T; k += 4){ //sum every 4th elements
                                t1 = _mm_loadu_ps(a[r * T + i] + p * T + k); 
                                t2 = _mm_loadu_ps(b[q * T + j] + p * T + k);
                                t1 = _mm_mul_ps(t1, t2); 
                                sum = _mm_add_ps(sum, t1);
                            }
                            sum = _mm_hadd_ps(sum, sum); 
                            sum = _mm_hadd_ps(sum, sum); 
                            _mm_store_ss(&t, sum);
                            c[r * T + i][q * T + j] += t;
                        }
                }
            } 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < i; ++j) 
                swap(b[i][j], b[j][i]);
    
        end = clock();
        time = (double)(end-start);
        cout<<"分片策略耗时: "<<(time/CLOCKS_PER_SEC)<<"s"<<endl;
        return time/CLOCKS_PER_SEC;
    }
    
    展开全文
  • 贪心算法(文字描述解释)

    千次阅读 2020-02-20 13:13:27
    贪心算法 ​ 贪心算法(又称贪婪算法,greedy algorithm)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解,而不能算是全局最优解...
  • 排序算法c语言描述---希尔排序

    万次阅读 多人点赞 2013-08-10 20:33:01
    排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路分析...
  • 并行算法设计的一般方法

    千次阅读 2012-12-02 22:23:03
    1.串行算法的直接并行化 发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。 由串行算法直接并行化的方法是并行算法设计...从问题本身描述出发,不考虑相应的串行算法,设计一个全新的并行算法 挖掘
  • 串行算法的直接并行 最直接,最易于理解的设计方法,发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。 Case 1:快速排序 ​ 快速排序的串行算法思想为随机选取主元进行划分,之后递归排序。直接...
  • unsigned char cal_table_high_first(unsigned char value) { unsigned char i ; unsigned char checksum = value ; for (i=8;i>0;--i) { if (check_sum & 0x80) { check_sum = (check_sum<... }
  • 个体学习器间存在强依赖关系、必须串行生成的序列化方法 代表是Boosting族算法。 Boosting族中最著名的代表是AdaBoost。 个体学习器间不存在强依赖关系、必须同时生成的并行化化方法 代表是Bagging和随机森林 ...
  • BP神经网络的Matlab实现——人工智能算法

    万次阅读 多人点赞 2018-01-27 23:07:23
    这几天在各大媒体上接触到了人工智能机器学习,觉得很有意思,于是开始入门最简单的机器算法——神经网络训练算法(Neural Network Training);以前一直觉得机器学习很高深,到处是超高等数学、线性代数、数理统计。...
  • 举一个简单的例子来说明SQL Server 中hash join的算法. 例如有两张表, 每张表都有10000行的记录, 假设做join的两个字段都是从1到10000的序数. 如果要做hashjoin, 那么首先对其中的一个表上的列进行hash运算, 将...
  • 分类算法

    千次阅读 2015-07-28 10:35:12
    本文总结了数据挖掘和机器学习过程中分类算法如神经网络算法、随机森林算法以及决策树等,希望能对数据挖掘爱好者有一定帮助。神经网络算法简介逻辑性的思维是指根据逻辑规则进行推理的过程;它先将信息化成概念,...
  • 编程算法

    千次阅读 2018-08-13 09:06:23
    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有...
  • 基于MPI的Warshall算法实现及其优化

    千次阅读 2006-11-30 21:52:00
    基于MPI的Warshall算法实现及其优化1....输入:关系R的关系矩阵输出:关系R的传递闭包矩阵1.1.1 Warshall算法的串行算法分析Warshall算法的串行算法类C描述初始化矩阵;for (i=0;i生成传递闭包矩阵*/ fo
  • 算法

    千次阅读 2013-12-12 16:51:34
    算法 译自From Wikipedia, the free encyclopedia   一种计算在位置名为A和B的两个数字a 和b的最大公约数 (g.c.d.) 的算法(欧几里得的算法)的流程图。  该算法通过在两个循环中连续减进行的:如果测试B≥A产生...
  • 循环冗余校验(CRC)算法入门引导

    万次阅读 多人点赞 2012-08-19 12:42:34
    写给嵌入式程序员的循环冗余校验(CRC)算法入门引导 前言 CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中,经常要用到CRC 算法对各种数据进行校验。因此,掌握基本的CRC算法应是...
  • 并行算法的设计基础

    2019-07-05 22:31:56
    并行算法的定义和分类 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。 并行算法分类 数值计算与非数值计算 ...串行算法的复杂性度量 最坏情况下的复杂度(Worst-C...
  • 凸壳算法

    万次阅读 2015-03-25 09:25:49
    可能我以后用到的比较少,就当是普及算法了,以下简单介绍凸壳串行算法。 关于凸壳的串行算法,可以说有好多种,有时间复杂度O(n^2)的,也有O(nlogn)的,下面依次介绍几种算法: 1、卷包裹法,时间复杂度为...
  • FPGA串行异步通信

    2009-08-28 09:25:41
    FPGA实现串行异步通信 内附有源代码,原理图说明还有一些算法描述
  • 在介绍CRC校验原理和传统CRC32串行比特算法的基础上,由串行比特型算法推导出一种CRC32并行算法。并结合SATAⅡ协议的要求,完成了SATAⅡ主控制器设计中CRC生成与校验模块的设计。最后通过在ISE平台上编写Verilog硬件...
  • 对于串行算法,一般只有一种基础模型(随机存取机器模型),而在并行领域,有许多种不同的并行算法模型和并行化模型,没有一种最佳模型的共识。 本节课讨论的模型基于动态多线程的多核机器,它是为共享内存的编程而...
  • iOS 算法~十大算法基础总结

    千次阅读 2017-06-14 08:22:19
    算法一:快速排序算法: 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明...
  • 计算机排序算法

    千次阅读 2013-08-01 15:13:49
    在计算机科学与数学中,一个排序算法(Sorting algorithm)是一种能将一串数据依照特定排序方式的一种算法。最常用到的排序方式是数值顺序以及字典顺序。...输出结果为递增串行(递增是针对所需的排序顺
  • 计算机常用算法对照表整理

    千次阅读 2017-07-26 10:58:01
    中文名称条件随机场算法,外文名称conditional random field algorithm,是一种数学算法,是2001年提出的,基于遵循马尔可夫性的概率图模型。 全部对照第一部分、计算机算法常用术语中英对照 Data Structures 基本...
  • 【原创】Liu_LongPo 转载请注明出处 【CSDN】http://blog.csdn.net/llp1992AdaBoost算法是基于单层决策树等弱分类算法的强...而AdaBoost算法通过将多个弱分类算法串行训练而成,属于强分类算法。AdaBoost算法是boost

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,948
精华内容 16,379
关键字:

串行算法的描述