# Lab 03: Timing Tests and Randomized Comparison Tests

[Prerequisites](https://tomthestrom.gitbook.io/cs61b-fall-2022/prerequisites-to-running-the-assignments.) 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 [#](https://fa22.datastructur.es/materials/lab/lab03/#timing-tests-for-list61b) <a href="#timing-tests-for-list61b" id="timing-tests-for-list61b"></a>

### Timing the construction of an AList with a bad resize strategy <a href="#timing-the-construction-of-an-alist-with-a-bad-resize-strategy" id="timing-the-construction-of-an-alist-with-a-bad-resize-strategy"></a>

As discussed [in lecture](https://docs.google.com/presentation/d/1ZKSPKdEjlLlzmf7LoQJlTUC3w0MPInSXy2DxTEva0yo/edit#slide=id.g625dc7e36_0943), 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:

```java
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:

```clike
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.30
```

#### Solution:

`class TimeAList`

```java
/**
 * 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:**

```clike
    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.57
```

### Timing 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:

```java
/** 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:**

```clike
           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.02
```

### Timing the getLast method of SLList [#](https://fa22.datastructur.es/materials/lab/lab03/#timing-the-getlast-method-of-sllist) <a href="#timing-the-getlast-method-of-sllist" id="timing-the-getlast-method-of-sllist"></a>

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:

1. Create an `SLList`.
2. Add N items to the `SLList`.
3. Start the timer.
4. Perform M getLast operations on the `SLList`.
5. Check the timer. This gives the total time to complete all M operations.

#### Solution:

`class TimeSLList`

```java
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:**

```java
           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.90
```

Obviously 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 [#](https://fa22.datastructur.es/materials/lab/lab03/#simple-comparison-test) <a href="#simple-comparison-test" id="simple-comparison-test"></a>

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`

```java
/*
 * 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 [#](https://fa22.datastructur.es/materials/lab/lab03/#randomized-function-calls) <a href="#randomized-function-calls" id="randomized-function-calls"></a>

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: <a href="#randomized-function-calls" id="randomized-function-calls"></a>

```java
@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:

```java
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:

```java
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.