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.