Noble_Mushtak's blog

By Noble_Mushtak, history, 3 years ago,

Usually, I hear people saying that std::cin and std::cout is a relatively slow form of input while scanf and printf is a faster form of input which should be sufficient for all problems. However, sometimes I wonder if there are any problems where scanf and printf would be too slow.

For example, look at the problem 1181D — Irrigation. This problem asks us to read in 500,000 numbers, each of which could be as large as 500,000, and then asks us to read in 500,000 more numbers, each of which could be as large as $10^{18}$. Clearly, this is a lot of input/output, so users should use scanf and printf over std::cin and std::cout. However, even when I used scanf and printf, my solution ran in 2355 ms, barely under the time limit of 2.5 seconds. On the other hand, when I wrote my code using an I/O library I wrote myself, which uses fread and fwrite to read/write 32768 bytes at a time, my improved solution ran in 592 ms, almost 4 times faster than the original solution.

Since my code barely ran under time using scanf and printf, I wonder if there are any CodeForces problems where using scanf and printf will inevitably lead to a Time Limit Exceeded error and users must use some other I/O method like I did. Has anyone else encountered a problem where scanf and printf just weren't quite fast enough? Moreover, has anyone else built a custom I/O library for competitive programming like I did? If anyone has knows how to do input/output faster than fread and fwrite, I would love to hear about it.

• +5

| Write comment?
 » 3 years ago, # |   0 Auto comment: topic has been updated by Noble_Mushtak (previous revision, new revision, compare).
 » 3 years ago, # |   +12 don't submit using slow C11your same code in C++17
•  » » 3 years ago, # ^ |   0 Wow, this is very surprising, but I think you are right. I also tested this with Tolik and His Uncle, and my C11 solution received Time Limit Exceeded error, but my C++11 solution received Accepted.
 » 3 years ago, # |   0 I had I/O issues with https://codeforces.com/problemset/problem/321/E. My solution was to read line by line, but I think that shouldn't be necessary.
 » 3 years ago, # |   +3 There is an interesting function called mmap()useful links to understand it:https://stackoverflow.com/questions/5588605/mmap-vs-readhttps://stackoverflow.com/questions/9817233/why-mmap-is-faster-than-sequential-iohttps://lemire.me/blog/2012/06/26/which-is-fastest-read-fread-ifstream-or-mmap/https://eklausmeier.wordpress.com/2016/02/03/performance-comparison-mmap-versus-read-versus-fread/It is faster than fread(); however, I don't recommend using it since you are not allowed to use it on most Online Judges.
•  » » 3 years ago, # ^ |   0 But only allowed in Linux/Ubuntu, the CodeForces' tester is under Windows
 » 3 years ago, # |   0 When testing the problems, I don't think they use your I/O library or any advanced one so I guess you should always be fine with printf/scanf
 » 3 years ago, # |   0 I suppose you might know that C++ IO with sync turned off (ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);) is actually faster than using scanf/printf. I never had some serious issues using this. As [user:tuwuna]have mentioned, compiler with higher version of language standard actually makes IO significantly faster. So generally in high enough version, those IO must not be an issue.(input speed) (output speed)Here is a blog in Korean online judge community where various input/output methods for various languages are tested by reading and writing 10m integers. Text itself is written in Korean, but it seems understandable with google translation.There is a mmap() which is faster than fread, but I don't think it is very useful, since it is not really that much faster. Especially, you should consider that there will almost never be 10m input. JAVA or other languages will SUFFER since they don't even have method comparable to fread. As you see, JAVA takes more than half a second reading 10m input.