This page covers some of the lessons learned when writing solutions in C++ for programming contest problems. Many of these problems require a substantial number of integer values to be read in and this can contribute significantly to the over execution time. This page covers some of the methods that can be used to reduce this time penalty.
To evaluate different methods of reading integer data, a large text input file of 100 million integer numbers was used. These numbers are read using the function below to compute a final sum (simply to keep the code from being optimized away):
1) C++ STD::CIN
The most standard approach to reading numbers is to use the C++ standard library. This is simple and easy to use:
2) C++ STD::CIN (Untied and Unsync streams)
Using the approach above, you can increase performance if you:
- Disable the synchronization between C and C++ standard streams
- Untie the cin and cout streams
For contests, this is safe to do as long as you don't mix C and C++ stream IO:
3) C Scanf
This is the old C standard way of reading in data:
4) Dedicated Integer Reader
This function is only useful when all the input is integer numbers (it cannot be used with any other input methods):
5) Raw IO
The most basic comparison is the raw reading from a file. This reads the entire input file into memory one block at a time without the conversion to numbers.
For all timing results, the test was run four times with the slowest result discarded and the remaining the results averaged.
The testing system was a Windows 10 64-bit machine with an intel i5-2500K (overclocked to 4.3Ghz) and 16GB of RAM.
|#||Method||Execution Time||Numbers Read per Second|
|1||C++ STD::CIN||61.14 seconds||1,635,455|
|2||C++ STD::CIN (Untied and Unsync streams)||51.45 seconds||1,943,322|
|3||C Scanf||24.76 seconds||4,037,397|
|4||Dedicated Integer Reader||1.89 seconds||52,678,897|
|5||Raw IO||0.64 seconds||-|
On a contest with a 3 second budget for solving the problem you have to be very careful what time you spend doing IO. My recommendation is that the IO take no more than 5% of your overall budget which means that it has to be completed in less than 150 milliseconds. Here are some recent contests and how they would fare on their largest test case:
|Contest||Max Integers||1) CIN||2) CIN||3) Scanf||4) Reader|
|Through A Maze Darkly||600,003||367 ms||316 ms||145 ms||11 ms|
|Stupendous Bowties||200,202||84 ms||73 ms||33 ms||5 ms|
- Always use Scanf since it is simple to implement and will keep the IO costs down
- In case of large datasets or if your solution is close to the edge - use the reader.