在C code +循环优化I / O（输出） [英] Optimizing I/O(Output) in C code + a loop
问题描述
我从一个标准输入code其内容各地（10 ^ 5）INT（S），然后执行后，我##它们输出在标准输出。我以setvbuf用来＆放大器照顾输入部分的;读线使用fgets_unlocked（），然后分析他们获得所需的INT（S）。
我有2个问题，对此我无法与过来：
1），因为我打印INT（S）500万在stdout其采取大量的时间：有什么办法减少这种（我尝试使用的fwrite（），但O / P打印不可打印的字符，由于原因<一href=\"http://stackoverflow.com/questions/7632095/using-fread-to-read-into-int-buffer/9857790#9857790\">using FREAD读入缓冲区INT ）
2）分析输入的INT（S）后说'X'我实际上是在一个循环中没有做％（MOD）找到没有除数的。（在下面的code见） ：也许这也是我的code是超时的理由：
在这个任何建议改善。
非常感谢
这实际上是从 HTTP一个问题：//www.$c$cchef.com/problems/PD13
＃包括LT＆;＆stdio.h中GT;
＃定义大小为32 * 1024
焦炭BUF [SIZE]主要（无效）
{
INT I = 0，CHK = 0;
unsigned int类型J = 0，DIV = 0;
诠释A = 0，NUM = 0;
焦炭CH;setvbuf用来（标准输入，（字符*）NULL，_IOFBF，0）;scanf函数（％d个，＆安培; CHK）;
而（getchar_unlocked（）='\\ n'！）;
而（（α= fread_unlocked（BUF，1，尺寸，标准输入））大于0）
{
对于（i = 0; I＆LT; A;我++）
{
如果（BUF [I]！='\\ n'）
{
NUM =（BUF [I] - '0'）+（10 * NUM）;
}
其他
如果（BUF [I] =='\\ n'）
{
DIV = 1;
为（J = 2; J＆下; =（NUM / 2）; J ++）
{
如果（（NUM％j）条== 0）// 2习题
{
DIV + = j的;
}
}
NUM = 0;
的printf（％d个\\ N，格）; //问题1
}
}
}
返回0;
}
//习题2是您biggesr的问题，现在....你只是想找到除数是多少？
我的第一个建议将是你的结果缓存在一定程度上......但是这可能需要你在开始的存储量的两倍。/
你可以做的是生成素数的前手名单（用筛子算法 ）。这将是理想的了解您的列表中最大的数 N 并生成所有素数，直到他的平方根。现在，在你的列表中的每个数字，你想找到他重新presentation为因素的产品，即
N = A1 ^ * P1 A1 P2 ^ * ... * ^一个PN
然后除数的总和会。
（（A1 ^（P1 + 1） - 1）/（A1 - 1））*（（A2 ^（P2 + 1） - 1）/（A2-1） ）* ... *（（一个^（P N + 1） - 1）/（一个-1））
要了解你（对n = 8） 1 + 2 + 4 + 8 = 15 =（16 - 1）/（2 - 1）
这将极大地提高了速度，但整数分解（你真的做什么）真的是昂贵的...
编辑：
在你的链接，最大值为500万，所以你必须在最700的素数
简单分解算法
无效primedecomp（INT号，const int的* primetable，为int * primecount，
INT POS，诠释tablelen）{
而（POS＆LT; tablelen＆放大器;＆安培;！号％primetable [POS] = 0）
POS ++; 如果（POS == tablelen）
返回 而（编号％primetable [POS] == 0）{
数=号/ primetable [POS]
primecount [POS] ++;
}
//号码已被修改
//懒得写一个循环，所以递归调用
primedecomp（数字，primetable，primecount，POS + 1，tablelen）;}
修改：而不是计数，计算 A ^（N + 1）使用 primepow =一个; primepow = A * primepow;
这将在C更清洁++或Java，你必须HashMap中。最后 primecount 包含值我说的上述 PI。
即使它看起来吓人，您将创建 primetable 只有一次。现在，这个算法
运行在最坏情况下O（tablelen）是 O（平方根（Nmax时））。您的初始
循环跑 O（Nmax时）。
I have a code which reads around (10^5) int(s) from stdin and then after performing ## i output them on stdout. I have taken care of the INPUT part by using "setvbuf" & reading lines using "fgets_unlocked()" and then parsing them to get the required int(s). I have 2 issues which i am not able to come over with:
1.) As i am printing int(s) 5 million on stdout its taking lot of time : IS THERE ANY WAY TO REDUCE THIS( i tried using fwrite() but the o/p prints unprintable characters due to the reason using fread to read into int buffer)
2.) After parsing the input for the int(s) say 'x' i actually find the no of divisors by doing %(mod) for the no in a loop.(See in the code below): Maybe this is also a reason for my code being times out: Any suggestions on this to improved. Many thanks This is actually a problem from http://www.codechef.com/problems/PD13
# include <stdio.h>
# 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 Is your biggesr issue right now.... You just want to find the number of divisors?
My first suggestion will be to cache your result to some degree... but this requires potentially twice the amount of storage you have at the beginning :/.
What you can do is generate a list of prime numbers before hand (using the sieve algorithm). It will be ideal to know the biggest number N in your list and generate all primes till his square root. Now for each number in your list, you want to find his representation as product of factors, ie
n = a1^p1 * a1^p2 *... *an^pn
Then the sum of divisors will be.
((a1^(p1+1) - 1)/(a1 - 1))*((a2^(p2+1) - 1)/(a2-1))*...*((an^(pn+1) - 1)/(an-1))
To understand you have (for n = 8) 1+ 2 + 4 + 8 = 15 = (16 - 1)/(2 - 1)
It will drastically improve the speed but integer factorization (what you are really doing) is really costly...
Edit:
In your link the maximum is 5000000 so you have at most 700 primes
Simple decomposition algorithm
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);
}
EDIT : rather than counting, compute a^(n+1) using primepow = a; primepow = a*primepow;
It will be much cleaner in C++ or java where you have hashmap. At the end
primecount contains the pi values I was talking about above.
Even if it looks scary, you will create the primetable only once. Now this algorithm
run in worst case in O(tablelen) which is O(square root(Nmax)). your initial
loop ran in O(Nmax).
这篇关于在C code +循环优化I / O（输出）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
