Stress testing for “Data Structures and Algorithms” courses – Java & Python

I am doing the Data Structures And algorithms specialization on Coursera. (Which means every now and then I pick it up and make a few weeks of progress…) Started out with Python and now I’m switching to Java.

In this post I’ll show you how to set up stress testing, by generating random input data and comparing your implementation’s results to correct “naive algorithm” results.

I’ll also share a script that loads input from files and compares them to answers. This is useful for testing example inputs or pre-given tests for some exercises (usually where stress testing is not feasible)

Moreover, there is a GitHub repo with the ready-to-use solution.

You can find more info about stress testing in Week 1 of the Algorithmic Toolbox course. It contains an example implementation of stress testing in C++ but we’re going to do more here.

Which language is better – Java or Python?

Let’s get this out of the way. In my opinion, Python is much better suited for prototyping and experimenting with algorithms. It has dynamic types, functions can be used as variables, lists are dead simple to use etc.

Java on the other hand is faster (it’s compiled into JVM bytecode before running) and if you figure out some quirks of the language then it’s fine for developing maintainable, robust and scalable algorithms, albeit in a bit more verbose way.

Maybe I should just try Kotlin next time 🙂 but I digress.

Requirements

What do we want to achieve with this stress tester? We need to get the requirements right to develop the right solution.

1. We have to use Java 8 without any help like Lombok annotations.
2. In these courses, you can only submit one file per assignment. Files must be ready for upload without any changes.
   This means that we can’t refer to any external interfaces/classes/modules from the solution, but we can go the other way.
3. We don’t want to copy the same stress tester code into every assignment file, but would rather to use the same external file with minimal modifications, so that we can improve it if needed.
4. We would like to measure performance and debug failed solutions if needed.

Stress testing implementation

As an example that works but doesn’t reveal any assignment solutions, we’ll just use the ‘algorithm’ that adds two numbers.

Java

Java algorithm

We can’t use interfaces but need to have an implicit one to do stress testing.

The main() function can stay, but we’ll need two functions, naiveAlgorithm() and implementedAlgorithm(). Their names have to stay the same across all assignments.

As return types, if it’s a list of numbers, I suggest using lists of objects (e.g. ArrayList<Integer>) instead of arrays of primitives (e.g. int[]). This is because lists do .equals() as we expect – not by exact reference, but by shallowly comparing elements. Also, they have better .toString() than arrays.

You can use arrays during your algorithm, just convert it to a list at the end, using streams like this (source):

return Arrays.stream(result)
  .boxed() // converts int to Integer etc.
  .collect(Collectors.toList());Code language: Java (java)

Java data class

We need to call the algorithm with the same data from the stress tester, but we don’t know (don’t want to know) what kind of data we’ll need. For Python or Javascript, we could use destructuring to convert an array into function call parameters.

For Java, it’s much nicer to create a data class for algorithm input. So this way,
aPlusB(int a, int b)
becomes
implementedAlgorithm(APlusBData data).

For simplicity, the data class can have public fields and a simple constructor. I also suggest adding toString to display data (you can easily generate it with NetBeans or IntelliJ).

For adding two numbers, it’s as simple as:

class APlusBData {
  public int a;
  public int b;

  public APlusBData(int a, int b) {
    this.a = a;
    this.b = b;
  }
}Code language: PHP (php)

main() will be modified to also generate an instance of this data class after reading from the standard input.

Java data generator class

This class is responsible for generating random input data. We could just use a static generate() method on the data class but it’s better to keep this functionality separate.

The code speaks for itself, you’ll have to use similar stuff for each assignment:

class APlusBDataGenerate
{
  static int min = -50000;
  static int max = 50000;
  static Random random = new Random();

  public static APlusBData generate()
  {
    return new APlusBData(randomInt(min, max), randomInt(min, max));
  }

  // utility methods like this can be copied to later assignments
  private static int randomInt(int min, int max)
  {
    return random.nextInt(max - min) + min;
  }
}Code language: PHP (php)

Java stress tester

You have two options for calling the class under test:

• Hardcoding the class name to call
• Using Java’s reflect API… and hardcoding the class name to call. Duh.

Anyways, the stress tester code is not that complicated. It contains some customization such as number of tests and also measures execution time with Instant objects.

Because we use lists (or autoboxed primitives like Integer) as outputs, it’s easy to compare them via .equals() and printing them with .toString(). Here’s the code:

