这是一个我从编程问题网站解决的问题(codechef.com,以防任何人在尝试自己之前不想看到这个解决方案).这使用测试数据在大约5.43秒内解决了问题,其他人在0.14秒内使用相同的测试数据解决了同样的问题,但代码复杂得多.任何人都可以指出我的代码中我失去性能的特定区域吗？我还在学习C++所以我知道有一百万种方法可以解决这个问题,但是我想知道我是否可以通过一些微妙的改变来改进我自己的解决方案,而不是重写整个事情.或者,如果有任何相对简单的解决方案,其长度相当,但性能会比我的更好,我也有兴趣看到它们.
请记住我正在学习C++,所以我的目标是改进我理解的代码,而不仅仅是给出一个完美的解决方案.
谢谢
此问题的目的是验证您用于读取输入数据的方法是否足够快,以处理标记有巨大输入/输出警告的问题.您应该能够在运行时每秒处理至少2.5MB的输入数据.处理测试数据的时间限制为8秒.
输入以两个正整数nk(n,k <= 10 ^ 7)开始.接下来的n行输入包含一个正整数ti,每个整数不大于10 ^ 9.产量
写一个整数来输出,表示有多少整数ti可以被k整除.例
7 3
1
51
966369
7
9
999996
11
4
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
//n is number of integers to perform calculation on
//k is the divisor
//inputnum is the number to be divided by k
//total is the total number of inputnums divisible by k
int n,k,inputnum,total;
//initialize total to zero
total=0;
//read in n and k from stdin
scanf("%i%i",&n,&k);
//loop n times and if k divides into n, increment total
for (n; n>0; n--)
{
scanf("%i",&inputnum);
if(inputnum % k==0) total += 1;
}
//output value of total
printf("%i",total);
return 0;
}
wal*_*lyk 12
速度不是由计算决定的 - 程序运行所用的大部分时间都是由i/o消耗的.
在第一次调用之前添加setvbuf调用scanf以获得显着改进:
setvbuf(stdin, NULL, _IOFBF, 32768);
setvbuf(stdout, NULL, _IOFBF, 32768);
- 编辑 -
所谓的魔术数字是新的缓冲区大小.默认情况下,FILE使用512字节的缓冲区.增加此大小会减少C++运行时库对操作系统发出读取或写入调用的次数,这是算法中最昂贵的操作.
通过将缓冲区大小保持为512的倍数,可以消除缓冲区碎片.大小是应该1024*10还是1024*1024取决于它要运行的系统.对于16位系统,大于32K或64K的缓冲区大小通常会导致分配缓冲区的困难,并且可能会对其进行管理.对于任何更大的系统,根据可用内存以及它将与之竞争的其他内容,使其尽可能大.
缺少任何已知的内存争用,请选择大小与关联文件大小相同的缓冲区大小.也就是说,如果输入文件是250K,则将其用作缓冲区大小.随着缓冲区大小的增加,肯定会有递减的回报.对于250K示例,100K缓冲区需要三次读取,而默认512字节缓冲区需要500次读取.进一步增加缓冲区大小,因此只需要一次读取就不可能在三次读取时显着提高性能.
我在28311552行输入上测试了以下内容.它比你的代码快10倍.它的作用是立即读取一个大块,然后完成下一个换行符.这里的目标是降低I/O成本,因为scanf()一次读取一个字符.即使使用stdio,缓冲区也可能太小.
块准备好后,我直接在内存中解析数字.
这不是最优雅的代码,我可能会有一些边缘情况,但它足以让你采用更快的方法.
以下是时间安排(没有优化器,我的解决方案只比原始参考快6-7倍)
[xavier:~/tmp] dalke% g++ -O3 my_solution.cpp
[xavier:~/tmp] dalke% time ./a.out < c.dat
15728647
0.284u 0.057s 0:00.39 84.6% 0+0k 0+1io 0pf+0w
[xavier:~/tmp] dalke% g++ -O3 your_solution.cpp
[xavier:~/tmp] dalke% time ./a.out < c.dat
15728647
3.585u 0.087s 0:03.72 98.3% 0+0k 0+0io 0pf+0w
这是代码.
#include <iostream>
#include <stdio.h>
using namespace std;
const int BUFFER_SIZE=400000;
const int EXTRA=30; // well over the size of an integer
void read_to_newline(char *buffer) {
int c;
while (1) {
c = getc_unlocked(stdin);
if (c == '\n' || c == EOF) {
*buffer = '\0';
return;
}
*buffer++ = c;
}
}
int main() {
char buffer[BUFFER_SIZE+EXTRA];
char *end_buffer;
char *startptr, *endptr;
//n is number of integers to perform calculation on
//k is the divisor
//inputnum is the number to be divided by k
//total is the total number of inputnums divisible by k
int n,k,inputnum,total,nbytes;
//initialize total to zero
total=0;
//read in n and k from stdin
read_to_newline(buffer);
sscanf(buffer, "%i%i",&n,&k);
while (1) {
// Read a large block of values
// There should be one integer per line, with nothing else.
// This might truncate an integer!
nbytes = fread(buffer, 1, BUFFER_SIZE, stdin);
if (nbytes == 0) {
cerr << "Reached end of file too early" << endl;
break;
}
// Make sure I read to the next newline.
read_to_newline(buffer+nbytes);
startptr = buffer;
while (n>0) {
inputnum = 0;
// I had used strtol but that was too slow
// inputnum = strtol(startptr, &endptr, 10);
// Instead, parse the integers myself.
endptr = startptr;
while (*endptr >= '0') {
inputnum = inputnum * 10 + *endptr - '0';
endptr++;
}
// *endptr might be a '\n' or '\0'
// Might occur with the last field
if (startptr == endptr) {
break;
}
// skip the newline; go to the
// first digit of the next number.
if (*endptr == '\n') {
endptr++;
}
// Test if this is a factor
if (inputnum % k==0) total += 1;
// Advance to the next number
startptr = endptr;
// Reduce the count by one
n--;
}
// Either we are done, or we need new data
if (n==0) {
break;
}
}
// output value of total
printf("%i\n",total);
return 0;
}
哦,它非常假设输入数据格式正确.