Lab 03: Timing Tests and Randomized Comparison Tests
Prerequisites to running the code.
Instructions: https://fa22.datastructur.es/materials/lab/lab03/
Solution: https://github.com/tomthestrom/cs61b/tree/master/lab03
The lab deals with writing timing and randomized tests, comparing their outputs and finding and fixing a tiny bug.
Timing Tests for List61B #
Timing the construction of an AList with a bad resize strategy
As discussed in lecture, a multiplicative resizing strategy will result in fast add operations / good performance, whereas an additive resizing strategy will result in slow add operations / bad performance. In this part of the lab, we’ll show how we can demonstrate this empirically.
In the timingtest package, we’ve provided the AList class created in lecture with the bad resizing strategy below:
public void addLast(Item x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size = size + 1;
}Your goal for this part of the lab is to write code that tabulates the amount of time needed to create a AList of various sizes using the addLast method above. The output of this timing test will look something like this:
Timing table for addLast
N time (s) # ops microsec/op
------------------------------------------------------------
1000 0.00 1000 0.20
2000 0.01 2000 0.20
4000 0.01 4000 1.20
8000 0.04 8000 4.30
16000 0.10 16000 10.00
32000 0.50 32000 49.70
64000 1.15 64000 114.80
128000 3.74 128000 374.30Solution:
class TimeAList
/**
* Returns a table with rows at N breakpoints from startingN to MAX_N for addLast operation of AList
*/
public static void timeAListConstruction() {
//starting nr of ops
int startingN = Math.multiplyExact(1, 1000);
//max nr of ops
int MAX_N = Math.multiplyExact(128, 1000);
AList<Integer> Ns = new AList<>();
AList<Double> times = new AList<>();
AList<Integer> opCounts = new AList<>();
/**
* for MAX_N = 128 runs 8 times - br points:
* 1 000 / 2 000/ 4 000/ 8 000/ 16 000/ 32 000 /64 000 /128 000
*/
for (int n = startingN; n <= MAX_N; n *= 2) {
AList<Integer>timedA = new AList<>();
Stopwatch sw = new Stopwatch();
int opCount;
/**
* Fill ArrayList timedA with ints from 0 to N
* */
for (opCount = 0; opCount < n; opCount += 1) {
timedA.addLast(opCount);
}
//stop Stopwatch
times.addLast(sw.elapsedTime());
Ns.addLast(n);
opCounts.addLast(opCount);
}
printTimingTable(Ns, times, opCounts);
}
Output - of the timing test - AList with a bad resize strategy:
N time (s) # ops microsec/op
1000 0.00 1000 1.00
2000 0.00 2000 1.50
4000 0.01 4000 2.25
8000 0.03 8000 3.50
16000 0.07 16000 4.38
32000 0.23 32000 7.13
64000 0.65 64000 10.17
128000 2.38 128000 18.57Timing the construction of an AList with a good resize strategy
Now modify the AList class so that the resize strategy is multiplicative instead of additive and rerun timeAListConstruction. Your AList objects should now be constructed nearly instantly, even for N = 128,000, and each add operation should only take a fraction of a microsecond.
Solution:
AList - addLast - modified resize to be multiplicative:
/** Inserts X into the back of the list. */
public void addLast(Item x) {
if (size == items.length) {
resize(size * 2);
}
items[size] = x;
size = size + 1;
}Output - of the timing test - AList with a good resize strategy:
N time (s) # ops microsec/op
------------------------------------------------------------
1000 0.00 1000 0.00
2000 0.00 2000 0.00
4000 0.00 4000 0.25
8000 0.00 8000 0.00
16000 0.00 16000 0.06
32000 0.00 32000 0.06
64000 0.00 64000 0.03
128000 0.00 128000 0.02Timing the getLast method of SLList #
Suppose we want to compute the time per operation for getLast for an SLList and want to know how this runtime depends on N. To do this, we need to follow the procedure below:
Create an
SLList.Add N items to the
SLList.Start the timer.
Perform M getLast operations on the
SLList.Check the timer. This gives the total time to complete all M operations.
Solution:
class TimeSLList
public static void timeGetLast() {
//starting nr of ops
int startingN = Math.multiplyExact(1, 1000);
//max nr of ops
int MAX_N = Math.multiplyExact(128, 1000);
int MAX_OP_COUNT = Math.multiplyExact(1, 10000);
AList<Integer> Ns = new AList<>();
AList<Double> times = new AList<>();
AList<Integer> opCounts = new AList<>();
/**
* for MAX_N = 128 runs 8 times - br points:
* 1 000 / 2 000/ 4 000/ 8 000/ 16 000/ 32 000 /64 000 /128 000
* Fills SLList with N items
* Calls getLast() of the SLList MAX_OP_COUNT times
*/
for (int n = startingN; n <= MAX_N; n *= 2) {
SLList<Integer> timedSLL = new SLList<>();
int opCount;
/**
* Fill SLList timedSLL with stuffing (ints from 0 to N)
* */
for (int stuffing = 0; stuffing < n; stuffing += 1) {
timedSLL.addLast(stuffing);
}
Stopwatch sw = new Stopwatch();
// call getLast() MAX_OP_COUNT times
for (opCount = 0; opCount < MAX_OP_COUNT; opCount += 1) {
timedSLL.getLast();
}
//stop Stopwatch
times.addLast(sw.elapsedTime());
Ns.addLast(n);
opCounts.addLast(opCount);
}
printTimingTable(Ns, times, opCounts);
}Output of the timing test - SLList getLast() - 1000 times for various sizes of SLList:
N time (s) # ops microsec/op
------------------------------------------------------------
1000 0.02 10000 1.90
2000 0.03 10000 3.30
4000 0.07 10000 6.60
8000 0.15 10000 14.90
16000 0.29 10000 28.80
32000 0.58 10000 57.90
64000 1.11 10000 111.30
128000 2.66 10000 265.90Obviously not a great output for retrieving the last item - this implementation of SLList goes over all the items to reach the last one.
Randomized Comparison Tests
Simple Comparison Test #
The goal of the rest of this lab is to find the bug in BuggyAList - a resizing AList. For our comparison, we're using a non-resizing, simple version of AList, called AListNoResizing that has an underlying array with a hardcoded size of 1000 .
Write a test called testThreeAddThreeRemove in TestBuggyAList that adds the same value to both the correct and buggy AList implementations, then checks that the results of three subsequent removeLast calls are the same.
Solution:
testThreeAddThreeRemove
/*
* Simple comparison test
* Test compares the results from performing the same operation on 2 classes:
* Class AListNoResizing vs TestBuggyAList
*/
@Test
public void testThreeAddThreeRemove() {
AListNoResizing<Integer> ALNR = new AListNoResizing<>();
BuggyAList<Integer> BAL = new BuggyAList<>();
int testVal1 = 3;
int testVal2 = 4;
int testVal3 = 5;
ALNR.addLast(testVal1);
ALNR.addLast(testVal2);
ALNR.addLast(testVal3);
BAL.addLast(testVal1);
BAL.addLast(testVal2);
BAL.addLast(testVal3);
assertEquals(ALNR.removeLast(), BAL.removeLast());
assertEquals(ALNR.removeLast(), BAL.removeLast());
assertEquals(ALNR.removeLast(), BAL.removeLast());
}The test passed - it's not strong enough to identify the bug in BuggyAList
Randomized Function Calls #
Next we were encouraged to write a randomized test and use the debugger to find the bug, I came up with the following test suite:
Solution:
@Test
public void randomizedTest() {
AListNoResizing<Integer> L = new AListNoResizing<>();
BuggyAList<Integer> BL = new BuggyAList<>();
int N = 500;
for (int i = 0; i < N; i += 1) {
int operationNumber = StdRandom.uniform(0, 4);
// if operation can't be executed proceed to the next iteration
if (L.size() == 0 && SizeNonZeroOperation.get(operationNumber)) {
continue;
}
switch (operationNumber) {
case 0 -> {
int randVal = StdRandom.uniform(0, 100);
L.addLast(randVal);
BL.addLast(randVal);
}
case 1 -> {
int sizeL = L.size();
int sizeBL = BL.size();
assertEquals(sizeL, sizeBL);
}
case 2 -> {
int lastValL = L.getLast();
int lastValBL = BL.getLast();
assertEquals(lastValL, lastValBL);
}
case 3 -> {
int lastValL = L.removeLast();
int lastValBL = BL.removeLast();;
assertEquals(lastValL, lastValBL);
}
default -> System.out.println("Operation nr " + operationNumber + " not implemented.");
}
}
}
Fixing the bug
Actually the bug lied an incorrect argument to the resize method
Original:
public Item removeLast() {
if ((size < items.length / 4) && (size > 4)) {
resize(size / 4);
}
Item x = getLast();
items[size - 1] = null;
size = size - 1;
return x;
}Solution:
public Item removeLast() {
if ((size < items.length / 4) && (size > 4)) {
resize(items.length / 4);
}
Item x = getLast();
items[size - 1] = null;
size = size - 1;
return x;
}Reasoning:
size != items.length, items is the underlying array, whose length only changes on resize, while size is an attribute that represents the number of elements in the array.
Last updated