A hidden gem: inner_product

Posted: November 14, 2017 in Competitive Programming, Programming Recipes
Tags: , ,

I know, it’s been a while since the last time I published something on my blog. The main reason is that in my spare time – apart from private life – I’ve been committed to organize events and activities in Italy and also to work on a personal project with a great friend of mine. Anyway, I found some time to share a new blog post I hope you will like.

This article is also part of my series C++ in Competitive Programming.

In the very first installment of this series, I showed an example whose solution amazed some people. Let me recall the problem: we have to find the minimum difference between any two elements in a sorted sequence of numbers. For example:

[10, 20, 40, 100, 200, 300, 1000]

The minimum difference is 10, that is 20-10. Any other combination is greater. Then, I showed an unrolled solution for such problem (not the most amazing one!):

Imagine there is always at least one element in the sequence. Note that we calculate elems[i+1]-elems[i] for each i from 0 to length-1, meanwhile, we keep track of the maximum of such differences. I see a pattern, do you?

Before getting to the point, let me show you another example. We want to calculate the number of equal adjacent characters in a string:

ABAAACCBDBB

That is 4:

ABAAACCBDBB

Again, here is a solution:

We compare s[i] with s[i-1] and, meanwhile, we count how many trues we get. Careful readers will spot a little difference from the previous example: at each step, we access s[i] and s[i-1], not s[i+1] and s[i]. I’ll develop this subtlety in a moment. Now, please, give me another chance to let you realize the pattern yourself, before I elaborate more.

This time we have two vectors of the same size, containing some values and we want to calculate the maximum absolute difference between any two elements. Imagine we are writing a test for a numerical computation, the first vector is our baseline (expectation) and the second vector is the (actual) result of the code under test. Here is some code:

Here we access the ith-elements of both the vectors at the same time. Is that similar to the other examples?

It’s time to get to the point, although you are already there if you have read the intro of this series – if you have not, please stay here and don’t spoil the surprise yourself!

Actually, there is not so much difference among the examples I showed. They are all obeying the same pattern: given two sequences, the pattern combines every two elements from input sequences at the same position using some function and accumulates these intermediate results along the way.

Actually, in functional programming, this pattern is the composition of three different patterns:

zip | map | fold

zip makes “pairs” from input sequences, map applies a function to each pair and returns some result, fold applies an operation to reduce everything to a single element. A picture is worth a thousand words:

For simplicity, imagine that zip and map are combined together into a single operation called zipWith.

Now we have two customization points:

  1. which function zipWith uses to combine each pair, and
  2. which function fold uses to reduce each result of zipWith to a single element.

The general case of this pattern operates on any number of sequences, making a tuple for each application of zip (e.g. imagine we zip the rows of a matrix, we get its columns).

In C++ we have an algorithm that (partially) implements this pattern: inner_product. I said “partially” just because it accepts only two ranges and for this reason I say “pairs of elements”, not tuples – as in the general case. In C++17’s parallel STL, inner_product is made in parallel by transform_reduce (be aware of the additional requirements).

In the future we’ll do such things by using new tools that will be incorporated into the standard: ranges. For now, inner_product is an interesting and (sometimes) understimated tool we have. Regardless you are going to use such pattern in real-world code, I think that understanding when this pattern applies is mindblowing. If you regularly practice competitive programming as I do, you have the opportunity to recognize many patterns to solve your problems. In the last years I have found several cases when this pattern worked smoothly and I am sharing here a few.

The simplest form of inner_product takes two ranges of the same length and a starting value, and it calculates the sum of the products of each pair. It’s literally an inner product between two vectors. inner_product has two additional customization points to replace “product” and “sum” as we wish.

Let’s have some fun.

It’s time to code the solutions to the previous challenges in terms of inner_product. I start from the latter.

I recall that we want to find the maximum absolute difference of two vectors of double. In this case we replace “product” with “absolute difference” and “sum” with “max”. Or, we combine each pair by calculating the absolute difference and we keep track of the maximum along the way. I stress the fact that we reduce the combined pairs along the way and not at the end: inner_product is a single-pass algorithm (e.g. it works on stream iterators).

Here is the code:

I tend to use standard function objects as much as possible. They are just clearer, shorter and (should be) well-known. Thinking a bit more we come up with:

Better than the other? It’s debatable, I leave the choice to you.

