Lost in permutation complexity

综合编程 Deque

This post will be dedicated to an STL algorithm I discovered only recently, and which caused me some serious performance issue at my first use of it.

This algorithm is std::is_permutation. It appeared in the STL with C++11 and in principle, it is quite a useful algorithm. It is however deeply penalized by its inefficiency, which make this algorithm almost impractical (not worth the trade-off in most use cases).

Inside this post, we will first describe the algorithm itself and describe some of the use cases that makes it interesting in principle.

Then we will talk a bit about my misadventure with it. This misadventure could have been avoided by reading the manual
and not use std::is_permutation in the first place. I suspect other might fall into the trap as well, for reasons that we will describe as well.

We will conclude by discussing the design decision that makes this algorithm implementation inefficient by construction, and discuss some alternatives.

Motivation for std::is_permutation

From the the cppreference documentation
, std::is_permutation is an algorithm that takes two ranges as input. It indicates whether there exists a rearrangement of the elements that would make both ranges be equal. The equality criteria can be parameterized.

Anagrams

The simplest use case for std::is_permutation would be to implement a function that would tell if two strings are anagrams
of each others.

According to Wikipedia, an anagram is “the result of rearranging the letters of a word [..] to produce a new word [..], using all the original letters exactly once”
. This is a perfect match for std::is_permutation:

Equality but for the ordering

A more interesting use case of std::is_permutation is to check that two collections are equal but for the ordering. In other words, that they contain the exact same elements.

This is a pretty common use case inside Unit Tests.

For instance, we may want to test a function eval_accounting_entries
that produces a vector of accounting entries for the current period. The contract says nothing about the order of the accounting entries produced.

In order to avoid testing more than the actual contract of eval_accounting_entries
, increasing the precision and resilience of our unit test, we could use std::is_permutation instead of std::equal.

This check of equality without the ordering might be useful as well inside a GUI. We might be interested in notifying some listening processes if the user modifies some accounting entries, but not if the modification is a simple rearrangement.

Testing an unstable sort

Time to describe my little misadventure. Let us say that we just implemented a new unstable sort algorithm and want to make sure that it is correct. How can we test that our implementation is bug free?

We could do some example based tests for starter, before adding some Property Based Testing
to increase our level of confidence. The plan is to:

  1. Find a good invariant that, if it holds, proves the sort is correct
  2. Generate a bunch of random vectors
  3. Call our sort routine on each of these vectors
  4. Check that the invariant hold on the outputs of the sort

Finding a good property to check

If our sort was stable, we could check the result of our sort against std::stable_sort. That would make it a perfect property. But our sort is unstable. So we cannot compare it against a reference sort to prove that it works. Sure, std::sort is unstable too, but the unstable swaps do not have to be the same.

Fortunately for us, sorting a collection is performing a permutation of the elements of a range such that the resulting order of the elements complies with the increasing order relative to some ordering relation R
.

It means that we can check that our unstable sort works fine by simply checking whether the resulting collection answers true to both std::is_permutation and std::is_sorted.

Implementing the property

We can port this definition into code. The check_sort_property
function returns true if the result
iterable is a correct sort of the input
iterable:

Note: Asserting that std::is_sorted returns true would not be enough: there could be missing elements. Asserting that the number of elements is the same would not be enough either: it could be the same element repeated as many time as needed. We really need the permutation check to ensure our sort works correctly.

Generating vectors

We then need to generate random vectors to perform our tests. We define a function make_vector_gen
that will return a lambda which we can call to generate random vectors for us.

  • The max_size
    allows us to parameterise how big the vector can be.
  • The value_generator
    allows us to generate the content of the vector

With this small piece of code, we are able to generate random vectors made of random elements of any chosen type:

Note: alternatively, we could rely on RapidCheck
. This is the choice to make if it was production code. But as the generator is simple enough, we can do it by hand here.

Generating tuples

To test our our sort on our random vector, we must first be able to generate some random elements inside our vector. We will settle for tuples of integers.

Why tuples and not simple integers? The motivation is to test our sort routine with a “less” function that orders by the second value of the tuple. This will allow us to exercise the “unstable” part of our algorithm (sorting integers would show no differences between stable and unstable sorts).

We design our tuple generator generically. The following code allows to generate arbitrarily large tuples, makes of arbitrarily chosen types:

Composing and testing our generators

