Reading input all together or in steps?

Question

For many programming quizzes we are given a bunch of input lines and we have to process each input , do some computation and output the result.

My question is what is the best way to optimize the runtime of the solution ?

1. Read all input, store it (in array or something) ,compute result for all of them, finally output it all together.

or 2. Read one input, compute the result, output the result and so on for each input given.

UPDATE

Since no answer was specific I would ask which approach is the best for problems like this:

Quadrant Queries (30 points)

There are N points in the plane. The ith point has coordinates (xi, yi). Perform the following queries:

1) Reflect all points between point i and j both including along the X axis. This query is represented as "X i j"
2) Reflect all points between point i and j both including along the Y axis. This query is represented as "Y i j"
3) Count how many points between point i and j both including lie in each of the 4 quadrants. This query is represented as "C i j"

Input:

The first line contains N, the number of points. N lines follow.
The ith line contains xi and yi separated by a space.
The next line contains Q the number of queries. The next Q lines contain one query each, of one of the above forms.
All indices are 1 indexed.

Output:

Output one line for each query of the type "C i j". The corresponding line contains 4 integers; the number of points having indices in the range [i..j] in the 1st,2nd,3rd and 4th quadrants respectively.

Constraints:

1 <= N <= 100000
1 <= Q <= 1000000

You may assume that no point lies on the X or the Y axis.
All (xi,yi) will fit in a 32-bit signed integer
...

Answer 1

It depends on the problem.

As long as all your data fits in the available physical RAM, there is no reason to pick either possibility for the sake of performance. Reading it all in one go has the advantage that you can jump back and forth in your data without losing performance to I/O, and you can validate all your data before you start processing. Especially with complex data structures (e.g. XML), this approach is much easier than the alternative.

OTOH, processing as you go ('streaming') will make your application more pipe-friendly, that is, if you chain it together with other commands through UNIX pipes (e.g., piping the output of ls into your program, and from there through grep), they will spend less time waiting for each other, and the user will see output right away.

If your input data set is too large to fit in memory at once, you don't have much of a choice - if you try to read it all in one go, you will run out of memory. At best, the system will start swapping, which means slow; at worst, the OS will simply refuse to give your application more memory, or even kill it for misbehaving.

Answer 2

This question isn't really answerable - or rather, the answer is: it depends.

For a short-running task, it doesn't really matter. If the whole thing is done after 1 second, you might as well just go with something that fits the problem well. If the tasks are orthogonal, i.e doesn't depend on each other in any way, you could just read input and compute output directly. However, it's often architecturally sound to do it as described further down in this answer.

For a longer task, typically 10+ seconds, it's very important usability-wise to show feedback, and also validate all input before computation starts. Note that the importance grows exponentially with the execution time.

I've used some tools that has two or more stages. Instead of validating even the syntax for the second stage, it would quit after 10+ minutes with the message 'command line syntax invalid' or something like that. Incredible stuff.

Reading options and input into a proper data structure, validating them and then working on that data gives you a lot for free. It will give you a starting point to start thinking about the problem. It will let you work on the data without worrying about parsing and so on. It will be easy to output timely error messages (since you parse and validate everything at the start).

Even if it is a one-shot thing it's in my opinion definately always worth it to structure the program in a good way.

Answer 3

Processing the data piecemeal will be a hair faster, but for a programming quiz in an academic setting, optimization shouldn't even be on the radar. Most of the reasons why you should do it this way have nothing to do with run time and everything to do with good practice:

• You don't have to re-invent the input-buffering-and-splitting wheel. Most languages include facilities to read line-at-a-time input that have been debugged and made reasonably efficient.
• You don't have to write code to figure out how much input there is and handle storing it before use.
• The amount of input isn't limited by available memory.
• Repeat the first three items for output.
• Your program becomes simpler to write and easier to understand: read, process, write instead of read and store repeatedly, process and store repeatedly, write repeatedly.
• Your program will get along better with other programs when it's part of a pipeline (e.g., generate-input | your-program | process-output). If you hold all of your output until all of the input has been processed, anything downstream has to sit idle until you start producing output, and you've effectively serialized the process (i.e., you've become a bottleneck).

Don't do anything obviously wasteful, but don't let optimization dictate your design, either. There's a place for that, but making it run fast doesn't come until after you've made it run and made it run correctly.