I know that if a computation takes linear or linearithmic time based on the size of the input, that’s good, and if it takes quadratic time, then that’s not so good.
However, what about memory usage? Suppose a program takes a file as input and does something with that file. Is it okay for the memory usage to be linear in the size of the file or should it be constant?
3
If you’re reading a file, it’s pretty hard to it to be a constant. In general, these rules aren’t so strict. If your data is always really small, having quadratic (+) computation/memory usage isn’t really that bad. If it’s good enough for your situation, it’s fast enough to not need refactoring.
In general though, you want polynomial time computation/memory because anything above that gets way too slow with even relatively small inputs.
1
If memory usage increase is linear then there’s always the possibiliy of running out of memory, if the input is very very large. Then you have to code around that either by swapping some pieces of data to disc (though you might be able to rely on the operating system to do this for you, but either way it will slow down processing time), or changing the way you process data. What you really have to ask is:
Is it likely that my input will be so large that the amount of memory necessary to process it will exceed the available memory?
There might be a way to calculate this before you begin processing, it probably depends on the specific problem you’re working on.
…or buy more memory. 😉
I would distinguish two main categories of procedures / approaches:
- A procedure loads some data into main memory, performs some operation, and saves the result to the disk.
- A procedure runs as a filter reading a data stream and producing a new data stream as output, which is saved on the fly. When the end of the input stream is reached, the procedure terminates.
In the first case (e.g. reading, editing, saving a document), memory usage can be linear (or even quadratic or more) in the size of the input data: the largest size for the input data will be determined by the amount of available memory. You can use this approach when your input data is small enough wrt the available memory.
In the seconds case (e.g. filtering relevant information from a large log file) even a linear memory usage can be undesirable, since it is easy to run out of memory as soon as the input stream is large enough. For problems of category 2 I would only accept a solution that can run in constant (stack and heap) memory.
Whether your solution falls into category 1 or 2 can depend on the (expected) size of the data. Take for example sorting. If you need to sort 100 MB of strings you can just load the data into main memory and use an in-memory algorithm. On the other hand, if you need to sort 1 TB of data, you should rather consider an algorithm that uses constant main memory (like some implementations of merge sort).
The problem of file input possibly exceeding available memory is an old, well known, and basically solved issue. This is what a buffered file reader is all about. Your buffer size is the maximum amount of memory your file will take up at a time. The idea is to read the input up to the maximum buffer size, process that chunk, then read in the next chunk. This makes for constant memory usage (at worst).
What if your process requires more than what’s available in a chunk? There are a bunch of algorithms out there for dealing with that sort of thing too. Worst case, you may need a larger buffer and possibly more memory, but it still should have a constant maximum.