Hi, I'm David MacIver, and I'd like to talk to you briefly about my testing library, Hypothesis.
So what is Hypothesis? It's a randomized testing library. Instead of writing examples, you specify what shape they should have, and Hypothesis tries your code against a wide variety of things of that shape.
We're going to look at an optimization problem called Feedback Arc Set for Tournaments. You're trying to put 1 through n into an order that agrees with a matrix of weights as much as possible.
It's for people who find travelling salesman too easy. n=thirty is hard, n=hundred is insoluble in the general case.
Here's a very bad solution to it. Don't worry about the details too much, but we're giving each number a weight that is the sum of how much other numbers want to sort before it, so high weight things go to the end.
We'll use Hypothesis to find problems with this approach. It's bad enough that we won't have to try very hard, but similar techniques would work for a more sophisticated ones.
We'll ask Hypothesis for three by three matrices of unsigned integers, then run the optimiser on them. Three by three is arbitrary - it could be much larger, but I needed to fit the output on a slide.
We're now going to assert that our solution is never backwards, regardless of the input: That is, if we run the optimizer it should never get an answer that we can improve just by flipping it in the opposite direction.
Lets run this under py.test and see what happens.
And we get an error. Our really bad optimiser is indeed really bad.
Hypothesis gives us this nice small matrix of zeroes and ones. It will have found a much more complicated example and then shrunk it down into something legible. The result isn't always this nice, but it's usually pretty nice.
What's happening here is that Hypothesis has found a case where every number was given the same weight, so we just got the default order, but we actually should have sorted 2 before 0.
We could fix this now and rerun the test, and Hypothesis would first rerun this example and then if we fixed the problem start looking for new ones. However we don't have time for that.
So instead I'll conclude here.
In summary, you should be using Hypothesis to test your code, because it's great. It will save you time and find bugs you'd have otherwise missed.
Here are some follow up links to me, to Hypothesis, and to these slides.
Thank you very much.