How to delete lines from input file?

[spidrw]

I'm writing this program to implement a two phase multi-way merge sort.
It works by splitting the data to be sorted into temporary sorted
lists (output files) equal in size to a memory constraint that is
passed in when the program is run. What I've got to do now is actually
merge the lists into one final output. The trick is that this is
supposed to save disk I/Os. What happens is I read the smallest
element from each temporary file into an array. From that array, the
smallest goes into the final output, and that element is then replaced
by the next element from the same list.

I feel like what I need to do is delete a number from one of the
temporary when it's read into the array. Then all I have to do is read
the first line from the same list to get the next number into the
merging array. Any suggestions on how to do this?

I'm using SDK 1.4.2 and the input/output files are binary, so I'm using
DataInput/OutputStream to do this.

Thanks,
Andrew Weber

 

[Lee Fesperman]

I'm writing this program to implement a two phase multi-way merge sort.
It works by splitting the data to be sorted into temporary sorted
lists (output files) equal in size to a memory constraint that is
passed in when the program is run. What I've got to do now is actually
merge the lists into one final output. The trick is that this is
supposed to save disk I/Os. What happens is I read the smallest
element from each temporary file into an array. From that array, the
smallest goes into the final output, and that element is then replaced
by the next element from the same list.

I feel like what I need to do is delete a number from one of the
temporary when it's read into the array. Then all I have to do is read
the first line from the same list to get the next number into the
merging array. Any suggestions on how to do this?

You won't be able to. You definitely can't delete anything from the front of the file.
You can delete from the end of a file, effectively truncating the file (using
RandomAccessFile), however that is probably not the best choice to avoid disk I/Os.

Why would 'deleting' save disk I/Os? Are you scanning the previous values to get the
next values from the temporaries? That's not a very good idea. Either use a skip
operation which would avoid some I/O or just keep all the temporaries open and keep
advancing through them.

 

[spidrw]

Lee,
The problem is that I really can't keep the files open. I thought
about keeping an array of input readers, but that goes beyond my memory
constraint. Basically, the only thing I can have in memory is an array
of doubles. I can have a couple of counters in memory if necessary
though. My other thought was to keep a count of which record I was on
(in each temporary file in an array), and just readLine() that many
times to get to the next one, but then I've got a lot of overhead
because I'm doing too many reads.

If this sounds odd, it's because it's an assignment of course.

Thanks.

 

[Lee Fesperman]

Lee,
The problem is that I really can't keep the files open. I thought
about keeping an array of input readers, but that goes beyond my memory
constraint. Basically, the only thing I can have in memory is an array
of doubles. I can have a couple of counters in memory if necessary
though. My other thought was to keep a count of which record I was on
(in each temporary file in an array), and just readLine() that many
times to get to the next one, but then I've got a lot of overhead
because I'm doing too many reads.

If this sounds odd, it's because it's an assignment of course.

Since this is homework, I shouldn't lead you by the nose, so I'll try to keep it to some
clues. It seems you're reading binary and using readDouble() in DataInputStream.
readLine() doesn't really apply in this case. As I suggested, you could 'skip' to the
next entries. See if you can figure out how to do this in relation to readDouble() in
DataInputStream.

 

[spidrw]

I'll check that out. And yes, I'm using readDouble() not readLine.

Thanks!