How to print on screen 2^20 lines of integers in c++ quickly (under 1 second)?

Question

I have to print on screen 2^20 lines of integers under 1 second printf is not quick enough for there , are there any other easy to use alternatives for fast output?

Each line contains only 1 integer.

I require it for a competitive programming problem whose source code I have to submit to the judge.

Answer 1

There is putchar and puts that you can try out.

If timing speed of the program is all that is required, you can print out to /dev/null (unix).

Answer 2

That's 4 MB of binary integer data. 5 MB if you count the newlines. If you like the data in binary, just write it out to wherever as binary values.

I'll assume you need formatting as well. The best way to do this then is to allocate a "huge" string which is big enough to handle everything, which in this case is 10+1 chars per integer. This means 11 MB. That is a reasonable memory requirement and definitely allocatable on a normal desktop system. Then, use sprintf to write the integer values out to the string:

#include <cstdio>
#include <iostream>
#include <string>

int main()
{
  std::string buffer(11534336, '\0');
  for (int i = 0; i < 1048576; ++i)
  {
    std::sprintf(&buffer[i * (10 + 1)], // take into account the newline
                 "%010d\n", i);
  }

  std::cout << buffer;
}

Note the effective formatting operation is very fast. The physical output to the console window will take some time on Windows, this is inherent to the Windows console and cannot be remedied. As an example, Coliru times out after 17872 entries, which I believe is 5 seconds. So unfortunately, printing to the screen at this speed is impossible using Standard C(++). You might be able to do it faster when you do everything on the GPU directly and display a surface/texture/image you create, but that can hardly be the point of the exercise.

Answer 3

There are about three major bottlenecks in printf

• parsing algorithm (must handle all kind of inputs/outputs)
• base conversions (typically not optimized for your particular purpose)
• I/O

The cure is

• process multiple entries at time
• process file i/o in blocks
• finetune the base conversion for your specific problem

If your numbers are in order, you can have considerable increase of speed by processing multiple integers at a time; e.g.

char strings[10*6];
memcpy(strings, "10000\n10001\n10002\n10003\n10004\n", 30);
memcpy(strings + 30, "10005\n10006\n10007\n10008\n10009\n", 30);

fwrite(strings, 60, 1, stdout);

After each block of 10 integers are printed, one has to update the common part of the string, which can be done even with 1 x sprintf + 9x memcpy.

Answer 4

Expanding on what stefaanv mentioned about using putchar, this is a somewhat ugly C-style hack that should do the job fairly quickly. It makes use of the fact that ASCII decimal digits are 0x30 to 0x39:

inline void print_int(int val)
{
   char chars[10];   // Max int = 2147483647
   int digits = 0;
   if (val < 0)
   {
      putchar('-');
      val = -val;
   }

   do
   {
      chars[digits++] = ((val % 10) + 0x30);
      val /= 10;
   }while (val && digits < 10);

   while (digits>0)
   {
      putchar(chars[--digits]);
   }
   putchar('\n');
}