浅谈代码提高运行效率的问题

        最近看一些别人写的代码还有自己的一些总结，对于代码的运行效率，自己有一些见解与大家分享一下；对于代码运行效率，对于初学者或者而言可能不是很关注，因为我们首先需要先把功能实现了，调试没问题了。但是对于做嵌入式的朋友，对代码的效率和内存空间使用上会比较关注，因为平台的先执行决定了我们必须关注这两点。要实现让代码运行效率更高，对于编程者的功底也是很有要求的，起码有若干年的开发经验吧（个人觉得）。

        对于简单功能的实现，我们应该是“手到擒来”，比如对于如下的一个需求：

        要求：输入一串字符，计算该字符串中数字的个数，比如输入："abc123cdef4567";输出7；以下是code：

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[80];
    int i, cnt = 0;

    printf("Please input a string: ");
    scanf("%s", str);


    for (i = 0; i < strlen(str); i++)
        if (str[i] >= '0' && str[i] <= '9')
            cnt++;
    printf("%d\n", cnt);
    return 0;
}

如上的代码，在Linux下通过gcc -Wall -g a.c -o a编译运行，输入如上的测试用例，输出的结果位7；现在分析一下代码，影响代码运行效率，可以从两方面去分析，分别是时间复杂度和空间复杂度；对于，这个code，时间复杂度主要是循环次数，空间复杂度主要是申请的空间，由于用户可以输入的字符串长度不确定，因此我们只能尽可能申请的比用户输入的字符串多一些（但是若用户输入的字符多于80个，那么就会越界的，这个是属于安全问题，在这儿暂不考虑，其实是可以通过其他方式规避这种越界的）。对于这个程序，我们着重考虑时间复杂度，对于strlen函数，通过我们对库函数的了解可知，strlen也是循环遍历，直到遇到'\0'返回字符串长度。所以，我们虽然用了一个循环，但是循环里还有循环，并且这个循环（strlen内的）还可能很多次，跟字符串的长度有关。所以，我们考虑对上面的程序做修改，去掉多余的循环；修改如下：

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[80];
    int i, len, cnt = 0;

    printf("Please input a string: ");
    scanf("%s", str);

    len = strlen(str);
    for (i = 0; i < len; i++)
        if (str[i] >= '0' && str[i] <= '9')
            cnt++;
    printf("%d\n", cnt);
    return 0;
}

有的朋友可能会说，在上一个code中，编译器会对其优化，优化成上面的这种形式。我对编译器的这种优化持怀疑态度，编译器会可能会优化吧。但是与其让编译器优化，不如自己显示优化，即使某些编译器不能优化，我们自己可以通过这种形式加以优化。这个code是多定义了一个变量，可但能会减少很多次的循环，这就是所谓的利用空间换时间的策略吧；

代码优化到目前，结束了吗？没有，远远没有；虽然我们（排除编译器优化）减少了多次循环，提高的代码运行效率，但是至少还是要计算一次字符串长度，那么可否把这样的一次求长度也省掉呢，答案是肯定的；我们在对第二个程序做进一步的优化，如下：

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[80];
    int i, cnt = 0;

    printf("Please input a string: ");
    scanf("%s", str);

    for (i = 0; str[i]; i++)
        if (str[i] >= '0' && str[i] <= '9')
            cnt++;

    printf("%d\n", cnt);

    return 0;
}

这里需要注意下，'\0'和0是相等的，即当对字符串进行遍历时遇到'\0'即0，就会退出循环，这样就会省去求字符串长度了，通过编译字符串一次实现统计数字的个数。又减少了一次循环，时间复杂度又进一步降低，同时较上一个代码有减少了len变量的申请。如果对指针使用比较熟练，可以用指针代替i，如下：

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[80], *pstr;
    int cnt = 0;

    printf("Please input a string: ");
    scanf("%s", str);

    pstr = str;
    while (*pstr) {
        if (*pstr >= '0' && *pstr <= '9')
            cnt++;
        pstr++;
    }

    printf("%d\n", cnt);

    return 0;
}

到目前为止，我认为的优化结束了。如果可以继续优化欢迎大家提出来。

为了提高代码的运行效率，从算法的角度可能效果更好些；对于某些功能，若考虑使用合适的算法，代码运行效率会更高。比如判断一个数的是否为素数。从素数的定义角度上考虑：指除了1和它本身以外，不能被任何整数整除的数；那么若但从定义角度上分析，代码可以写成如下：

int is_prime(int n)
{
    int i;

    for (i = 2; i < n; i++)
        if (n % i == 0)
            return 0;

    return 1;
}

代码很简单，但是我们如果考虑时间复杂度，就要考虑循环次数；若传入的n是一个素数，并且是一个比较大的素数，那么循环的此时还是很可观的（循环次数n - 2次)。所以，有没有算法（判断素数）可以减少这样的循环呢；答案是肯定的。算法就是：对i循环对n开平方次，即只要判断n对2～n的开平方取余是否位0就可以判断n是否位素数了。代码如下：

int is_prime(int n)
{
    int i, size;

    size = sqrt(n);
    for (i = 2; i <= size; i++)
        if (n % i == 0)
            return 0;

    return 1;
}

若n为3607，若用第一种素数定义法去判断是否为素数，需要循环3607 - 2次，若用第二种方法，则循环60 - 2次；素数越大，第二种方法的效率越明显；当然，对于判断素数还可以进一步优化判断，若传入的实参是偶数，直接pass，不是素数；若是奇数，则可能是素数，可以使用函数做判断。若求某个区间内有多少个素数，比如1000以内的。通过先排除偶数，然后再判断奇数，效率又会有很大提高；

以上是个人的见解，如有不同想法欢迎提出来，大家一起分享～