如何优化打印输出两个整数中较大和较小的差异？ [英] How to optimize printing out the difference between the greater and the lesser of two integers?
问题描述
UVA问题编号。 10055，Hashmat the Brave Warrior ，可能是那里最容易出问题的问题。输入由一系列无符号整数≤2^ 32组成（因此要求使用64位整数......）对于每对，任务是打印出大整数和小整数之间的差异。
UVA Problem no. 10055, Hashmat the Brave Warrior, probably the easiest problem there. The input consists of a series of pairs of unsigned integers ≤ 2^32 (thus mandating the use of 64bit integers…) For each pair the task is to print out the difference between the greater and the lesser integer.
根据统计数据，最快的解决方案在0.01秒以下运行。但是，我所有解决这个问题的尝试通常都是在0.02秒内完成，可能随机偏差为±0.01秒。
According to the statistics, the fastest solutions run in below 0.01 sec. However, all my attempts to solve this typically run in 0.02 sec, with probably random deviations of ± 0.01 sec.
我试过：
#include <cstdint>
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
uint_fast64_t i, j;
while(cin >> i >> j) {
if(i > j)
cout << i-j << '\n';
else
cout << j-i << '\n';
}
}
还有：
#include <cstdlib>
#include <cstdint>
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int_fast64_t i, j;
while(cin >> i >> j) {
cout << abs(i-j) << '\n';
}
}
还有：
#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
uint_fast64_t i, j;
while(cin >> i >> j) {
cout << max(i,j)-min(i,j) << '\n';
}
}
所有结果相同。
我也尝试使用 printf（） / scanf（）而不是 cin / cout ，仍然有相同的结果（此外，我的基准显示 cin / cout 前面有 cin.tie（nullptr）甚至可以比 printf（）/ scanf（）快一点 - 至少除非有一些方法可以优化 cstdio的性能我不知道）。
I also tried using printf()/scanf() instead of cin/cout, still with same results (besides, my benchmarks were showing that cin/cout preceded by cin.tie(nullptr) can be even a little faster than printf()/scanf() – at least unless there are some ways to optimize the performance of cstdio I’m not aware of).
有没有办法优化它到低于0.01秒，或者我应该假设那些已经达到这个时间的人要么是非常幸运，要么是骗子打印出对法官输入的预先计算答案？
Is there any way to optimize this down to below 0.01 sec., or should I assume that guys who’ve achieved this time are either extremely lucky or cheaters printing out a precomputed answer to the judge’s input?
程序使用 C ++ 11进行编译5.3.0 - 带有选项的GNU C ++编译器：-lm -lcrypt -O2 -std = c ++ 11 -pipe -DONLINE_JUDGE 。
编辑：这是我尝试结合@Sorin和@MSalters的建议：
This is my attempt to combine the advices of @Sorin and @MSalters:
#include <stdio.h>
#include <stdint.h>
unsigned long long divisors[] = {
1000000000,
1000000000,
1000000000,
1000000000,
100000000,
100000000,
100000000,
10000000,
10000000,
10000000,
1000000,
1000000,
1000000,
1000000,
100000,
100000,
100000,
10000,
10000,
10000,
1000,
1000,
1000,
1000,
100,
100,
100,
10,
10,
10,
1,
1,
1
};
int main()
{
unsigned long long int i, j, res;
unsigned char inbuff[2500000]; /* To be certain there's no overflow here */
unsigned char *in = inbuff;
char outbuff[2500000]; /* To be certain there's no overflow here */
char *out = outbuff;
int c = 0;
while(1) {
i = j = 0;
inbuff[fread(inbuff, 1, 2500000, stdin)] = '\0';
/* Skip whitespace before first number and check if end of input */
do {
c = *(in++);
} while(c != '\0' && !(c >= '0' && c <= '9'));
/* If end of input, print answer and return */
if(c == '\0') {
*(--out) = '\0';
puts(outbuff);
return 0;
}
/* Read first integer */
do {
i = 10 * i + (c - '0');
c = *(in++);
} while(c >= '0' && c <= '9');
/* Skip whitespace between first and second integer */
do {
c = *(in++);
} while(!(c >= '0' && c <= '9'));
/* Read second integer */
do {
j = 10 * j + (c - '0');
c = *(in++);
} while(c >= '0' && c <= '9');
if(i > j)
res = i-j;
else
res = j-i;
/* Buffer answer */
if(res == 0) {
*(out++) = '0';
} else {
unsigned long long divisor = divisors[__builtin_clzll(res)-31];
/* Skip trailing 0 */
if(res < divisor) {
divisor /= 10;
}
/* Buffer digits */
while(divisor != 0) {
unsigned long long digit = res / divisor;
*(out++) = digit + '0';
res -= divisor * digit;
divisor /= 10;
}
}
*(out++) = '\n';
}
}
仍为0.02秒。
推荐答案
我会尝试消除IO操作。
读取一个数据块（尽可能大）。
计算输出，将它们写入另一个字符串，然后将该字符串写出来。
I would try to eliminate IO operations. Read one block of data (as big as you can). Compute the outputs, write them to another string then write that string out.
你可以使用sscanf或stringstream来读取/写入你的内存块。
You sscanf or stringstream equivalents to read/write from your memory blocks.
IO通常需要通过内核，所以你可能会稍微松开CPU。还有一些成本（时间）与之相关。它虽小，但你试图在不到10毫秒的时间内运行。
IO usually needs to go through the kernel so there's a small chance that you would loose the CPU for a bit. There's also some cost(time) associated with it. It's small but you are trying to run in less than 10ms.
这篇关于如何优化打印输出两个整数中较大和较小的差异？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