We now have the ability to generate vectors of tuples of arbitrary types. We can create a last generator of random integers:

We can now easily combine all of our generators to create a vector of tuples of integers. We can quickly check that it behaves correctly:

Three, two, one… TEST!

Everything is ready. We can now test that our custom_sort
routine does its job correctly by running some random test inputs and check that our sort property always holds.

Let us start small, with one single example of a vector holding up to 50,000 tuples of integers, which we will sort by their second component:

Now, this is where it hurts. Depending on the generating inputs:

  • The actual sorting lasts less than 1 milliseconds
  • The property check might last more than 500 milliseconds

So much for the fast feedback of unit tests… With 100 test samples (the default of most property based testing libraries), we have to wait almost a minute to get some feedback. What is happening?

Hopelessly inefficient std::is_permutation

The reason why the property check is so slow is because the implementation of std::is_permutation has a worst case quadratic complexity. This behaviour is documented in both cplusplus.com
and en.cppreference.com
.

Note: obviously, I should have read the manual. But had I read the manual, I would have chosen not to use std::is_permutation. This is not very satisfactory.

Quadratic by design

Given the definition of the std::is_permutation
algorithm, there is no other way it could be better. Having only access to an equality predicate, the algorithm cannot do much better than trying (in the worse case) all the combinations.

By asking for a little more than an equality predicate, it could do a much better job. We will explore such alternatives later in the post.

Surprisingly slow

Most algorithm design courses teach us that quadratic complexity is something we should not accept unless we have no other choice (*). The big problem here is that there are much more efficient algorithms available for us to check for std::is_permutation.

Most developers do know about these better algorithms, as they are frequently asked as interview questions. This makes the quadratic implementation of std::is_permutation
counter-intuitively slow
, increasing the the chance of introducing a performance defect in the software.

(*): The rationale is that quadratic algorithms do not scale. Linear algorithms scale with the hardware. Throwing a multiplicative logarithm does not change this result that much: with twice as much as resources, such algorithm can handle nearly twice as big inputs.

Range V3

Range V3
seems to follow the same algorithm as the one used for std::is_permutation. It also implements a quadratic algorithm to do the job. You can have a loop at permutation.hpp
and read the code by yourself.

Some alternatives

There are plenty of alternatives to implement std::is_permutation much more efficiently. Which alternative to select depends on the concepts available on the type inside the iterables provided to std::is_permutation.

Potential solutions

We list below some of these most obvious algorithms we could use to implement std::is_permutation, in decreasing order of preference:

For types with few inhabitants
, like char
, we can number each inhabitant. We can create an array, indexed by each inhabitant, and count the number of characters for both strings. We then check that the number of occurrences of each character is the same in both strings. The resulting algorithm is O(N).

For types with hash functions
, we can follow the same principle, but with a hash map. We count the frequency of each term in each collection and compare the result. We then check if the keys and their associated values (the number of occurrences of the key) match in both hash maps. The resulting algorithm is slower, but still O(N).

For types with a strict total ordering
, we can sort one of the collection, and binary search each element of the other collection in it. The usual trick is to sort the smallest collection, but in our case, if the size differ, we can early return with a negative answer. The resulting algorithm is O(N * log N) due to the sort and the N binary searches.

Drawbacks of the alternatives

Each of these alternative solutions are much faster than the std::is_permutation current implementation. They will scale properly.

The problem with each of these algorithms is that they require extra memory
to perform their work. The first two alternatives requires either an array or an hash map, and the last one will have to create a vector to avoid mutating its inputs (and also, binary search requires a random access container to be efficient, which is not a given).

One additional problem with each of these algorithms is that they ask for more than the standard Regular Type requirements
on which the STL is based. On the other side, the std::is_permutation implementation is perfectly satisfied by the Regular Type requirements.

Conclusion and what’s next

We went over a use case that show how penalising the quadratic algorithmic complexity of std::is_permutation
can be. We discussed why the algorithm could not be made better with the requirements it makes on the types contained in the ranges it takes as inputs.

We went over some alternative, in which the algorithm complexity could be vastly improved by requiring just a bit more on the types manipulated inside the algorithm.

The next post will discuss a bit more these additional requirements and whether they can be justified as basic assumption on types manipulated by the STL algorithms.

Deque稿源:Deque (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » Lost in permutation complexity

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录