STEP BY STEP

发表于 分类于 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

图像处理中的空间滤波主要有2种类型，平滑空间滤波和锐化空间滤波。平滑空间滤波一般用于模糊图像，比如消除散乱的噪声点等。平滑空间滤波主要有均值滤波和中值滤波，以及其余的复杂统计方法。滤波窗口的大小可以选为33或者44或者5*5等。
其实不同的空间滤波处理基本上就滤波窗口的系数不相同，除了均值滤波要除以滤波窗口大小以及中值滤波要特殊处理之外，那么我们可以实现一个针对特定滤波窗口实现的滤波公共函数。比如，均值滤波窗口

{1,1,1}

{1,1,1},

{1,1,1}

就是选取当前像素点周围9个点的像素值总和再除以9得到的。而中值滤波则必须得到这9个值中排行第5的值作为当前像素的值。平滑滤波的原理也比较简单。下面给出相关的代码。

滤波基础函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//传入滤波窗口系数和尺寸(nSize*nSize)
void CxBitmap::Filter(double* pfFactors, int nSize, BOOL bAve)
{
    double fMedian = 0;
    int nRead = 0;
    int nRadius = nSize / 2;//滤波窗口的半径
    int nBytePerPixel = bitmapinfoheader.biBitCount / 8;
    int i, j, k, m, n;

    //拷贝边界到临时缓存区
    for (i = 0; i < nRadius; ++i)
    {
        memcpy(pbyTmpBuffer + i * m_nBytesPerLine, pbyBuffer + i * m_nBytesPerLine,
                m_nBytesPerLine);
        memcpy(pbyTmpBuffer + (bitmapinfoheader.biHeight - 1 - i) * m_nBytesPerLine,
                pbyBuffer + (bitmapinfoheader.biHeight - 1 - i) * m_nBytesPerLine,
                m_nBytesPerLine);
    }

    for (i = 0; i < bitmapinfoheader.biHeight; ++i)
    {
        nRead = i * m_nBytesPerLine;
        for (j = 0; j < nRadius; ++j)
        {
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
        }

        nRead = i * m_nBytesPerLine + nBytePerPixel * (bitmapinfoheader.biWidth - nRadius);
        for (j = 0; j < nRadius; ++j)
        {
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
            pbyTmpBuffer[nRead] = pbyBuffer[nRead++];
        }
    }

    for (i = nRadius; i < bitmapinfoheader.biHeight - nRadius; ++i)
    {
        nRead = i * m_nBytesPerLine + nRadius * nBytePerPixel;
        for (j = nRadius; j < bitmapinfoheader.biWidth - nRadius; ++j)
        {
            for (k = 0; k < m_nBytesPerPixel; ++k)
            {
                fMedian = 0;
                for (m = 0; m < nSize; ++m)
                {
                    for (n = 0; n < nSize; ++n)
                    {
                        fMedian += *(pfFactors + nSize * m + n) * pbyBuffer[nRead                            + (m - nRadius) * m_nBytesPerLine + (n - nRadius) * nBytePerPixel];
                    }
                }
                if (bAve)
                {
                    fMedian /= nSize * nSize;
                }
                //assert(nMedian >= 0);
                //注意必须处理变换后不在0-255范围内的像素
                if (fMedian < 0)
                {
                    fMedian = 0;
                }
                if (fMedian > 255)
                {
                    fMedian = 255;
                }
                pbyTmpBuffer[nRead++] = fMedian;
            }
        }
    }

    m_bBinary = FALSE;//滤波处理之后肯定不是二值图像了
    memcpy(pbyBuffer, pbyTmpBuffer, bitmapinfoheader.biSizeImage);
}

均值滤波函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//8邻域滤波均值滤波
void CxBitmap::AverageFilter()
{
    const int AVE_NEIGHBOUR_SIZE = 3;
    static double s_fAveFactors[AVE_NEIGHBOUR_SIZE][AVE_NEIGHBOUR_SIZE] =
    {
        {1, 1, 1},
        {1, 1, 1},
        {1, 1, 1},
    };
    assert(m_bLoad);
    if (m_bLoad)
    {
        Filter(s_fAveFactors[0], AVE_NEIGHBOUR_SIZE, TRUE);
    }
}

发表于 分类于 阅读次数： Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

hough变换是图像处理里面一种检测直线等规则曲线的方法。这里介绍下检测直线的原理和实现方法，最后给出相关的代码。

先给出数学上面的里面，斜截式直线y=kx+b有两个参数k,b，注意直线方程是在笛卡儿坐标系xoy中的。任意一条直线对应于kob平面中一个点(k,b)。那么，对于xoy平面中的任意一个点肯定有无数条通过它的直线，那么直线都有对应的kob平面中的点，这些点能组成一条直线。综合起来就是，xoy平面中一条直线对应于kob平面中的一个点，xoy平面中的一个点对应于kob平面中的一条直线。
现在有个问题是斜截式无法表示xoy平面中所有直线，那么我们希望能找到能够表示xoy平面中所有直线的参数式子。这个式子是r=xcos(θ)+ysin(θ)。推导过程如下：

r为原点到直线的距离，(x0,y0)为垂足，θ为垂线和x轴正向的夹角，那么对于直线上面的任意的一个点都有
(x0, y0) (x-x0,y-y0)=0,得到x x0 - x0 x0 + y y0 - y0 y0 = 0，即x x0 + y y0 = x0 x0 + y0 y0 = r r。等式两边再除以r得到r = x cos(θ) + y sin(θ)。那么这个关于(θ,r)的参数式子可以表示xoy平面上所有的直线了。

现在再来讨论下如何根据这个参数式子检测直线的。
我们手上的只有xoy平面上的图像。而且根据我们的推理，我们的图像的原点必须在左下角，因为我们是用笛卡尔坐标系推出该参数式子的。那么，我们可以枚举图像上面每一个可能是直线上面的点(比如，我们可以对图像阈值化后，像素值为255的点就可能是直线上面的点），由于图像上的每个点对应于θor平面上面的一条曲线(这里管它是直线还是曲线了，对于检测原理没影响)，那么我们就能得到很多θor平面上的曲线。我们对每个(θ,r)点计数通过其上的曲线个数，最后选取曲线个数最大的那个点（θmax,Rmax）其对应的肯定是我们要检测的直线。至于其它的预处理，一般是梯度滤波增强边缘或者拉普拉斯增强边缘，然后弄个全局二值化，就可以用hough变换检测直线了(我这次的实验就没有平滑滤波噪声，那样会使直线变粗，使检测效果变坏）。
最后我给出我的检测直线的代码，并指出代码需要主要的实现点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//针对hough变换的定义得到的直线相对的是坐标系原点的坐标系
//针对hough变换的定义得到的直线相对的是坐标系原点的坐标系
void CxBitmap::HoughLine(int* pnR, double* pfTheta)
{
    const double PI = 4.0 * atan(1.0);
    double fRate = PI / 180;
    int nWidth = GetWidth(), nHeight = GetHeight();
    int iRMax = (int)sqrt(nWidth * nWidth + nHeight * nHeight) + 1;
    int iThMax = 360;
    int iTh;
    int iR;
    int iMax = -1;
    int iThMaxIndex = -1;
    int iRMaxIndex = -1;
    int *pnArray = NULL;
    int nPos = 0;

    if (m_bBinary == FALSE)
    {
        GrayToBinary();
    }
    pnArray = new int[iRMax * iThMax];//iRMax行,每一行长度是iThMax
    memset(pnArray, 0, sizeof(int) * iRMax * iThMax);

    for (int y = 0; y < nHeight; y++)
    {
        nPos = m_nBytesPerLine * y;
        for (int x = 0; x < nWidth; x++)
        {
            if(pbyBuffer[nPos] == 255)
            {
                for(iTh = 0; iTh < iThMax; iTh++) { iR = (int)(x * cos(iTh * fRate) + y * sin(iTh * fRate)); if(iR > 0)
                    {
                        pnArray[iR * iThMax + iTh]++;
                    }
                }
            }
            nPos++;
        } // x
    } // y

    for(iR = 0; iR < iRMax; iR++)
    {
        for(iTh = 0; iTh < iThMax; iTh++) { int iCount = pnArray[iR * iThMax + iTh]; if(iCount > iMax)
            {
                iMax = iCount;
                iRMaxIndex = iR;
                iThMaxIndex = iTh;
            }
        }
    }

    *pnR = iRMaxIndex;
    *pfTheta = fRate * iThMaxIndex;

    delete [] pnArray;
}

注意nPos 必须按m_nBytesPerLine对齐，因为即使是灰度图像每行的长度也不一定是图像的宽度，如果这个错了，检测结果就完全错了。另外一个是计算出来的iR值必须大于0才有效。
相关博文可以参考这篇关于hough变换的文章，我也说说hough变换

发表于 分类于 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

假如你定义了一个位图类，里面包含位图头，位图信息头，调色板，位图数据。然后你按照位图的格式将位图文件读入你的类中，现在你知道了位图的全部信息了。主要信息包含在位图信息头里面，数据则在位图数据缓冲里面。现在的问题是，在Windows下面如何将一张位图画出来，而且现在是如何从数据缓存里面绘画出位图。
一般情况，我们都是直接绘制在dc里面，而不是绑定到子控件，让子控件自己绘画，比如picture控件之类的，我觉得提供绘制在dc里面的接口更具有广泛性。

现在我知道两种从内存数据绘制彩色位图的2种方法。第一种麻烦一点，第二种则相当直接。
方法一：
第一步，用CreateCompatibleDC创建跟目标dc的兼容性内存dc。
第二步，用CreateCompatibleBitmap创建跟目标dc的兼容性位图。
第三步，用SelectObject将第二步创建的兼容位图选入第一步创建的兼容dc中。
第四步，用SetDIBits设置兼容位图的数据缓冲。
第五步，用BitBlt将数据从兼容内存dc绘制到目标dc。
第六步，删除兼容位图和兼容dc。
代码如下，其中buffer代表位图数据缓冲。

1
2
3
4
5
6
7
8
9
10
11
HDC hCompatibleDC = CreateCompatibleDC(hDc);
HBITMAP hCompatibleBitmap = CreateCompatibleBitmap(hDc, bitmapinfoheader.biWidth,
bitmapinfoheader.biHeight);
HBITMAP hOldBitmap = (HBITMAP)SelectObject(hCompatibleDC, hCompatibleBitmap);
SetDIBits(hDc, hCompatibleBitmap, 0, bitmapinfoheader.biHeight,
buffer, (BITMAPINFO*)&bitmapinfoheader, DIB_RGB_COLORS);
BitBlt(hDc, nStartX, nStartY, bitmapinfoheader.biWidth, bitmapinfoheader.biHeight,
hCompatibleDC, 0, 0, SRCCOPY);
SelectObject(hCompatibleDC, hOldBitmap);
DeleteObject(hCompatibleDC);
DeleteObject(hCompatibleDC);

方法二：直接调用StretchDIBits绘制位图。
该函数功能相当强悍，似乎专为从内存数据绘制位图到dc而生。
函数原型如下：
int StretchDIBits(
HDC hdc, // handle to DC
int XDest, // x-coord of destination upper-left corner
int YDest, // y-coord of destination upper-left corner
int nDestWidth, // width of destination rectangle
int nDestHeight, // height of destination rectangle
int XSrc, // x-coord of source upper-left corner
int YSrc, // y-coord of source upper-left corner
int nSrcWidth, // width of source rectangle
int nSrcHeight, // height of source rectangle
CONST VOID lpBits, // bitmap bits
CONST BITMAPINFO lpBitsInfo, // bitmap data
UINT iUsage, // usage options
DWORD dwRop // raster operation code
);
使用也相当简单，调用

1
2
3
4
StretchDIBits(hDc, nStartX, nStartY, bitmapinfoheader.biWidth,
bitmapinfoheader.biHeight, 0, 0, bitmapinfoheader.biWidth,
bitmapinfoheader.biHeight, buffer, (BITMAPINFO*)&bitmapinfoheader,
DIB_RGB_COLORS, SRCCOPY);

即可了。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 306 阅读时长 ≈ 1 分钟

区别一：引用必须要指代一个对象，所以引用必须初始化，但是指针不需要。

区别二：存在空指针，但是不存在空引用，引用必须要指代某个对象。

区别三：由于不存在空引用，使用引用时候不需要测试是否有效，但是使用指针则需要保证其是有效的。

区别四：指针可以改变其指向的对象，但是引用不可以，引用一被初始化后就不能改变。

区别五：重载[]操作符的时候，由于语法需要，应该返回引用而不是指针。

区别六：从概念上看，指针是一个变量，而引用则是其它变量的别名。

区别七：指针是占据内存的，但是引用则不一定会分配内存，引用只是一个别名。

区别八：对指针使用操作符和对引用使用操作符效果不同，对引用使用操作符得到的都是对所指代的对象使用操作符的结果。

发表于 分类于 阅读次数： Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

该函数原型如下，
BOOL SetWindowPos(
HWND hWnd, // handle to window
HWND hWndInsertAfter, // placement-order handle
int X, // horizontal position
int Y, // vertical position
int cx, // width
int cy, // height
UINT uFlags // window-positioning options
);

第一个参数是你要修改的窗口局部，第二个参数是用于修改Z order的，可以用这个参数把你的窗口弄成TopMost之类的窗口，后面四个参数很好理解，最后那个参数是一些标志，具体的请查看msdn。
基本上我觉得使用这个函数有些时候达不到你想要的效果原因是不知道这个函数使用的坐标系其实不是桌面坐标系，也不是当前窗口的客户区坐标系，而是父窗口的客户区坐标系。这个点可能在你移动非子窗口的时候没有什么影响，但是你想移动子窗口的时候就会出问题了，老是达不到你想要的效果那是非常烦人的，而你debug进去发现你的数据又都是对的。当你意识到该函数使用的坐标系的时候，对应的问题就都能够解决了。

我列举2个例子，一个是设置窗口为顶级窗口同时修改为覆盖整个桌面工作区，另一个是移动子窗口对话框到主对话框的客户区左上角。2个例子都在我的代码内部，后面我会提供代码下载。

例子一，设置窗口为顶级窗口同时修改为覆盖整个桌面工作区。
将下面的代码放在你的主对话框的OnInitDialog()函数内部就能够达到例子一的效果了。

1
2
3
4
5
RECT rect;
SystemParametersInfo(SPI_GETWORKAREA, 0, (PVOID)rect, 0);
m_nScreenWidth = rect.right - rect.left;
m_nScreenHeight = rect.bottom - rect.top;
SetWindowPos(wndTop, rect.left, rect.top, m_nScreenWidth, m_nScreenHeight, SWP_SHOWWINDOW);

例子二，移动子窗口对话框到主对话框的客户区左上角。
这个例子的实现比较麻烦，首先修改子对话框的资源文件里面的属性，一定改成child类型的对话框。其次，用非模式对话框创建出子对话框，同时注意把主对话框最为其父窗口。最后只需要在child对话框的OnInitDialog()函数里面调用SetWindowPos(wndTop, 0, 0, 0, 0, SWP_NOSIZE);//移动子窗口,则坐标是相对于父窗口客户区就能达到效果了。这三个操作是缺一不可的。

代码下载地址，实验二。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

正如大家所知道的那样，多核多cpu越来越普遍了，而且编写多线程程序也是件很简单的事情。在Windows下面，调用CreateThread函数一次就能够以你想要的函数地址新建一个子线程运行。然后，事情确实你发现创建多线程根本没有让程序快多少，也没有提高多少cpu利用率，甚至可能让cpu利用率下降。唯一能够确定的是多线程能够避免界面假死。为什么会是这样的了。本文将举一些例子和讲述一些原因。

首先，我来讲一下多处理的一些知识。如下图所示，

多处理器系统也只有一个待运行的线程队列，内存中也只有一个操作系统拷贝，而且也只有一个内存系统，但是会有多个cpu同时运行不同的线程。一个cpu运行一个线程，那么上图中的系统最多能在同一时间运行2个线程。其实，多处理系统需要掌握的知识不是这些，而是缓存一致性。
现在来解释下什么是缓存一致性。由于，还是只有一个内存系统。所有cpu都要和这个内存系统通信，但是只有一条总线，那么这无疑会造成总线紧张，限制整体的速度了。那么，你多个cpu也没多少意义了。解决这个问题的办法还是利用cpu的缓存机制，学过组成原理的同学都知道，cpu的缓存命中率还是很高的，有90%以上吧。那么，我继续利用缓存机制还是可以降低总线的频繁使用的。但是，每个cpu都有自己的缓存。如果有2个cpu的缓存存储的是同一内存数据的内容，其中一个cpu的缓存更新了，另外一个cpu的缓存也必须更新，这就是所谓的缓存一致性。编程多线程程序的一个很重要的一点就是避免因为缓存一致性引起的缓存更新风暴。
现在我举一个缓存更新风暴的例子。
如图所示的类定义，
缓存一致性风暴
锁lockHttp和lockSsl中间只有8个字节，而绝大部分系统上一个缓存行是128个字节，那么这2个锁很可能就处在同一个缓存行上面。那么，最坏的情况会发生什么事情了。假设处理器P1在运行一个处理http请求的线程T1，处理器P2在运行一个处理ssl请求的线程T2，那么当T1获得锁lockHttp的时候，锁的内容就会改变，为了保持缓存一致性，就会更新P2的缓存。那么，T2要获得锁lockssl的时候，发现缓存已经失效了，就必须从内存中重新加载缓存之类。总之，这会将缓存命中率降低到90%以下，引起性能的严重降低。而且发生这种事情的原因是因为我们不了解硬件的体系结构。

多cpu不能成倍提高速度的原因是任务的某些部分是必须串行处理的。比如，矩阵乘法可以分为三个部分，初始化矩阵，相乘，返回结果。这三部分第二部分可以用多线程来处理，第一部分和第三部分则是不可以的。而且第二部分必须在第一部分完成之后，第三部分必须在第一部分完成之后。那么，无论你添加多少个处理器，最快的时间都至少是第一部分和第二部分的时间之和。这个事实好像叫做Amdahl法则。
如果使用多线程，那么就必须考虑线程同步，而线程同步又是导致速度降低的关键。所以下面就讲述一些方法来加快多线程程序的吞吐速度。
方法一，把一个任务分解为多个可以子任务。
因为总有些子任务是可以并发的，多个子任务并发执行了很可能就能够避免cpu需要io操作的完成了，而且能够提高系统的吞吐量。
方法二，缓存多线程的共享数据。
当你已经在使用多线程了，很多时候必须使用共享数据。如果，数据是只读的，那么可以在第一次获取后保存起来，以后就可以重复使用了。但是，第一次的获取还是无法避免的需要线程同步操作的。
方法三，如果线程数目有限，就不要共享数据。
做法是为每一个线程实例化一个单独的数据，其实就是为每一个线程分配一块数据使用。这样没有线程同步操作了，速度可以尽可能的提示。
方法四，如果没办法确定线程数目到底有多少，那么使用部分共享吧。
部分共享其实就是使用多个资源池代替一个资源池，资源池的数目得更加经验来确定。如下图所示，

最后在提一个叫做Thundering Herd的问题，该问题维基百科有定义http://en.wikipedia.org/wiki/Thundering_herd_problem。大意是，当多个线程在等待一个资源的时候，如果事件等待到了，操作系统是唤醒所有等待的线程让它们自己去竞争资源了还是选择一个线程把资源给它。当然唤醒所有的线程肯定开销要大，而且所有没有抢到资源的线程还得重新进入等待状态，这无疑造成很多没必要的操作，浪费了没必要的线程上下文切换。总之，会不会存在Thundering Herd还是跟不同的操作系统有关的。万一存在Thundering Herd了，多线程可能就没那么好办了。

到现在我们知道了为什么多cpu并不能成倍提高程序的速度了。首先因为有些任务无法并行，其次即使是并行cpu之间还是有很多牵制的。本书的内容主要来自提高c++性能的编程技术一书。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

设计优化是一种全局的优化，是比代码优化更难判断的东西。本文只以提高c++性能的编程技术一书的说法再自己的理解为例子。性能和灵活性本来就是相互冲突的东西。将两者结合得很好的例子一般能想到STL，但是STL在特定的场合肯定比不上专用代码的性能。比如，用stl里面的accmulate累加int能够与自己的实现效果一样，但是累加string的话就会比手动实现效果差很多。所以作者提出了个这样的观点，软件库是通用的，但是软件不是，所以没必要让软件太通用，视野应该窄一点。

例子一，还是利用缓存机制。
比如，一个web服务器经常要计算时间戳，而且是在1s内要计算不少次。由于时间戳没必要以ms进行区分，那么可以只计算一次时间戳，然后将时间戳保存起来，或者作为参数传递给后面的调用。

例子二，扩展数据类型。
比如，使用字符串的时候假如经常要计算字符串长度，那么可以定义一个结构体，内部有个成员用于保存长度。这样在很多需要长度的场合就可以避免重复计算长度了。

例子三，避免公共代码陷阱。
比如，在一个公共函数中，需要处理ipv4和ipv6两种情况，那么你就必须在函数中进行判断当前处理的是ipv4还是ipv6。但是，这种判断并不是必须的，如果你不使用公共函数的话。最重要的问题是，如果有很多这样的公共函数，那么就会出现成千上万这样其实没必要的判断，无疑对于性能是一个重大的损失。

例子四，使用高效的数据结构和算法。
当然这点需要扎实的算法知识。

例子五，使用缓式计算。
同上一篇文章中描述的一样，将计算延缓到真正需要的时候。比如，调用getpeername获得对方ip地址和调用getsockname获得本地服务器ip地址都是些昂贵的调用，那么我们还是把这些调用延迟到真正需要的时候吧。而且对方ip地址可以在accept函数调用的时候就得到了，这个时候保存起来就可以了。
缓式计算类似于下面的类定义，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class X
{
    X() {veryExpensive = NULL;}
    ~X() { if (veryExpensive) delete veryExpensive; }
    Z* get_veryExpensive()
    {
        if (NULL == veryExpensive)
        {
            set_veryExpensive();
        }
        return veryExpensive;
    }

    void set_veryExpensive
    {
        veryExpensive = new Z;//do some expensive thing
        //...
    }
private:
    Z* veryExpensive;
};

例子六，避免无用计算。
比如，很多时候memset并不是必须的，那么就应该避免，尤其memset大块内存的时候。类中对成员的默认构造函数调用有的时候也是浪费，应该使用成员初始化列表。这种情况，应该还有很多其它的例子。

例子七，删除已经失效的代码。
已经失效的代码是只不会再使用的代码，你应该将其删除掉，否则那些代码还是会造成性能损失。

总之，设计上面的优化是个太难的题目了，我觉得这本书上面很多例子都有点和代码上的优化重复了。不过，性能和灵活性确实是相反的方向，有的时候牺牲灵活性是非常必须的。</pre>

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

代码优化这种东西，肯定是经验之谈，即使你对代码的执行细节理解的很清楚，没有实际的经验体会也不会对之有多大的感觉。看书本人虽然觉得是揠苗助长，但是这估计就类似于打疫苗吧。要是艾滋有疫苗现在估计就没有世界艾滋日了。所以，看看书打打疫苗还是很有好处的。
代码优化很多就是些避免冗余计算，但是场合不同，有些可能你都从没有考虑过需要这样的优化。我打算把我从提高c++性能的编程技术上面看到的代码优化总结一下，随便扯几下。

例子一，用缓存计算结果优化循环。

原始代码，

1
for (...; !done; ...) done = patternMatch(pat1, pat2, isCaseSenstive());

优化代码,
1
2
bool isSenstive = isCaseSenstive();
for (...; !done; ...) done = patternMatch(pat1, pat2, isSenstive);

这个例子比较简单，一般情况大家都能优化循环，去掉循环内部的重复的函数调用和计算等。

例子二，预先计算某些结果以优化后面的计算。
比如，你需要将一个字符串转换为大写的，你是对字符串循环一次，循环内部调用toupper了，还是预先计算出toupper的结果，以后每次查表了。
优化后的代码应该是类似于这样的。
for (char p = header; p; ++p) p = uppercaseTable[p];
你所需要做的就是在初始化时候构造出uppercaseTable这张大小为256的表，如果你需要经常做大写转换无疑能不错的提高性能。

例子三，降低灵活性来换取速度。
书上只举了一个例子，为ip地址分配内存。我们知道ip4的地址不会超过15个字节，即使ip6的地址也不是很长。如果每次，我们动态分配内存去容纳地址，这肯定是非常浪费的事情。如果你需要容纳的地址数目是有限的，那么我们完全可以静态分配数组来容纳地址。全局new和delete的操作是非常昂贵的，这不仅仅在堆内存分配过程的复制上，线程同步机制也消耗了很多cpu周期。这只是个小小的例子而已，灵活性有的时候根本没必要。

例子四，用80-20规则优化常用代码路径速度。
这个例子的内容说起来比较麻烦，其实就是利用c语言的短路逻辑判断，执行较少的代码。
比如，if (e1 || e2)和if (e1 e2)这样的代码。通过，优化可以提高速度。
假设c1为e1执行的代价，p1为e1为真的概率，c2为e1执行的代价，p2为e2为真的概率。
那么可以计算出if (e1 || e2)的代价期望，同样可以计算出if (e2 || e1)的代价期望，选择较小的即可了。

例子五，延迟计算。
有些计算你可能并不需要，那么就请等到你真正需要的时候再计算吧。

1
2
3
4
5
6
7
8
9
10
int route(Msg* msg)
{
	ExpensiveClass upstream(msg);
	if (goingUpstream)
	{
	...//use upstream
	}

	return SUCCESS;
}

这种代码明显应该把对象upstream的定义放在if内部，因为有些对象的构造和析构可能会花费很大代价。
不过，我好像记得有公司内部的代码规范禁止在构造函数和析构函数作有意义的初始化和释放，而是自己再写个Init和UnInit函数来代替构造函数和析构函数的本职作用。我也不知道哪样好点，如果是那样的话，本例子就对他们没有意义了。呵呵。

例子六，去掉无用计算。
例子的内容是用成员初始化列表代替成员的默认构造函数的调用，没有什么多说的。

例子七，恰当利用系统的缓存机制。
比如，下面结构体的定义。
struct X { int a; char b[4096]; int c;};
应该改成struct X { int a; int c;char b[4096]; };
原因是cpu缓存可能就128个字节，那么加载a的时候可能一次缓存了连在一起的128个字节。由于a和c之间距离比较远，那么c就不在缓存行里面了。如果，你需要再访问c就会造成缓存失败，就需要重新加载缓存。这种降低缓存命中率的事情确实不怎么好。但是，你也不知道编译器会不会调整内存结果，把a和c默认连在一起了。我觉得还是不要做这种假设吧，这完全是改变编程者的意图了。

例子八，去掉没必要的堆内存使用，改为堆栈内存。

例子九，谨慎使用库。
比如，string的使用很多情况就比默认的char数组慢很多。其内部七七八八的实现不知道做了多少工作了，而作为调用者可能你都不怎么清楚。就比如很多时候我们根部不需要线程同步，但是string的内部实行可能考虑了线程同步，那么对于我们这完全就是个浪费了。string.h内部的那些字符串操作函数，应该是没有考虑线程同步的，这个时候显然就快很多了。

例子十，请打开编译器优化选项。
因为很多编译器优化选项不是默认打开的，如果你没有打开，那么编译器是不可能为你做全力的优化的。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 28k 阅读时长 ≈ 25 分钟

引用计数说得直接点就是不同的对象内部共享同样的内容(内存)，同时对象能够自己跟踪自己被引用多少次，能够在没有被继续引用的时候删除自己，保证了没有内存泄漏的出现。看起来貌似java里面的垃圾回收机制了。很多事物都有两面性，引用计数也不例外。看起来牛逼的东西必然有它的弱点，总有一些地方它比不过最原始的东西。

书上说了两种极端的情况，一种是大量的对象共享少数的相同的内容，一种是同样的内容只被共享少数几次，也就是基本没多少共享。显然前者是利用引用计数的典型情况。一般来说，下面的一些条件有利于引用计数的使用。比如说，目标对象消耗大量的资源;资源的分配和释放很昂贵;高度共享:由于使用复制构造函数和赋值操作符,所以引用计数可能比较大;引用的创建和清除相对低廉。如果程序中出现大量的对象创建和释放的操作，使用引用计数的效果反而会更差，而出现大量的对象的赋值操作则适合于引用计数的使用。

一般来说主要有两种实现方式。一种是你能够修改目标类的代码的情况，一种是你不能够得到目标类代码的情况。另外，还有给这些实现加上线程同步的情况。我分别实现了相关的代码，你也可以从提高c++性能的编程计数上面找到相关的代码。

情况1的类设计图如下，

从类设计图中可以看到要实现一个引用计数需要额外的三个类。RCObject是存储引用计数变量的基类，RCPtr是一个智能指针类，RCBigInt类里面包含一个RCPtr成员，该类相当于BigInt的代理类，和BigInt向外提供同样的接口。BigInt的实现稍微复杂了点，你也可以用任何简单的类替换它。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt : public RCObject
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

template <typename T> class RCPtr
{
public:
    RCPtr(T* realPtr = NULL) : pointee(realPtr) { Init(); }
    RCPtr(const RCPtr rhs) : pointee(rhs.pointee) { Init(); }
    ~RCPtr() { if (pointee) pointee->removeReference(); }
    T* operator->() const { return pointee; }
    T operator*() const { return * pointee; }
    RCPtr operator=(const RCPtr rhs);

private:
    T* pointee;
    void Init();
};

template <typename T> void RCPtr<T>::Init()
{
    if (pointee == 0) return;

    if (pointee->isShareable() == false)
    {
        pointee = new T(*pointee);
    }
    pointee->addReference();
}

template <typename T> RCPtr<T> RCPtr<T>::operator=(const RCPtr rhs)
{
    if (pointee != rhs.pointee)
    {
        if (pointee) pointee->removeReference();
        pointee = rhs.pointee;
        Init();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCPtr<BigInt> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果:

情况2的类设计图如下所示，

从图中可以看到，由于无法修改BigInt的实现，引入了一个新类CounterHolder作为引用计数的中间类。该类继承自RCObject，智能指针类RCIPtr包含一个CounterHolder的指针，而CounterHolder里面才包含一个BigInt的指针。
这就相当于多了一次间接操作，因此在RCIBigInt的创建和删除操作中会增加时间，这可以从运行结果中可以看到。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

template <typename T> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter) { Init(); }
    ~RCIPtr() { if (counter) counter->removeReference(); }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
    };

    CountHolder* counter;
    void Init();
};

template <typename T> void RCIPtr<T>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T> RCIPtr<T> RCIPtr<T>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter) counter->removeReference();
        counter = rhs.counter;
        Init();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果：

