我可以让这段C++代码更快，同时又不会让它变得更复杂吗？
这是我从一个编程问题网站(codechef.com)上解决的一个问题，如果有人不想在尝试之前看到这个解决方案的话。这用测试数据解决了大约5.43秒的问题，其他人用同样的测试数据在0.14秒内解决了同样的问题，但代码复杂得多。谁能指出我代码中性能下降的特定区域？我仍然在学习C++，所以我知道有一百万种方法可以解决这个问题，但我想知道我是否可以通过一些细微的改变来改进我自己的解决方案，而不是重写整个解决方案。或者，如果有任何相对简单的解决方案，在长度上可以与我的类似，但性能会比我的更好，我也很有兴趣看到它们。
请记住，我正在学习C++，所以我的目标是改进我理解的代码，而不仅仅是得到一个完美的解决方案。
谢谢
问题：
这个问题的目的是验证您用来读取输入数据的方法是否足够快，可以处理带有大量输入/输出警告的问题。您应该能够在运行时每秒处理至少2.5MB的输入数据。处理测试数据的时间限制为8秒。
输入以两个正整数n k (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;
}回答 10
Stack Overflow用户
发布于 2010-01-24 08:11:48
我在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;
}哦，它在很大程度上假设输入数据的格式是正确的。
Stack Overflow用户
发布于 2010-01-24 07:01:45
速度不是由计算决定的-程序运行的大部分时间都被i/o消耗掉了。
在第一个scanf之前添加setvbuf调用，以实现显著的改进：
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次读取。进一步增加缓冲区大小，以便只需要一次读取，不太可能比三次读取有显着的性能改进。
Stack Overflow用户
发布于 2010-01-24 06:58:34
尝试将if语句替换为count += ((n%k)==0);。这可能会有一点帮助。
但是我认为你真的需要把你的输入缓冲到临时数组中。一次从输入中读取一个整数的开销很大。如果您可以将数据获取和数据处理分开，编译器也许能够为数学运算生成优化的代码。
https://stackoverflow.com/questions/2125021
复制相似问题
腾讯云开发者
