External bottom up merge sort too slow

Question

My external sort function works but it is way too slow. I think the bottleneck is the merge function. How can I make it faster. Is there a better merge function I can use for merging into a file using random access file objects and buffers?

private static void merge(String a, String b,
int l, int m, int r)throws FileNotFoundException, IOException
{
    RandomAccessFile a1f = new RandomAccessFile(a,"rw");
    RandomAccessFile b1f = new RandomAccessFile(b,"rw");
    a1f.seek(l*4);
    b1f.seek(l*4);

    for(int i = l; i<m;i++){
        a1f.seek(i*4);
        b1f.seek(i*4);
        int num = a1f.readInt();
        b1f.writeInt(num);
    }

    for(int j=m; j<r; j++){
        a1f.seek((m + r - j - 1)*4);
        b1f.seek(j*4);
        int num = a1f.readInt();
        b1f.writeInt(num);
    }
    int i = l;
    int j = r - 1;

    //for (int i = l; i < m; i++) b[i] = a[i];
    //for (int j = m; j < r; j++) b[j] = a[m + r - j - 1];
    //if (b[j] < b[i]) a[k] = b[j--];
    //else a[k] = b[i++];

    for (int k = l; k < r; k++){
        b1f.seek(j*4);
        int b_j = b1f.readInt();
        b1f.seek(i*4);
        int b_i = b1f.readInt();
        if(b_j<b_i){
            b1f.seek((j--)*4);
            a1f.seek(k*4);
            a1f.writeInt(b1f.readInt());
        }
        else{
            b1f.seek((i++)*4);
            a1f.seek(k*4);
            a1f.writeInt(b1f.readInt());
        }

    }

    a1f.close();
    b1f.close();
}

Answer 1

The most glaring problem in your code here, is that you open and close the file on each call to the merge function. You should instead open it once in the calling function, and pass in the already-open files to the merge method. The open and close operaions are both slow, and should be minimized.

I recommend that you re-work that part of the solution, then re-post as a 'follow on', but then also include the calling part of the function in to your question so that more of the overall structure of your solution can be reviewed.

The variables a, b, l, r, m i, j, and k are also all horrible names... you should rename them to be 'self-documenting'. They should be called what they are. The variable l is particularly problematic because it is so easy to confuse with 1.

I struggle to understand the difference between the a and b files. It appears that you are copying the first chunk of data from the a-file to the b-file, and then merging from two different places in the b file back to the a-file.

I would recommend instead having two read-poitns on the b file and then write back to the A. The extra copy is slowing you down too. There's no need to copy from a-to b if you can jsut swap them...

Answer 2

Your main problem is that you have no buffering. You are going to be swamped with IO costs.

You should read in a byte[] from both positions in the input file, merge into a third byte[] and then write that out to memory. The aim is to chose byte[]s that fit in memory but are large enough to cover the costs of IO calls.

Two input buffers of length 4096 and one output buffer of length 8096 will probably do fine. Then use read(byte[]). You might get smaller reads than the 4096-at-a-time, so be sure to check the return value.

Of course, this is what a buffered stream will do for free. You could just have two buffered streams into the input file and one into the output file. The main problem is j--, which isn't really possible in a buffered stream without throwing away the buffer all the time.

One quick change is that in this:

for (int k = l; k < r; k++){
    // stuff
        a1f.seek(k*4);
        a1f.writeInt(b1f.readInt());
    // stuff
        a1f.seek(k*4);
        a1f.writeInt(b1f.readInt());
}

You are calling seek before every write. You don't need to seek at all; just do

a1f.seek(l*4);
for (int k = l; k < r; k++){
    // stuff
        a1f.writeInt(b1f.readInt());
    // stuff
        a1f.writeInt(b1f.readInt());
}

as the writeInt moves you on for you. Note that not seeking is important when using buffered streams if you want them to stay fast (hence the need for two buffered streams on the input file, rather than 1 with seeking).

Manually buffering with byte[] may seem tiresome but it works.