Testing with Hypothesis

https://bit.ly/hypothesis-pydata-london

What is Hypothesis?

  • Randomised testing library based on the Haskell library, Quickcheck.
  • You write the tests, Hypothesis gives you the examples.

The Problem

  • Feedback Arc Set for Tournaments.
  • Trying to provide a good "ranking" for a tournament.
  • Given an \(n \times n\) matrix of weights, A, find a permutation \(\sigma \in S_n\) that minimizes \(\sum_{i < j} A_{\sigma j, \sigma i} \).
  • n=30 is hard. n=100 is insoluble.

import numpy as np

def cost(tournament, order):
    n = tournament.shape[0]
    return sum(
        tournament[order[j], order[i]]
        for i in range(n)
        for j in range(i + 1, n)
    )

def feedback_arc_set_tournament(tournament):
    m, n = tournament.shape
    assert m == n
    weights = np.zeros(dtype='uint', shape=n)
    for i in range(n):
        for j in range(n):
            if i != j:
                weights[i] += tournament[j, i]
    return np.argsort(weights)
  


from hypothesis import given
from hypothesis.extra.numpy import arrays


@given(arrays(dtype='uint', shape=(3, 3)))
def test_is_no_worse_than_reverse(tournament):
    result = feedback_arc_set_tournament(tournament)
    assert (
      cost(tournament, result) <=
      cost(tournament, result[::-1])
    )
  


Falsifying example: test_is_no_worse_than_reverse(
  tournament=array([
    [0, 0, 0],
    [0, 0, 1],
    [1, 1, 0]], dtype=uint64))

AssertionError: assert 2.0 <= 1.0
    where 2.0 = cost(tournament, array([0, 1, 2]))
    and   1.0 = cost(tournament, array([2, 1, 0]))
  

Conclusion

  • Hypothesis hooks your algorithms up to high quality random data.
  • Lets you focus on testing invariants rather than writing examples.
  • You should be using Hypothesis to test your code.

drmaciver.com / @DRMacIver

https://hypothesis.readthedocs.org/

https://bit.ly/hypothesis-pydata-london