最后给出的是多线程版本的代码，在Windows下可以用临界区或者互斥体实现。互斥体实现的版本比较慢，但是临界区的版本为什么在gcc的release版本中运行出现内存错误了，而debug版本中没有问题，在vc6下运行也没有问题。

临界区版本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

class CriticalSectionLock
{
public:
    CriticalSectionLock()
    {
        InitializeCriticalSection(csMyCriticalSection);
    }
    ~CriticalSectionLock()
    {
        DeleteCriticalSection(csMyCriticalSection);
    }
    void lock()
    {
        EnterCriticalSection(csMyCriticalSection);
    }
    void unlock()
    {
        LeaveCriticalSection(csMyCriticalSection);
    }
private:
    CRITICAL_SECTION csMyCriticalSection;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt, CriticalSectionLock> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在vc6下的运行结果,

从结果中可以看出RCIBigInt的赋值操作情况在性能上已经没有多少优势了，在vc6下反而更慢，这主要是因为线程同步操作的原因。

互斥体版本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

class MutexLock
{
public:
    MutexLock()
    {
        hMutex = CreateMutex(NULL, FALSE, NULL);
    }
    ~MutexLock()
    {
        CloseHandle(hMutex);
    }
    void lock()
    {
        WaitForSingleObject(hMutex, INFINITE);
    }
    void unlock()
    {
        ReleaseMutex(hMutex);
    }
private:
    HANDLE hMutex;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt, MutexLock> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在codeblocks配gcc的环境下的运行结果，

从图里面还是能看到，在Windows下用互斥体同步确实比较慢。

发表于 分类于 ， ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

stl这种东西这几年确实用得不少了，大一暑假刚开始看c++primer的时候就知道有这么个东西，当时觉得非常神奇的样子。不过，我用stl最多的地方还是在做acm的一些题目的时候。很多时候为了方便，为了代码简洁性就用stl了。我还是比较喜欢stl这个东西的。

我只打算讲点简单的东西。比如大致的实现原理和使用的一些注意情况，另外讲下我对迭代器失效的理解。

vector是一个动态数组，既然是数组，那么在末尾增加和删除是很快的，复杂度是O(1)。但是，在其它位置增加和删除复杂度就跟位置有关系了，复杂度是O(n)。默认情况对vector的查找是不会应用二分的，所以你用stl里面的find查找复杂度也是O(n)。当vector的容量大小需要经常改变时候，你可以预估计容量的最大大小，然后调用reserve函数预分配一块大内存，这样就可以避免频繁的内存分配释放造成的性能损失了。

deque类似于vector。但是在头部增加和删除复杂度也是O(1)，不过我没看过stl的实现，也不知道为什么。

list的内部实现大概是双向链表。那么在任意位置的插入和删除复制度都是O(1)。对于查找的话，虽然理论复杂度也是O(n)。不过，list的查找肯定会比vector慢的，因为多了一次取地址的间接操作。而且，数组因为地址是连续的，可以来个地址的缓存。

set和map内部是用红黑树实现的。红黑树也就是一棵平衡查找树吧，大家都学过二叉平衡树，红黑树大概类似这种东西。算法导论里面有对红黑树的详细介绍，不过看得让我很头晕，而且我也不想去实现一个红黑树，光是二叉平衡树的旋转已经很无语了。反正红黑树类似二叉平衡查找树就行了。那么，红黑树的插入删除都可能改变原有结点的位置之间的关系，意思是不仅仅是破坏或者增加一个结点的位置。但是原有结点的地址肯定是没有变化的。增删查改的复杂度都是log(n)。还有，对set和map的查找要应用容器内部的成员函数find，而不是全局的stl函数find。前者是二分查找，而后者是顺序查找。

下面我讲讲我对stl迭代器失效的理解。其实，大致知道了stl容器的实现，这个问题就很好理解了。

vector是动态数组，那么插入和删除元素都会改变该元素后面元素的地址，那么先前获取的指向后面位置元素的迭代器就会失效了。而且即使你插入在最后，也可能使所有的迭代器失效，因为可能这个时候刚好vector必须增加容量来容纳你新插入的元素了。你再访问这些迭代器的话，不是访问到错误的内容就是内存错误了。

list的话，由于结点是孤立的，是用指针把所有结点串起来的，那么原有结点的地址一直都不会改变。只要不对结点进行了删除，那么原来获取的迭代器就不会失效。但是，++和—的结果可能会和原来不一致的。

deque类似于vector吧。不过，我还是不是很清楚。

set和map的话，类似于list。它们的结点地址也一直不会变化，但是插入和删除会改变整棵树的布局，所以原来的迭代器++或者—之后可能就会指向乱七八糟的东西了。但是，你获取原来的元素还是可以的。

总之，对容器进行插入和删除之后一定要注意迭代器失效的情况，最好是从写法上避免这种可能性吧，而不是利用迭代器不失效的可能性。