8.Project 3 Design§

Implement Quicksort
On disk as a big virtual memory
The disk file is mediated by a buffer pool for better performance
The goal is to minimize disk I/O
Small project: No parser, no world controller, just a main, a sort, and a buffer pool

Disk File

You will use RandomAccessFile to access the disk file
This gives the needed basic functionality (read/write/seek)
This is “unbuffered” (we provide our own buffering via the buffer pool)

Records: Binary Data

Records to sort are 4-byte quantities
2 byte key and 2 byte data field
Don’t grab the wrong bytes, or get them out of order!
Most of the time you simply copy clumps of 4 bytes (swap)
When you need to get the key out:
Best approach is to wrap the 4-byte quantity in a ByteBuffer
Use getShort() to pull out the key value
“ASCII” vs. “Binary” files
The only difference is that the “ASCII” files have keys and values selected so that they happen to print nicely
One side effect is that there are lots of duplicate keys in “ASCII” files

Performance

Most tests have a time limit.
Most of those can easily be met if your buffer pool is implemented correctly.
Only read if the corresponding block is not in memory
Only write when the block is flushed (not every time block is altered)
One or two tests require something more. Two approaches
Improve the algorithm implementation (see OpenDSA)
Code tune: Look especially at wasted creation/destruction of temporary byte arrays

Project Staging

  1. Download starter kit. Submit to Web-CAT. Look at the test case info.
  2. Make the Quicksort work with a stubbed buffer pool that is simply holding the array in memory. Replace Quicksort [] with method calls. Make sure that you read keys and swap records correctly.
  3. Start adding buffer pool functionality until that works completely and efficiently.
  4. Do final optimizations to pass tests.