I am coding for various programming olympiads and am trying to improve time efficiency. I'm looking for the fastest way to get input, using the gcc compiler without any external library.
I've previously used cin and cout, but found that scanf and printf are much faster. Is there an even faster way? I don't care of space complexity that much, I rather prefer better time.
This method is known as Fast I/O or Fast Input/Output technique. As we know C++ is a backward compatible language which means it supports most of the C programming language syntax. In C programming, we use printf () and scanf () function for output and input respectively.
Generally, buffered input will be the fastest. The less frequently you have to flush your input buffer, the faster the input will be. For a full and very informative discussion, see this question.
In C++, we can take input and output using both scanf () & cin and printf () & cout respectively. It is recommended by many to use scanf () and printf () instead of cin and cout to achieve fast Input and output process, but we can achieve the same using cin and cout too using these 2 lines inside the main function :
Declare a variable with appropriate data type, take input and perform operations. In competitive programming it is important to read input as fast as possible and operations has to be performed faster there performance matters. We can make the fast one even faster. How…?
That streams are always slower than the C-API functions is a pretty common misconception because by default, they synchronize with the C-layer. So yeah, that's a feature, not a bug.
Without sacrificing type safety (and readability, depending on your taste), you possibly gain performance with streams by using:
std::ios_base::sync_with_stdio (false);
A little indicator:
#include <cstdio>
#include <iostream>
template <typename Test>
void test (Test t)
{
const clock_t begin = clock();
t();
const clock_t end = clock();
std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n";
}
void std_io() {
std::string line;
unsigned dependency_var = 0;
while (!feof (stdin)) {
int c;
line.clear();
while (EOF != (c = fgetc(stdin)) && c!='\n')
line.push_back (c);
dependency_var += line.size();
}
std::cout << dependency_var << '\n';
}
void synced() {
std::ios_base::sync_with_stdio (true);
std::string line;
unsigned dependency_var = 0;
while (getline (std::cin, line)) {
dependency_var += line.size();
}
std::cout << dependency_var << '\n';
}
void unsynced() {
std::ios_base::sync_with_stdio (false);
std::string line;
unsigned dependency_var = 0;
while (getline (std::cin, line)) {
dependency_var += line.size();
}
std::cout << dependency_var << '\n';
}
void usage() { std::cout << "one of (synced|unsynced|stdio), pls\n"; }
int main (int argc, char *argv[]) {
if (argc < 2) { usage(); return 1; }
if (std::string(argv[1]) == "synced") test (synced);
else if (std::string(argv[1]) == "unsynced") test (unsynced);
else if (std::string(argv[1]) == "stdio") test (std_io);
else { usage(); return 1; }
return 0;
}
With g++ -O3, and a big text file:
cat testfile | ./a.out stdio
...
0.34 sec
cat testfile | ./a.out synced
...
1.31 sec
cat testfile | ./a.out unsynced
...
0.08 sec
How this applies to your case depends. Modify this toy-benchmark, add more tests, and compare e.g. something like std::cin >> a >> b >> c
with scanf ("%d %d %d", &a, &b, &c);
. I guarantee, with optimizations (i.e. without being in debug mode), performance differences will be subtle.
If that does not saturate your needs, you might try other approaches, e.g. reading the whole file first (may or may not bring more performance) or memory maps (which is a non-portable solution, but the big desktops have them).
#include <cstdio>
#include <iostream>
template <typename Test>
void test (Test t)
{
const clock_t begin = clock();
t();
const clock_t end = clock();
std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n";
}
void scanf_() {
char x,y,c;
unsigned dependency_var = 0;
while (!feof (stdin)) {
scanf ("%c%c%c", &x, &y, &c);
dependency_var += x + y + c;
}
std::cout << dependency_var << '\n';
}
void unsynced() {
std::ios_base::sync_with_stdio (false);
char x,y,c;
unsigned dependency_var = 0;
while (std::cin) {
std::cin >> x >> y >> c;
dependency_var += x + y + c;
}
std::cout << dependency_var << '\n';
}
void usage() { std::cout << "one of (scanf|unsynced), pls\n"; }
int main (int argc, char *argv[]) {
if (argc < 2) { usage(); return 1; }
if (std::string(argv[1]) == "scanf") test (scanf_);
else if (std::string(argv[1]) == "unsynced") test (unsynced);
else { usage(); return 1; }
return 0;
}
Results:
scanf: 0.63 sec
unsynced stream: 0.41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With