Library to Empirically Estimate Big-O Time Efficiency and Check Results of Analysis in JUnit Tests with Java 8

public class HeapSortTest {

@Test

public void assertLogLinear_RunHeapSort_DetectLogLinear() {

// ARRANGE

final BigOAnalyser boa = new BigOAnalyser();

final HeapSort sut = (HeapSort) boa.createProxy(HeapSort.class);

// ACT

for (int x = (16 * 1024); x >= 1024; x /= 2) {

sut.sort(createSortInput(x));

}

traceReport(boa, "sort");

// ASSERT

BigOAssert.assertLogLinearOrPowerLaw(boa, "sort");

}

private static List<Long> createSortInput(int size) {

final List<Long> result = new ArrayList<Long>(size);

for (int i = 0; i < size; i++) {

result.add(Math.round(Long.MAX_VALUE * Math.random()));

}

return result;

}

private static void traceReport(final BigOAnalyser boa, String method) {

System.out.println("--- HeapSortTest -----------------------");

System.out.println();

final Table<Integer, String, Double> data = boa.getDataChecked(method);

System.out.println(BigOReports.getPolynomialDegree(data));

System.out.println(BigOReports.getBestFunctionsReport(data));

System.out.println(BigOReports.getDataReport(data));

}

}

With the system under test (sut):

public class HeapSort {

public Long[] sort(@BigOParameter List<Long> unsorted) {

...

}

...

}

The annotation @BigOParameter marks the parameter which is the driver of the run time. At the moment all marked parameters will be measured, but just the first will be analysed (in later versions this should be possible).

A First Big-O-Test Case - with Lambda Expressions

With Lambda Expressions you can express the same in a shorter way:

public <P> BigOResult execute(BigOTestAction<P> action) {

Preconditions.checkNotNull(action);

Preconditions.checkNotNull(clazzUnderTest);

@SuppressWarnings("unchecked")

final P sut = (P) this.boa.createProxy(clazzUnderTest);

// give JIT compiler the chance to optimize

this.boa.deactivate();

action.apply(sut);

// here the measurement starts

this.boa.activate();

action.apply(sut);

return this;

}

Estimate the Polynomial Degree

Estimating the Polynomial Degree is quite simple. You need some measured data and plot them in a log-log-graph. Try to fit a line and the slope of the line is a good estimation of the polynomial degree.

For real polynomial functions the slope is close to an integer, e.g. 3 for cubic, 2 for quadratic, 1 for linear or 0 for constant functions.

Figure 1: Slope of a fitted line in the log-log plot of measured data

final Table<Integer, String, Double> data = boa.getDataChecked(method);

System.out.println(BigOReports.getPolynomialDegree(data));

System.out.println(BigOReports.getBestFunctionsReport(data));

System.out.println(BigOReports.getDataReport(data));

System Under Test Wrapper

In some cased you may have no access to the source code or like to test static methods. In these cases, you can use a simple wrapper method:

public void sortWrapper(@BigOParameter List<Long> values) {

Collections.sort(values);

}

@Test

public void sortWrapper_RunJavaCollectionsSort_DetectPolynomialDegree() {

// ARRANGE

final BigOAnalyser boa = new BigOAnalyser();

final WrapperTest sut = (WrapperTest) boa.createProxy(WrapperTest.class);

// ACT

for (int x = (32 * 1024); x >= 64; x /= 2) {

sut.sortWrapper(createSortInput(x));

}

// ASSERT

BigOAssert.assertPolynomialDegree(boa, "sortWrapper", 1.25, 0.5);

}

and you should get an output like: