算法于效率

算法与效率


/* 和以前一样，这里的代码也是从记事本中粘贴来的，代码无法缩进，sorry了 ^_^ */


现在我们要写的程序就是将文件内的数字读出来，将char转化为int。在C中，读入的char字符虽然为“12345”但是在int中则仍然为ASCII字符，想要将读入的char转化为int，我们可以写一段程序，采用最简单的方法，莫过于将程序中的数字装入数组，然后按位乘以10并相加，请看以下代码：
#include
#include
#include

void main()
{
char c, *ch; int j=0;
ch = new char[80];
ifstream i(""test"", ios::in | ios::binary);
if(!i) { cerr<<""open error. ""; exit(0); }

while(i.get(c))
{
if(c>=0x30 && c<=0x39) ch[j++]=c;
} ch[j]='''';

int k=0; int tmp, ct=j-1, b;
for(int i=0; i<=j-1; i++)
{
ct--;
if(ch[i]==0x30) tmp=0;
if(ch[i]==0x31){ tmp=1;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x32){ tmp=2;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x33){ tmp=3;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x34){ tmp=4;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x35){ tmp=5;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x36){ tmp=6;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x37){ tmp=7;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x38){ tmp=8;
for(b=0; b<=ct; b++)
tmp*=10; }

if(ch[i]==0x39){ tmp=9;
for(b=0; b<=ct; b++)
tmp*=10; }
k+=tmp;
}
cout< }
这几乎是最蠢的算法，几乎每读入一个数字，全部采用if条件判断，相应的效率肯定无法提高，在对于程序速度要求很高的情况下，例如游戏程序，肯定无法满足要求。
在这里，我们可以使用结构来提高速度，满足要求，在struct中定义字符型和int型，相对地将每个字符对应结构中的int，然后扫描该结构，请看下列程序：
#include
#include
#include
struct X {
char Char;
int num;
};

X ex[10]={
{0x30, 0}, {0x31, 1}, {0x32, 2}, {0x33, 3}, {0x34, 4},
{0x35, 5}, {0x36, 6}, {0x37, 7}, {0x38, 8}, {0x39, 9}
};

void main()
{
char c, *ch; int j=0;
ch = new char[80];
ifstream i(""test"", ios::in | ios::binary);
if(!i) { cerr<<""open error. ""; exit(0); }

while(i.get(c))
{
if(c>=0x30 && c<=0x39) ch[j++]=c;
} ch[j]='''';

int k=0; int tmp, ct=j-1, b;
for(int i=0; i<=j-1; i++)
{
ct--;
for(int p=0; p<=9; p++){
if(ch[i]==ex[p].Char)
{
tmp = ex[p].num;
for(b=0; b<=ct; b++)
tmp*=10;
}
}
k+=tmp;
}
cout< }
这里，在for循环中，扫描结构中的数据，如果与数组中对应则进行处理，因为在结构中已经定义了相对应的整型，所以处理速度非常快。
这就是算法所带来的程序效率，在Windows时代，可视化编程几乎忽略了算法的存在，虽然对于编程人员来说是个省心的编程方法，但是对于整个程序来说无疑是一大败笔，GNU的高级程序员们曾经说过：“最好的程序就是：聪明的数据结构+笨拙的代码”。
以上的程序速度很快对吗？不过，还有更精巧，速度更快的算法，请看下列程序：
#include
#include

void main ()
{
char ch; int j=0, tmp;
ifstream i(test, ios::in | ios::binary);
if(!i) { cerr<<""open error. ""; exit(0); }

while(i.get(ch))
{
if(ch>=0x30 && ch<=0x39)
j=j*10+((int)ch-''0'');
}
cout< }
几乎无须扫描和比较任何数据就可快速计算出相对数字，这段代码比上面两段代码执行效率都快几乎15%。

这就是不同算法带来的不同效率，在大工程中，您就可以看出它们之间的区别了。

DarkSpy于1999/12/25