std::equal_range

-
Today we are talking about equal_range. Take a look at the signatures here. This is a handy little algorithm that returns the range (as a pair of forward iterators) where each item in the returned range matches the value (where what "matches" is defined by the Compare). We will look at a practical use in this post, that actually relates to a previous post on a piece of software called Contex. 

Suppose we have a vector of strings and we have a vector of unique queries. We want to count the number of times a query appears in the vector of strings. A very obvious way to do it takes $O(ns)$ where $n$ is the length of the string vector and $s$ is the number of queries. This is not very good. There are (at least) two better ideas
  • We can attempt to sweep the strings "at the same time" as the queries.
  • We can carry out a binary search on a sorted version of the strings for the beginning and end of a range of strings that satisfy each query, for each query.
Both of these involve sorting the vectors so we impose a cost of $O(n \log n)$ off the bat. The first solution then incurs a $O(n)$ cost in the event that all of (or most of) the queries appear in the vector. If all the queries are not in the vector then we suffer greatly and return to the  $O(sn)$ cost.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
std::unordered_map<std::string, int> matchingStrings(std::vector<std::string>& strings,
                                                     std::vector<std::string>& queries) {
 std::sort(strings.begin(), strings.end());
 std::sort(queries.begin(), queries.end());
 std::unordered_map<std::string,int> counts;
 auto s = strings.begin();
 bool notfound;
 int count = 0;
 for (const auto& q : queries) {
     count = 0;
     auto temp = s;
     notfound = false;
     while (q!=*s) {
         if (s != strings.end()-1) {
             s++;
         }
         else {
             counts[q] = count;
             notfound = true;
             s = temp;
             break;
         }
     }
     if (notfound) continue;
     while (q==*s) {
         count++;
         if (s != (strings.end()-1)) {
             s++;
         }
         else {
             break;
         }
     }
     counts[q] = count;
     }
     return counts;
}

If we use the other method that involves using a binary search then we can be a little more robust on our complexity estimates. The following code has a complexity bound of $O((n+s)\log(n))$. This irrespective of whether we find the query or not, obviously things get better if we actually find the query.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::unordered_map<std::string, int> matchingStrings(std::vector<std::string>& strings,
 std::vector<std::string>& queries)
{
 std::sort(strings.begin(), strings.end());
 std::sort(queries.begin(), queries.end());

 std::unordered_map<std::string, int> counts;

 auto start = strings.begin();

 for (auto const& q : queries) {
     auto first = std::lower_bound(start, strings.end(),q);
     auto second = std::upper_bound(start, strings.end(),q);
     counts[q] = second - first;
     start = second;
     }
     return counts;
}

std::lower_bound and std::upper bound use a binary search, each incurring a logarithmic cost. Needless to say the code is so much cleaner and more readable. Note that we update the starting point of the binary searches, this is because looking before the end of the previous range is wasteful (both vectors are sorted). We can go one step further with the STL using std::equal_range...


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::unordered_map<std::string, int> matchingStrings(std::vector<std::string>& strings,
 std::vector<std::string>& queries)
{
 std::sort(strings.begin(), strings.end());
 std::sort(queries.begin(), queries.end());

 std::unordered_map<std::string, int> counts;

 auto start = strings.begin();

 for (auto const& q : queries) {
     auto p = std::equal_range(start, strings.end(), q);
     counts[q] = p.second - p.first;
     start = p.second;
     }
     return counts;
}

So much cleaner than the original code! The complexity of both methods is dominated by the sorting so they are essentially equivalent for sufficiently large inputs, although the first method can really struggle if a sufficient proportion of the queries are not present in the vector of strings (especially if these are alphabetically minimum).

Comments

Post a Comment

Popular posts from this blog

Using the AVX instruction set to boost performance

-
Image
The AVX instruction set uses CPU registers to perform SIMD (Single Instruction Multiple Data) operations, which can be used to significantly speed up mathematical operations. I recently decided to create a digital filter in C++, and starting with the basics I came across a Finite Impulse Response (FIR) filter. Mathematically a FIR filter outputs a weighted sum of the most recent input values of the signal. The mathematics of a FIR filter are outlined  here . In practice, we typically work on sections of a signal. This is quite simply because we can not hold the entire signal in RAM. Consider the following signal which has been split into three chunks each of size 6,                                                        $$ [012123][123332][123342] $$ and the following filter $b = [1,2]$. In the routines discussed in this blog the a...
Read more

The magic behind deep learning : Obtaining gradients using reverse Automatic Differentiation.

-
Image
Every now and again a wave of rage washes over me when I hear someone (be it a news outlet, etc) refer to deep learning, and the like, as magic. Although, I must admit that I was a bit vague on how you can generate an error function given a network of nodes then minimise it without using numerical differentiation or providing the actual derivative (Although there are (totally) derivative-free minimisation methods such as Simplex etc.). The process of writing software for generating this error function (and a neural network) is not of my concern here, although it might be in a future blog post. What is of my concern is obtaining the gradient of this error function. Automatic Differentiation  First, lets discuss the process of obtaining the derivative of a expression that we already have the computation graph for . You will see that obtaining the computation graph is half the battle and many of the resources on the internet explaining Automatic Differentiation (AD) tend to brus...
Read more

Information Entropy

-
In the field of Information Theory, we can define the information conveyed $I(E)$ by the occurrence of an event $E$ as $$I(E) = \log \frac{1}{p(E)},$$ where $p(E)$ is the probability of the event $E$. Note that if the event is unlikely then the information gained is large. Suppose that we have an information source $X$, which can be thought of as a discrete random variable. $X$ can take on many "states" $\{x_i\}$. We can define the entropy of the system as $$H(X) = \sum_i^n  p(x_i)I(x_i),$$ where $n$ is the number of states that $X$ can take. An example of $X$ is an alphabet. A qualitative description of the entropy of an information source is a measure of its unpredictability. We can see this by observing the following: If the probabilities of the states of the source are uniform the entropy is maximised. That is, when we have no prior information about the likelihood of each state we expect the entropy of the information source to be large. We can prove this f...
Read more