8.1. Project 3 Design¶
8.1.1. Project 3 Design¶
8.1.1.1. Project 3 Design¶
Implement QuicksortOn disk as a big virtual memoryThe disk file is mediated by a buffer pool for better performanceThe goal is to minimize disk I/OSmall project: No parser, no world controller, just a main, a sort, and a buffer pool
8.1.1.2. Disk File¶
You will use RandomAccessFile to access the disk fileThis gives the needed basic functionality (read/write/seek)This is “unbuffered” (we provide our own buffering via the buffer pool)
8.1.1.3. Records: Binary Data¶
Records to sort are 4-byte quantities2 byte key and 2 byte data fieldDon’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 ByteBufferUse getShort() to pull out the key value“ASCII” vs. “Binary” filesThe only difference is that the “ASCII” files have keys and values selected so that they happen to print nicelyOne side effect is that there are lots of duplicate keys in “ASCII” files
8.1.1.4. 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 memoryOnly write when the block is flushed (not every time block is altered)One or two tests require something more. Two approachesImprove the algorithm implementation (see OpenDSA)Code tune: Look especially at wasted creation/destruction of temporary byte arrays
8.1.1.5. Project Staging¶
Download starter kit. Submit to Web-CAT. Look at the test case info.
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.
Start adding buffer pool functionality until that works completely and efficiently.
Do final optimizations to pass tests.
