Efficient way to separate text file to header, tail lines and the leftover in between

Question

I'm looking for a more efficient algorithm for the following problem:

The input of the algorithm is a text file and two non-negative integer numbers - the number of headers and the number of tails.

Execution of the algorithm should provide two output files. Output file 1 should have all the header lines followed by the tail lines. Output file 2 should have all the lines between the headers and the tails - if there is any.

e.g.:

Input file content:

1
2
3

Number of headers: 1 Number of tails: 1

Then after the execution the expected content of the outptut file 1 is

1
3

while the content of output file 2 is

2

One solution reads the input file once, and after finding the header lines (and writing those to output file 1), in a fixed size (size of tails) of queue data structure maintains the possible tail lines. When reading a new line it puts it into the queue. If the queue would be full then it removes the first line from the queue and writes it to output file 2. If it reached the EOF, it writes the content of the queue into the output file 1.

This implementation has an efficient time complexity, but the space complexity is based on the number of tails. If the number of tails is large it can end up reading a large file into the memory.

To avoid this I thought about another algorithm which reads the input file twice. First it counts the number of lines. And in the second iteration based on the number of lines, it can figure out where the tail lines are starting. With this we can avoid reading a large file which perhaps would not fit into the memory.

Is there any algorithm which could be used to iterate through the input file only once, but at the same time avoid filling up the memory with a large file?

(I'm using Java for the implementation with BufferedReader and simple text file)

Answer 1

The head lines are essentially a non-problem, so I don't see a need to discuss it.

If you want your program to be able to handle streaming data, there's no way around buffering. But if you only want to be able to read true files, you can position to the end minus some buffer size, and read a buffer to count line endings in the buffer. If there are not sufficient lines in the buffer, read more buffers until you found the required number of lines. This can be done in linear time with constant memory.

You should also think about whether the requirements are reasonable. A number of tail lines that would cause memory problems with your simple buffering algorithm is probably nonsense anyway.