在 C 代码中优化 I/O(输出)+ 一个循环 [英] Optimizing I/O(Output) in C code + a loop

问题描述

我有一个代码，它从标准输入读取大约 (10^5) 个整数，然后在执行 ## 后我将它们输出到标准输出.我已经使用setvbuf"处理了 INPUT 部分 &使用fgets_unlocked()"读取行，然后解析它们以获得所需的整数.我有 2 个无法解决的问题:

1.) 因为我在 stdout 上打印 int(s) 500 万，所以它花费了很多时间:有什么办法可以减少这种情况(我尝试使用 fwrite()，但由于原因，o/p 打印出不可打印的字符)使用 fread 读入 int 缓冲区)

2.) 在解析 int(s) 的输入后说 'x' 我实际上通过对循环中的 no 执行 %(mod) 来找到除数的编号.(见下面的代码):也许这个也是我的代码超时的一个原因:对此有任何改进的建议.非常感谢这其实是http://www.codechef.com/problems/PD13

# include # 定义尺寸 32*1024字符缓冲区[大小];主要(无效){int i=0,chk =0;无符号整数 j =0 ,div =0;int a =0,​​num =0;字符 ch;setvbuf(stdin,(char*)NULL,_IOFBF,0);scanf("%d",&chk);while(getchar_unlocked() != '
');while((a = fread_unlocked(buf,1,SIZE,stdin)) > 0){for(i=0;i

解决方案

//Prob 2 Is your biggesr issue now.... 你只想找到除数的个数?

我的第一个建议是在某种程度上缓存你的结果......但这可能需要两倍于开始时的存储量:/.

您可以做的是事先生成素数列表(使用筛分算法).最好知道列表中最大的数 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 )位置++；if(pos == tablelen)返回while(number % primetable[pos] ==0 ){number = number/primetable[pos];素数[位置]++；}//号码已修改//懒得写循环了，所以递归调用primedecomp(数字，primetable，primecount，pos+1，tablelen)；}

EDIT :而不是计数，使用 primepow = a 计算 a^(n+1);primepow = a*primepow;

在 C++ 或 Java 中使用 hashmap 会更清晰.在最后primecount 包含我上面所说的 pi 值.

即使看起来很吓人，您也只会创建一次 primetable.现在这个算法在 O(tablelen) 的最坏情况下运行，即 O(square root(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() != '
');
while((a = fread_unlocked(buf,1,SIZE,stdin)) >0)
{
    for(i=0;i<a;i++)
    {
        if(buf[i] != '
')
        {
            num = (buf[i] - '0')+(10*num);
        }
        else
        if(buf[i] == '
')
        {   
            div = 1;
            for(j=2;j<=(num/2);j++)
            {
                if((num%j) == 0)    // Prob 2
                {
                    div +=j;
                }
            }
            num = 0;
            printf("%d
",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 代码中优化 I/O(输出)+ 一个循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！