程序性能优化（一）

通过设计合理的数据结构和算法将一些本需要在运行期间计算的信息预先存放在内存中来提升性能，是一种空间换时间的优化，下面一些实际的例子描述了这种优化方法的使用：

在一个递增的数组中查询和待查找元素最接近的的索引

例如数组[1,2,3,4,5]，待查找元素为1.1返回数组索引0，待查找元素为1.6返回数组索引1，通过计算和数组每个元素的差值，循环遍历一遍数组可以即可得到索引值，如下代码所示：

const double g_searchTable[] = {1,2,3,4,5};

int getIndex(double data)
{
    int index = 0;
    double temp;

    double temp1 = fabs(g_searchTable[0]-data);

    for(int i=0;i<sizeof(g_searchTable)/sizeof(g_searchTable[0]);i++)
    {
        temp = fabs(g_searchTable[i]-data);
        if(temp < temp1)
        {
            temp1 = temp;
            index = i;
        }
    }

    return index;
}

View Code

该代码在循环内部存在浮点数计算、计算绝对值而且要遍历数组，如果数组足够大且频繁调用程序性能必然低下。我们可以通过把非递减的数组元素看成一个连续区域中的几个位置，计算出各个位置间的中点，划分为不同的区间，即可通过比较待待查找的元素落在什么区间中得出索引值。入下图所示如果待查找元素小于1.5返回索引0。这里就需要我们增加一个区间数组[1.5,2.5,3.5,4.5],在代码中直接跟元素比较即可得到索引信息。

const double g_searchTable[] = {1,2,3,4,5};
const double g_searchDivTable[] = {1.5,2.5,3.5,4.5};

int getIndex1(double data)
{
    int index = 0;

    for(int i=0;i<sizeof(g_searchDivTable)/sizeof(g_searchDivTable[0]);i++)
    {
        if(data < g_searchDivTable[i])
        {
            return i;
        }
    }

    return sizeof(g_searchDivTable)/sizeof(g_searchDivTable[0]);
}

View Code

通过增加一个对应的区间数组空间，我们消除了浮点运算、绝对值计算，并且在确定待查元素的区间后即可得到结果，不用继续遍历数组。

switch语句的编译优化

我们在代码中经常使用switch语句，其结构清晰，通过计算表达式的值跳转到指定的case分支中，在编译过程中往往并不是将表达式同case常量依次比较来定位到具体分支中，这样的效率往往很低下，编译器通常使用了“跳转表技术”来定位分支目标地址。跳转表可以看成一个地址数组，其中每一个元素表示一个代码段的地址，通过映射表达式值为跳转表中的索引即可获取对应的目标地址。如下switch语句：

switch(n)
{
　　case 5:   //ADDR1
　　case 7:   //ADDR2
　　deafult:  //DEFAULT_ADDR
}

编译器往往转换为如下跳转表：

JumpTable = [ADDR1, DEFAULT_ADDR, ADDR1];

int index = n-5;
if index >2
    goto DEFAULT_ADDR

goto JumpTable [index]

通过使用跳转表技术，增加跳转表的空间消耗，可以直接定位到目标地址。

字符串到系统标示符的映射

在一些系统中我们往往需要将一系列的字符串转换为系统对应的标示符，例如编译器的分词模块对输入的“int”字符串转换为系统的TK_INT类型。系统中默认的标示符往往很多，如果对输入字符串通过代码分支依次比较将十分耗费时间。为了提升效率我们可以考虑通过使用hash技术，选取合适的散列函数将字符串转换为一个映射数组的下标。下面代码将“add”、“sub”、“mul”、“div”转换为系统的对应类型：

typedef enum
{
    T_ADD,
    T_SUB,
    T_MUL,
    T_DIV,
    T_ERR
}Token;
typedef struct
{
    char* str;
    Token tk;
    char nextFlag;
}MAP_T;

MAP_T map0[] = {{"add",T_ADD,1},{"sub",T_SUB,1},{"mul",T_MUL,0}};//“add”、“sub”、“mul”通过散列函数计算出相同的数组下标0
MAP_T map1[] = {{"div",T_DIV,0}};//“div”通过散列函数计算出数组下标1
//映射信息
MAP_T* hashTable[] = {map0,map1};

Token getTk(char* str)
{
    int index = -1;
    MAP_T *pMap = NULL;

    index = getHashCode(str);
    pMap = hashTable[index];

    while(1)
    {
        if(0 == strcmp(str,pMap->str))
        {
            return pMap->tk;
        }
        if(0 == pMap->nextFlag)
        {
            break;
        }
        pMap++;
    }
    return T_ERR;
}

View Code

入上所示，我们保存了所有字符串和系统标示符的对应关系，计算待转换字符串的hash值即可快速定位到一个小的区间中。通过选取适当散列函数可以的得到更好的效率。这里使用了链地址法来解决hash冲突。

以上实例都是基于空间换时间的优化方式，通过设计合理的数据结构，保存关键的信息，可以极大的对程序性能优化。

转载请注明原始出处：http://www.cnblogs.com/chencheng/p/3372945.html

程序性能优化（一）

推荐阅读