优化C代码中的I / O(输出)+循环
我有一个代码从stdin读取(10 ^ 5)int(s)然后执行## i后在stdout输出它们。 我通过使用“setvbuf”和使用“fgets_unlocked()”读取行来处理INPUT部分,然后解析它们以获得所需的int(s)。 我有2个问题,我无法解决:
1.)因为我在stdout上打印了500万,花了很多时间:有什么方法可以减少它(我尝试使用fwrite()但o / p打印出不可打印的字符,因为使用fread的原因读入int缓冲区 )
2.)解析int(s)的输入后说’x’我实际上通过对循环中的no执行%(mod)来找到除数的数量。(参见下面的代码):也许这也是一个我的代码超时的原因:对此有任何改进建议。 非常感谢这实际上是来自http://www.codechef.com/problems/PD13的问题
# include # define SIZE 32*1024 char buf[SIZE]; main(void) { int i=0,chk =0; unsigned int j =0 ,div =0; int a =0,num =0; char ch; setvbuf(stdin,(char*)NULL,_IOFBF,0); scanf("%d",&chk); while(getchar_unlocked() != '\n'); while((a = fread_unlocked(buf,1,SIZE,stdin)) >0) { for(i=0;i<a;i++) { if(buf[i] != '\n') { num = (buf[i] - '0')+(10*num); } else if(buf[i] == '\n') { div = 1; for(j=2;j<=(num/2);j++) { if((num%j) == 0) // Prob 2 { div +=j; } } num = 0; printf("%d\n",div); // problem 1 } } } return 0; }
// Prob 2你的biggesr现在问题….你只是想找到除数的数量?
我的第一个建议是在某种程度上缓存你的结果……但这需要你开始时存储量的两倍:/。
您可以做的是事先生成素数列表( 使用筛选算法 )。 知道列表中最大的数字N
并生成所有素数直到他的平方根是理想的。 现在,对于列表中的每个数字,您希望将其表示作为因子的乘积,即
n = a1^p1 * a1^p2 *... *an^pn
那么除数的总和就是 。
((a1^(p1+1) - 1)/(a1 - 1))*((a2^(p2+1) - 1)/(a2-1))*...*((an^(pn+1) - 1)/(an-1))
要理解你有(对于n = 8) 1+ 2 + 4 + 8 = 15 = (16 - 1)/(2 - 1)
它将大大提高速度,但整数分解(你真正做的)真的很贵……
编辑:
在您的链接中,最大值为5000000,因此您最多有700个素数
简单的分解算法
void primedecomp(int number, const int* primetable, int* primecount, int pos,int tablelen){ while(pos < tablelen && number % primetable[pos] !=0 ) pos++; if(pos == tablelen) return while(number % primetable[pos] ==0 ){ number = number / primetable[pos]; primecount[pos]++; } //number has been modified //too lazy to write a loop, so recursive call primedecomp(number,primetable,primecount, pos+1,tablelen); }
编辑 :而不是计数,使用primepow = a; primepow = a*primepow;
计算a^(n+1)
primepow = a; primepow = a*primepow;
primepow = a; primepow = a*primepow;
在你有hashmap的C ++或java中它会更清晰。 最后, primecount
包含我上面讨论的pi
值。
即使它看起来很可怕,你也只会创建一次。 现在,该算法在最坏的情况下在O(tablelen)
运行,其为O(square root(Nmax))
。 你的初始循环在O(Nmax)
。
您可以比printf打印得快得多。
查看itoa()
,或编写自己的简单函数,将整数转换为ascii非常快。
这是一个快速n-dirty版本的itoa应该可以快速用于您的目的:
char* custom_itoa(int i) { static char output[24]; // 64-bit MAX_INT is 20 digits char* p = &output[23]; for(*p--=0;i/=10;*p--=i%10+0x30); return ++p; }
请注意,此function有一些严重的内置限制,包括:
- 它不处理负数
- 它目前不处理十进制forms的大于23个字符的数字。
- 它本质上是线程危险的。 不要尝试在multithreading环境中。
- 只要再次调用该函数,返回值就会被破坏。
我写这篇文章纯粹是为了速度,而不是为了安全或方便。
版本2基于@UmNyobe和@wildplasser的建议(见上面的评论)代码执行在线判断需要0.12秒和3.2 MB的内存。 我自己检查了2 * 10 ^ 5 int(输入),范围从1到5 * 10 ^ 5,并执行:
真正的0m0.443s
用户0m0.408s
sys 0m0.024s
**请查看是否可以进行更多优化。
enter code here /** Solution for the sum of the proper divisor problem from codechef **/ /** @ author dZONE **/ # include # include # include # include # define SIZE 200000 inline int readnum(void); void count(int num); int pft[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709}; unsigned long long int sum[SIZE]; int k = 0; inline int readnum(void) { int num = 0; char ch; while((ch = getchar_unlocked()) != '\n') { if(ch >=48 && ch <=57) { num = ch -'0' + 10*num; } } if(num ==0) { return -1; } return num; } void count(int num) { unsigned int i = 0; unsigned long long tmp =0,pfac =1; int flag = 0; tmp = num; sum[k] = 1; for(i=0;i<127;i++) { if((tmp % pft[i]) == 0) { flag =1; // For Prime numbers not in pft table pfac =1; while(tmp % pft[i] == 0) { tmp =tmp /pft[i]; pfac *= pft[i]; } pfac *= pft[i]; sum[k] *= (pfac-1)/(pft[i]-1); } } if(flag ==0) { sum[k] = 1; ++k; return; } if(tmp != 1) // For numbers with some prime factors in the pft table+some prime > 705 { sum[k] *=((tmp*tmp) -1)/(tmp -1); } sum[k] -=num; ++k; return; } int main(void) { int i=0,terms =0,num = 0; setvbuf(stdin,(char*)NULL,_IOFBF,0); scanf("%d",&terms); while(getchar_unlocked() != '\n'); while(terms--) { num = readnum(); if(num ==1) { continue; } if(num == -1) { perror("\n ERROR\n"); return 0; } count(num); } i =0; while(i