写了一个计算pi值的c语言程序:
https://github.com/gongchengra/hacker/blob/master/c/16_pi.c
全部代码如下:
#include <stdio.h>
#define NUMBER 100000
int array_divide_number(int *array, int number, int size)
{
int i,tmp;
int modulo=0;
for(i=0;i<size;i++)
{
tmp = array[i]+modulo*10;
array[i] = tmp/number;
modulo = tmp%number;
}
return 0;
}
void print_array(int *array, int size)
{
int i,last;
for(last=size-1;last>=0;last--)
{
if(array[last] != 0)
{
break;
}
}
for(i=0;i<=last;i++)
{
printf("%d",array[i]);
}
printf("\n");
}
void copy_array(int *source, int *target, int size)
{
int i;
for(i=0;i<size;i++)
{
target[i] = source[i];
}
}
void plus_array(int *augend, int *addend, int *sum, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
sum[i] = augend[i] + addend[i];
if(sum[i]>9)
{
sum[i] = sum[i] % 10;
sum[i-1]++;
}
}
}
void minus_array(int *minuend, int *subtracter, int *answer, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
if(minuend[i] >= subtracter[i] || i == 0)
{
answer[i] = minuend[i] - subtracter[i];
}
else
{
if(minuend[i-1] == 0)
{
minuend[i-2]--;
minuend[i-1] = 10;
}
minuend[i-1]--;
answer[i] = 10 + minuend[i] - subtracter[i];
}
}
}
int main()
{
int i;
int flag=1;
int d5[NUMBER]={0};
int t5[NUMBER]={0};
int d239[NUMBER]={0};
int t239[NUMBER]={0};
int pi[NUMBER]={0};
d5[0]=16;
d239[0]=4;
array_divide_number(d5,5,NUMBER);
array_divide_number(d239,239,NUMBER);
//every iteration will increase three valid digitals
for(i=1;i<NUMBER*3/2;i+=2)
{
copy_array(d5, t5, NUMBER);
copy_array(d239, t239, NUMBER);
array_divide_number(t5,i,NUMBER);
array_divide_number(t239,i,NUMBER);
if(flag > 0)
{
plus_array(pi,t5,pi,NUMBER);
minus_array(pi,t239,pi,NUMBER);
}
else
{
minus_array(pi,t5,pi,NUMBER);
plus_array(pi,t239,pi,NUMBER);
}
flag = -1*flag;
array_divide_number(d5,5*5,NUMBER);
array_divide_number(d239,239*239,NUMBER);
}
print_array(pi, NUMBER);
return 0;
}
程序可以工作,但是需要的时间太久,
time ./16_pi.exe >pi3.log
./16_pi.exe > pi3.log 617.76s user 0.15s system 98% cpu 10:27.94 total
计算pi的十万位需要617秒,将近十分钟,请教SF上的达人,在不改变计算pi的算法前提下有没有办法可以优化程序来减少程序运行的时间?
刚好考完试比较闲,所以上午都在优化这个程序:)。
试了各种优化方法,有些方法行有些不行,不行的这里就略过。
另外,因为各人的电脑不同,所以不要看绝对的数据,看相对值的变化就好了。
说说我的过程:
编译器选项优化
考虑lz的代码应该是release版本的,对应的就是-O2
选项,那么试试gcc -O2
,定下基值:
# 第1组是计算10000位的结果。为了尽快看到结果,之后我都是优化10000位的版本
gcc -O2 ./Pi.c && time ./a.out > p4.out
./a.out > p4.out 2.46s user 0.01s system 98% cpu 2.502 total
# lz的10万位的计算结果。(我觉得lz的程序是不是还是debug模式……)
gcc -O2 ./Pi.c && time ./a.out > p4.out
./a.out > p4.out 258.91s user 0.16s system 99% cpu 4:19.61 total
然后试一下各种编译器选项,最后确定-O3
的效果最好。
gcc -O3 ./Pi.c
time ./a.out > p.out
./a.out > p.out 2.36s user 0.00s system 97% cpu 2.392 total
检查下生成输出文件的md5,跟优化前一致。
之后又试了别的编译器,最好的还是用gcc。
代码上的优化
不能改算法,那么就替换掉部分函数。
比如,把copy_array
改成memcpy
,结果跑到了2.30s。
又试了下,把int数组全改成short,结果没有变化囧。
试着分拆下for循环。发现把array_divide_number
拆成一次性算5个,居然能跑到2.28s。(不是偶然,多次重复运行都能达到差不多的结果)
循环拆开有时候能够提高运算效率,不过具体有没有效果基本靠运气……
然后又试了下其他的小修小补,没多大影响。
最后试了下,用宏代替所有的函数。依然没变化。
看来在编译器使用-O3
优化后,靠微调代码的优化已经没有多大空间了。
进一步的优化?
如果要进一步做优化,可以考虑下利用特殊的硬件提高运算效率,比如GPU或者MIC之类的。因为我手头上没有“特殊的硬件”,所以这一步就没有尝试了。
有条件可以试一下:)
总结:
- 编译器选项上的优化是最重要的。人工的优化基本上靠设计更好的算法,光是考虑细枝末节,成效不大。
- 这个算法好处是没有涉及浮点数,精度有保证。坏处是依赖关系多,很难矢量化或并行化,而且内存利用也不充分。
贴个最后的结果:
gcc -O3 Pi.c && time ./a.out > ../p.out
./a.out > ../p.out 238.82s user 0.12s system 99% cpu 3:59.65 total
从258.91s优化到238.82s,嗯。
最后的代码:
#include <string.h>
#include <stdio.h>
#define NUMBER 100000
void array_divide_number(short *array, const int number, const int size)
{
int i;
int modulo=0;
for(i=0;i<size;i+=5)
{
int tmp;
tmp = array[i]+modulo*10;
array[i] = tmp/number;
modulo = tmp%number;
tmp = array[i + 1]+modulo*10;
array[i + 1] = tmp/number;
modulo = tmp%number;
tmp = array[i + 2]+modulo*10;
array[i + 2] = tmp/number;
modulo = tmp%number;
tmp = array[i + 3]+modulo*10;
array[i + 3] = tmp/number;
modulo = tmp%number;
tmp = array[i + 4]+modulo*10;
array[i + 4] = tmp/number;
modulo = tmp%number;
}
}
void print_array(short *array, int size)
{
int i,last;
for(last=size-1;last>=0;--last)
{
if(array[last] != 0)
{
break;
}
}
for(i=0;i<=last;++i)
{
printf("%d",array[i]);
}
printf("\n");
}
void plus_array(short *augend, short *addend, short *sum, const int size)
{
int i;
for(i=size-1;i>=0;--i)
{
sum[i] = augend[i] + addend[i];
if(sum[i]>9)
{
sum[i] = sum[i] % 10;
sum[i-1]++;
}
}
}
void minus_array(short *minuend, short *subtracter, short *answer, const int size)
{
int i;
for(i=size-1;i>=0;--i)
{
if(minuend[i] >= subtracter[i] || i == 0)
{
answer[i] = minuend[i] - subtracter[i];
}
else
{
if(minuend[i-1] == 0)
{
minuend[i-2]--;
minuend[i-1] = 10;
}
minuend[i-1]--;
answer[i] = 10 + minuend[i] - subtracter[i];
}
}
}
int main()
{
int i;
int flag=1;
short d5[NUMBER]={0};
short t5[NUMBER]={0};
short d239[NUMBER]={0};
short t239[NUMBER]={0};
short pi[NUMBER]={0};
d5[0]=16;
d239[0]=4;
array_divide_number(d5,5,NUMBER);
array_divide_number(d239,239,NUMBER);
//every iteration will increase three valid digitals
const int end = NUMBER * 3 / 2;
for(i=1;i<end;i += 2)
{
memcpy(t5, d5, NUMBER * sizeof(short));
memcpy(t239, d239, NUMBER * sizeof(short));
array_divide_number(t5,i,NUMBER);
array_divide_number(t239,i,NUMBER);
if(flag == 1)
{
plus_array(pi,t5,pi,NUMBER);
minus_array(pi,t239,pi,NUMBER);
}
else
{
minus_array(pi,t5,pi,NUMBER);
plus_array(pi,t239,pi,NUMBER);
}
flag = -1*flag;
array_divide_number(d5,25,NUMBER);
array_divide_number(d239,57121,NUMBER);
}
print_array(pi, NUMBER);
return 0;
}
主要是这个算法复杂度太大(10000^2),如果不优化算法,先从减少函数调用次数的角度,再从降低单位函数调用消耗时间的角度。
考虑省掉copy_array函数调用,改成memcpy:
for(i=1;i<NUMBER*3/2;i+=2)
{
copy_array(d5, t5, NUMBER);
copy_array(d239, t239, NUMBER);
array_divide_number(t5,i,NUMBER);
array_divide_number(t239,i,NUMBER);
另外,main函数5个长度10000的int数组变量,太大了,搞不好会栈溢出。
要提高程序运行的速度,不外乎更换更好的硬件,使用复杂度更低的算法,优化程序的代码
利用arctan计算pi的算法复杂度O(n2),不过是最好理解的,另外一些比较好的算法都比这个好一点,不过貌似都需要用到FFT,不仔细研究简直理解不能。。。
还有就是上面那位哥们回答的也不错,你的代码有很多可以优化的地方,开编程器优化什么的都行,尽量让程序只做必须的运算。。
主要是算法决定了程序运行时间,为什么还不能改算法呢,用这个算法吧pi=1/6(1/1^2+1/2^2+1/3^2+...)