public class StressTester {

    private static boolean shouldStop = true;
    private static int numTests = 100;

    public static void main(String[] args) {
        int count = 1;
        while (true) {
            System.out.println("Test " + count++);
            APlusBData data = APlusBDataGenerate.generate();
            Instant startTime = Instant.now();
            Object naive = APlusB.naiveAlgorithm(data);
            Instant stopTimeN = Instant.now();
            Object implemented = APlusB.implementedAlgorithm(data);
            Instant stopTimeI = Instant.now();

            System.out.println("Naive: " + Duration.between(startTime, stopTimeN)
                    + ", implemented: " + Duration.between(stopTimeN, stopTimeI));

            if (!naive.equals(implemented)) {
                System.out.println("Test failed!");
                System.out.println("Solution: " + naive);
                System.out.println("Yours:    " + implemented);
                // debug if needed
                APlusB.implementedAlgorithm(data);
                break;
            }

            if (shouldStop && count > numTests) {
                System.out.println("Success!");
                break;
            }
        }
    }
}Code language: JavaScript (javascript)

As you can see, you have to replace all APlusB, APlusbData, APlusBDataGenerate references if you want to stress test a different class.

In the GitHub repo, there’s another file that uses Class objects to call the required functions – there you only have to change class names in a single place.

Okay, so much for Java.

Python

Life is much easier in Python:

• We have top-level functions exported
• Functions are first class citizens i.e. can be easily used in variables
• We can use any array to be destructured into function call parameters

All is needed is a gen_params() function in each assignment that generates stress test data in a list, plus a functions variable that exports the naive and implemented algorithms like this:

functions = [sum_of_two_digits_naive, sum_of_two_digits]

Then the stress tester is as simple as:

import sys
from time import time
import APlusB as runner # only need to input file name here

def stress_test():
    print("Start")
    n = 0
    fs = runner.functions
    while True:
        results = []
        times = []
        data = runner.gen_params()
        for f in fs:
            try:
                t0 = time()
                results.append(f(*data))
                t1 = time()
                times.append(t1 - t0)
            except:
                print("Error! Data:", data)
                raise

        if all(x == results[0] for x in results):
            print("OK", n, "| Input:", "| Times/ratio:", *[[fs[l].__name__, f'{times[l]:.2f}', f'{times[l] / times[0]:.2f}'] for l in range(len(times))])
            n += 1
        else:
            print("Wrong answer", results, "Data:", data)
            breakCode language: PHP (php)

Testing algorithms from files

Okay, so we have a tests/ folder, with a bunch of numbered files, like 1, 2, 3... for inputs and 1.a, 2.a etc. for expected outputs. All we need is to run the full program as intended and compare results to expected answers.

To do this, I have created a Fish script. Fish is a popular shell similar to bash, but easier to use and script. If you haven’t started using it yet, I suggest doing so. 🙂

The script looks like this:

#!/usr/bin/env fish

if test (count $argv) = "0"
  echo "Give class or file name as argument!"
  exit 1
end

echo "Running all test cases from ./tests"

set PROGRAM java -cp ./target/classes $argv
# python:
# set PROGRAM python3 $argv

set TESTS (find ./tests -type f -name '*[^.a]' | sort -g)
# length of diff output
set LENGTH 10000

for TEST in $TESTS
    set RESULT (cat $TEST | $PROGRAM | tr -d '[:space:]')
    set EXPECTED (cat $TEST.a | tr -d '[:space:]')
    if test $RESULT = $EXPECTED
        printf "Test %s OK\n" $TEST
    else
        printf "Test %s ERROR \n -actual:   %s\n -expected: %s\n -diff" $TEST (echo $RESULT | cut -c 1-$LENGTH) (echo $EXPECTED | cut -c 1-$LENGTH)
        # break
    end
endCode language: PHP (php)

If using Java, first compile the code with mvn compile (if using Maven), or turn on auto-compile in the IDE. Maven places resulting .class files in target/classes/ folder so we can use that for execution.

If using Python, uncomment the corresponding line and run the tester with the same syntax.

$ fish test.fish APlusB[.py]

That’s it!

GitHub repo

I created a repo with all the code. Feel free to take a look:

I hope you enjoyed this little guide! If you have any questions let me know in the comments or a GitHub issue/PR.