JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
I/O optimization in C(++) | Reply
I need to read a large amount of integers (say, n integers) formatted using the usual decimal notation. What is the fastest way to do it in C(++)?

I've tried the following:
for (i = 0; i < n; i++) scanf("%d", &a);

But it's a bit slower than:
for (i = 0; i < (n >> 2); i++) scanf("%d%d%d%d", &a, &b, &c, &d);
for (i = 0; i < (n & 3) ; i++) scanf("%d", &a);

and the likes.

Is there any tricks or functions to do this? Cheers.
Re: I/O optimization in C(++) (response to post by ilham) | Reply
man read: http://seth.positivism.org/man.cgi/read

Read the entire input into a char[] and do the parsing on your own, this is probably the fastest approach you can use without using assembler :)
Re: I/O optimization in C(++) (response to post by misof) | Reply
BTW, is getting the entire input into a char[] and then using sscanf() faster than just directly doing scanf()? Of course, it won't be as fast as read(), but is it any faster than scanf() at all? What about using stringstream in C++? (i.e, is it any faster than directly doing cin?)
Re: I/O optimization in C(++) (response to post by aboyner) | Reply
The cin stream is horribly slow. Even in C++ you can use the functions from C.

read+sscanf will probably be slower than just using scanf, not to mention the fact that if the count of the numbers to read is unknown, using scanf you can read them one by one, using sscanf to get them from a string can be tricky (you will probably have to use strtok instead).

The problem with the speed of *scanf is that they are general and handle lots of different issues. If you know that the input is a list of integers, you can live without most of them.

The most convenient way is to define a macro that parses an integer into a variable.

Example:

#include <unistd.h>
#include <iostream>
using namespace std;
 
unsigned char buf[1100000];
 
#define GETNUM(n) { \
  n=0; \
  while (*start>32) { \
    n*=10; n+=*start-'0'; \
    start++; \
  } \
  while (*start>0 && *start<=32) start++; \
}
 
int main() {
  int cnt=read(0,buf,1099000); // I assume that the input is <1MB
  buf[cnt]=0;
 
  unsigned char *start=buf;
  while (*start>0 && *start<=32) start++; // skip leading whitespaces
 
  int sum = 0, tmp;
  while (*start) { GETNUM(tmp); sum += tmp; }
  cout << sum << endl;
}
Re: I/O optimization in C(++) (response to post by aboyner) | Reply
sscanf won't be very useful here. When we call sscanf in a loop we also have to properly increment the buffer pointer (which we cannot do until we do double parsing).

So the following code will fill all the array elements with [1,1,1,...,1] rather than [1,2,3...100];
int a[100];
char buf = "1 2 3 ... 100";
for (int i=0; i<100; ++i) 
    sscanf( buf, "%d", &a[i] );

stringstream would handle this properly. However I am not sure whether it will be faster or not (my guess is that there wont be much difference). But I know that cin is quite slower than scanf.

I believe misof's suggested technique would be the fastest.
Re: I/O optimization in C(++) (response to post by misof) | Reply

The cin stream is horribly slow.

You can speed it up a bit using:
ios_base::sync_with_stdio(0);
Re: I/O optimization in C(++) (response to post by marian) | Reply
... and from a horribly slow input stream you suddenly have... (a short dramatic pause) just a plain slow input stream :)))

But yes, turning out synchronization with stdio can help a bit. You have to be aware of the fact that after you do this, the result of mixing the usage of cin and scanf is undefined. The problem that causes the "horribly" part is that by default cin wants to be compatible with scanf, so that you can use both in your program. The price to pay is that it doesn't do buffered reads, so every time you need to read something from cin, your program has to make a system call.
RSS