Lost in permutation test complexity

综合编程 2017-04-15

In our lost in permutation complexity post
, we talked about the std::is_permutation algorithm and its algorithmic complexity issue. We went over several use cases that seems like perfect matches for std::is_permutation.

But because of its quadratic complexity, we made the argument that std::is_permutation is almost impractical: its costs is not worth the trade-off of manually coding the alternative.

In our still lost in permutation complexity post
, we discussed an alternative hash based implementation, which decreased the complexity drastically. We also discussed proposals of changes for std::hash in the STL and would improve the C++ developer’s experience.

To conclude this series, I would like to answer an interesting comment that was added in the Reddit associated post
. Answering this comment on Reddit directly would make for a big wall of text, hence this post, which aims at providing a comprehensive answer.

Situating the context

Ourfirst post started by describing a necessary and sufficient property to test that an unstable sort was doing its job correctly.

This property is based on the fact that an unstable sort is a permutation of a collection such that the resulting collection would answer true to std::is_sorted
. We named this property check_sort_property
and translated it into code:

We used this property inside a Property Based Test
. Such tests usually consist in four distinct phases:

  1. Generating random inputs (random vectors of pair of ints in our case)
  2. Call our unstable sort routine on each of these vectors
  3. Check that the property holds on the output of the unstable sort
  4. Shrinking the failing random input to find a simpler counter example

To summarize, the goal of the check_sort_property
property is to describe succinctly and precisely a condition that makes such a test pass or fail (knowing that the test is performed on random inputs).

The Reddit comment

The check_sort_property
property got some attention and got a comment saying that the usage of std::is_permutation
was not justified here, and that there were another ways to unit test the unstable sort:

[…] the given problem is unit testing an unstable sorting algorithm. Compare the output with your expected result, and check that corresponding items in output and expected are equal (or neither less than the other).

Using is_permutation to compare two sorted ranges is misguided.

The comment (as I understand it) arguments that it would be much easier to test the unstable sort by comparing the output of the unstable sort against an expected result.

To clarify my original intentions and motivations, we will go through some rationales to justify the usage of properties such as check_sort_property
to verify the correctness of an algorithm, instead of comparing with equality the result of a function call with an expected output (whether the context is property based tests or example based tests).

Missing In Action: Expected

The first category of cases in which we cannot test an algorithm result against a fixed expected result, is when the expected result is not easy to craft.

Random inputs

In most cases, it proves very difficult to check our input against expected results when the inputs are random. This is precisely what we do in property based testing

As mentioned in ourfirst post, finding the exact expect result is sometimes feasible anyway. For instance, if we have a reference algorithm to test against. We could use std::stable_sort
to test against, if we were implementing a stable sort.

In our case however, there is no algorithm that would match exactly what we want to test. We went over this argument in the section “FINDING A GOOD PROPERTY TO CHECK” of ourfirst post.

Big inputs

One second use case in which the “expected” result is not easily accessible is when dealing with big inputs. For instance, we could try to test our unstable sort on a vector of thousands or more elements.

An hand-crafted expected result (matching a hand-crafted input) will be very hard to create and later maintain. Understanding the failure in such case is hard if not abstracted by good properties (predicates).

It becomes so tedious that most developers will just copy-paste the result of their algorithm and set it as “expected” output. This defeats the purpose of testing in the first place. But it gets even worse: it transforms “unit tests” into “regression tests”. These regression tests do not ensure correctness as much as they ensure that nothing changes.

This is rarely a good idea: software changes. These changes will be made harder by such tests, that will most likely be red in a non-meaningful way. The errors will most likely be ignored, and the test will undergo the same process as the creation of the test: a copy-paste of the new result into the “expected” result.

Beware of over-testing

Now, and even if we can hand-craft an appropriate expected output, there is another reason why checking the output of the unstable sort against an expected result is not necessarily something we should do.

It has to do with testing too much of an algorithm.

Freedom to improve

The purpose of implementing an unstable sort instead of a stable sort is to get a degree of freedom on the output of the algorithm. This degree of freedom can be leveraged to implement a faster algorithm.

This freedom extends in the time axis too: it should be fine to get different results for our stable sort across releases. If we discover a faster implementation in the future, we want to be in position to implement it. This might change the relative ordering of equivalent elements: this is fine.

Freedom implication on tests

If we have unit tests that test the whole expected output, instead of relying on a property that tests only what makes the result of our unstable sort valid, we might slow down future changes in our implementation.

Improving the algorithm could make such tests go red. It could be because we broke the algorithm. It could also be because the test relied on the implementation details of the algorithm (the specific instability). In short, unit tests should test the interface, not the implementation details

For that reason, testing the output of an algorithm using a property might have a big positive impact on adapting to change. To do so, the should test the contract of the function and no more. Such tests will turn red only if we truly broke something.

(*): This argument for testing the contract and not the implementation is in contradiction with some brainless applications of Test-driven development
. The inflexibility of locking everything in place with implementation details testing will likely hurt your productivity.


I hope this post answers the valid concerns that were raised inside the Reddit post
and did clarify why we went for the implementation of a property making use of std::is_permutation
and std::is_sorted
to verify the correctness of our unstable sort.

It first had to do with the use of property based testing, and the difficulty to come up with exact expected outputs in such a situation. But it also has to do with the notion of testing the contract of a function and not its implementation, to make future changes easier (within the boundaries of the contract).

You can contact or follow me on Twitter


责编内容by:Deque (源链)。感谢您的支持!


Lua Bindings Shootout As part of improving sol, benchmarks are done to measure the runtime impact o...
Some questions about coding and testing an API I'm building an API in PHP using CodeIgniter framework (with an API library ...
A Gentle Introduction to Statistical Hypothesis Te... Data must be interpreted in order to add meaning. We can interpret data by ...
Do you think your code is Perfect? Well, Think aga... “Any fool can write code that a computer can understand. Good programmers wri...
Here Is Theranos CEO Elizabeth Holmes’ Desperate L... Theranos, the disgraced blood testing company, is in dire financial straits and...