The other two challenges are on a single sequence, aren’t they? Does the pattern still apply?

It does.

Zipping two distinct ranges is probably more intuitive, but what about zipping a sequence with itself? We only have to pass correct iterators to inner_product. We want to combine s[i] with s[i-1]. zipWith should use operator== and fold operator+. For the first sequence we take S from the second character to the last character. For the second sequence we take S from the first character to the second last character. That is:

  1. S.begin() + 1, S.end()
  2. S.begin(), S.end()-1

We have to pass the first three iterators to inner_product:

We zip with equal_to which uses operator== under the hood and we fold with plus<> which applies operator+. As you see, not having to specify the second sequence’s boundary is quite handy. If the solution is not clear, I hope you will find this picture useful:

When equal_to is called, the left hand side is S[i] and the right hand side is S[i-1]. In other words, the first range is passed as the first parameter to zipWith and the second range as the second parameter.

Careful readers will spot a subtle breaking change: the solution is not protected against an empty string anymore. Advancing an iterator that is not incrementable (e.g. end) is undefined behavior. We have to check this condition ourself, if we need. This example on HackerRank never fall into such condition, so the solution is just fine.

Finally, in the first exercise we are requested to calculate the minimum difference between any two elements in a sorted sequence of numbers. I intentionally wrote elems[i+1]-elems[i] and not elems[i]-elems[i-1]. Why? Just to show you another form of the same pattern. This one I like less because the call to inner_product is more verbose:

We can apply the other pattern by (mentally) turning the loop into elems[i] – elems[i-1]:

As before, the solution is not protected against an empty sequence. You understand that zipping a sequence on itself (by shifting it) is never protected against an empty range.

This pattern works in all the examples above just because the stride between two elements is 1. If it was greater, it would have failed – I know, we can use boost::strided or such but I don’t mind here. Basically, we have processed adjacent elements in a “window” of size 2. There are scenarios where this window can be larger and inner_product still applies.

As an example we take Max Min on HackerRank. This problem is very close to calculating the minimum difference between any two elements in a sorted sequence of numbers. It states: Given a list of N non-unique integers, your task is to select K integers from the list such that its unfairness is minimized. If (x1,x2,…,xk) are K numbers selected from the list, the unfairness is defined as:

max(x1, x2, …, xk) – min(x1, x2,…, xk)

A possible solution to this problem consists in sorting the sequence and applying zipWith | fold as we did in the very first example. The only difference is that the distance between the two elements we zip together is K-1:

Do not misunderstand: inner_product still steps by one every time and still combines elements in pairs. It’s just that we zip the sequence with itself by shifting it by K-1 positions and not by just 1. Here is what I mean:

As you see, although the size of the window is K, inner_product still works in the same way as before. The pairs that it conceptually creates (remember that the first sequence is shifted by K-1 positions) are depicted below:

 

This works only if K is less than or equal to N (and N has to be at least 1).

The pattern fits this problem because we turn the sequence in a particular structure: we sort it. We have to select K elements and we know that min(x1,…,xk) is x1 and max(x1,…,xk) is xk. This is just an effect of sorting. So we just check all these possible windows, incrementally, by using only x1 and xk. We may ignore erverything inside the window. Another interesting property is that the first range passed to inner_product is always greater (the problem states that all elements are distinct) than the second, for each iteration. This is why we can use minus<> for zipWith. If we wanted the opposite, we would have changed the order of the iterators or we would have iterated backwards. Using algorithms make variations simpler than rolling a for loop.

 

Recap for the pragmatic C++ competitive coder:

  • In C++, (zip | map | fold) on two ranges is implemented by inner_product:
    • set the first callable to customize fold (plus by default);
    • set the second callable to customize (zip | map) – combined in a single operation (multiplies by default);
    • the order of the iterators matter: the first range is the left hand side of zipWith, the second range is the right hand side;
  • zipping a sequence on itself is just the same pattern;
    • be aware it won’t work with ranges shorter than the number of positions we shift the sequence by (e.g. 1 in the first 3 examples);
  • praciting recognizing and understanding coding patterns is food for the brain.
Advertisements
Comments
  1. DrDrag says:

    I enjoyed this article. Although I knew inner product before, I only used it for real inner products.

    But hell, there are even more obscure functions like valarray.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s