large inputs in c??

can anyone please guide me that how can i efficiently handle large inputs in c
and what is meaning of “You are expected to be able to process at least 2.5MB of input data per second at runtime.”

problem: Enormous Input Test

1 Like

The main point of this problem is to check how well you’re program can handle large number of inputs, which according to the question can be up to 10^7 integers!

Ok, I’ll try explaining the 2.5mb/s part although I’m not sure if it’s right… (feel free to correct me if there some mistake!!)

Lets assume the size of one integer to be around ~ 2 bytes

So 10^7 ints(numbers) will take ~ 2x10^7 bytes of memory

But 1MB = 1048576 bytes

So, 2x10^7bytes = 2x10^7 / 1048576 MB = ~ 19MB

Now we can a time limit of 8s for this program, so 19/8 = ~ 2.375 MB of data should be read in a second!

In C/C++ , scanf/printf functions will be enough to solve this problem but the execution time will be of the range 5-6s! If you want to make you’re program run faster, you need to compose you’re own input function, one of which is by using getchar_unlocked() function explain over here : http://programmerthing.blogspot.in/2011/06/spoj-450-enormous-input-test.html

3 Likes

thanks alot for your answer i have also heard about fread somewhere i googled but cant find much about the difference between fread and scanf
can you please help me over this
and i am sorry for replying late

fread is used for reading a file, typically you don’t need this in contest programming…

@back2basics your calculations are not correct (hope mine are (-:open_mouth: ). First of all it’s about input size, so memory for integer is not really important (and it’s 32 bits = 4 bytes). Important is that there are 10^7 numbers in input file, each of them is 10^9 max, so if there are only 1000.000.000s, that 11 characters for number (including ‘\n’), so it’s 11*10^7 bytes (1 char = 1 byte), so in max file you’d need to read 13MB per second, but as described in problem statement they expect you to read just 2.5MB per second

2 Likes

@betlista should i or not use fread in this case i have read somewhere that fread is much faster than scanf to read user inputs if not fread than what else should i use to read user inputs faster??

@nishant_25: I’m not C/C++ guru and especially not in performance tunning in C/C++. It is fact, that you can use scanf and your code won’t get TLE. Maybe someone else will help with performance.

thanks @bettista for helping me
:slight_smile:

meanwhile I found an example how to use fread, you can try :wink:

http://discussed.codechef.com/showthread.php?p=4446

thanks @bettista