我可以让这段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;
}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;
}哦，它在很大程度上假设输入数据的格式是正确的。
https://stackoverflow.com/questions/2125021
复制相似问题
腾讯云开发者
