Improving runtime by preventing a hashtable from growing

[Paul]

I solved the following problem:
Given a sequence in the form of a vector<int> and a non-negative integer r,
find the length of the longest subsequence which has range <= r.
By "range", I mean the stats definition of max - min.

The code is below.
I solved it by hashing as this is much faster than sorting for long vectors.
(I tested for vectors of size >= 10 million).
I am particularly interested in small r, and the most interesting case to
me is r == 1 because that case was given to me as part of a job interview
process many years ago.

I was advised that the relevant hashtables should not be allowed to grow
by introducing a new element when the key is not present.
However, when I decommented the below line to prevent the hashtable
growing, I saw no change in performance.
Should the commented code be commented or decommented?
Any other feedback is welcome, too.

Many thanks.

Paul Epstein

/* CODE BELOW ******************************************************/

int hashLongest(const std::vector<int>& vec, int r)
{
// For each int in the vector, count how many times it occurs.
std::unordered_map<int, int> allCounts;

for (int v : vec)
++allCounts[v];

// For each int k in the vector, count how many values of x occur
// such that x >= k and x <= k + r
std::unordered_map <int, int> leftCounts;

for (auto a : allCounts)
for (int i = 0; i <= r; ++i)
if ((long long)a.first + i > INT_MAX)
break;
else // if (allCounts.find(a.first + i) != allCounts.end())
leftCounts[a.first] += allCounts[a.first + i];

// The maximum value of leftCounts is the result
int Max = 0;
for (auto x : leftCounts)
Max = std::max(Max, x.second);

return Max;
}

[Jorgen Grahn]

On Fri, 2019-11-22, Paul wrote:
> I solved the following problem:
> Given a sequence in the form of a vector<int> and a non-negative integer r,
> find the length of the longest subsequence which has range <= r.
> By "range", I mean the stats definition of max - min.

Surely that problem must be possible to express in a more
understandable way. What does "the stats definition of max - min"
mean? What does "stats" mean, for that matter?

Since max(subseq) <= max(seq) and min(subseq) >= min(seq), it seems to
me the answer is always "the full sequence" or "there isn't one".

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paul]

On Saturday, November 23, 2019 at 9:38:42 AM UTC, Jorgen Grahn wrote:
> On Fri, 2019-11-22, Paul wrote:
> > I solved the following problem:
> > Given a sequence in the form of a vector<int> and a non-negative integer r,
> > find the length of the longest subsequence which has range <= r.
> > By "range", I mean the stats definition of max - min.
>
> Surely that problem must be possible to express in a more
> understandable way. What does "the stats definition of max - min"
> mean? What does "stats" mean, for that matter?
>
> Since max(subseq) <= max(seq) and min(subseq) >= min(seq), it seems to
> me the answer is always "the full sequence" or "there isn't one".

Thanks for your interest.
The answer depends on both the vector and r.
The vector can be considered as a sequence with vec[0], vec[1] being the
first two terms for example.
As a sequence it has lots of subsequences.
Consider all the subsequences S which have the property that max(S) - min(S) <= r.
The problem is to find the maximum length of S for all subsequences S which
have that property.

Another way to say it is that we want the maximum length of all subsequences
with range <= r.
However, that might be confusing because there's a set-theoretic definition
of "range" and a statistical definition of "range" and these definitions
are very different. I mean the statistical definition of "range".

Paul Epstein

[Paul]

As an example, remember that my function is called hashLongest
hashLongest({2,1,3,1}, 1) = 3. [2, 1 ,1] is a subsequence which has
range 1. That subsequence has length 3. If any subsequence has range <=1
then its length will always be <= 3. That is why 3 is the answer for this example.

Paul

[Öö Tiib]

On Friday, 22 November 2019 19:31:22 UTC+2, Paul wrote:
> I solved the following problem:
> Given a sequence in the form of a vector<int> and a non-negative integer r,
> find the length of the longest subsequence which has range <= r.
> By "range", I mean the stats definition of max - min.
>
> The code is below.
> I solved it by hashing as this is much faster than sorting for long vectors.
> (I tested for vectors of size >= 10 million).

Perhaps your vectors were biased to have only narrow
range of integers in those and searched for ranges were very low (like
1 or 2) otherwise your solution is clearly sub-optimal solution of the
given problem.

The std::sort of vector of 10 millions of really random integers
tends to be about twice faster than counting equal elements of it into
hash table. Also searching for longest subsequence in sorted vector is
O(length) linear while your search from hashtable is O(length*range)
rectangular.

[Paul]

Thanks for your interest.
My experimental results don't agree with your post.
***However, there is definitely the possibility that my testing is flawed.***
Accordingly, I will post my entire code, including testing.
I will report the results for r = 100 although many other values of r
give similar results.

The vector has a size of 100 million.
It is generated by 100 million calls to std::rand().
The sorting algorithm code and hashtable code will be posted below.
The two algorithms were tested against the same vector.
The longest subsequence with a range of <= 100 had length 310012
The hashing algorithm took 2.4 seconds and the sorting algorithm
took 8.3 seconds.
The IDE was a free version of Visual Studio

// ************************ ALGOS AND TEST ******************************
// Given a sequence expressed as a vector, and given a non-negative integer r:
// Find the maximum length of all subsequences which have a range <= r.
// range is defined to be the maximum - minimum as in statistics.
// This solution should have O(rN)
// Originally, this was in a coding test with r = 1.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <utility>
#include <climits>

int hashLongest(const std::vector<int>& vec, int r)
{
// For each int in the vector, count how many times it occurs.
std::unordered_map<int, int> allCounts;

for (int v : vec)
++allCounts[v];

// For each int k in the vector, count how many values of x occur
// such that x >= k and x <= k + r
std::unordered_map <int, int> leftCounts;

// The maximum value of leftCounts is the result

int Max = 0;
for (auto a : allCounts)
{
for (int i = 0; i <= r; ++i)
if ((long long)a.first + i > INT_MAX)
break;
else // if (allCounts.find(a.first + i) != allCounts.end())
leftCounts[a.first] += allCounts[a.first + i];

Max = std::max(Max, leftCounts[a.first]);
}

return Max;
}

// Previous sorting approach to solve the same problem.
// length is continually incremented.
int sortLongest(std::vector<int>& vec, int r)
{
std::sort(vec.begin(), vec.end());
int length = 0;
for (int behind = 0; behind < vec.size(); ++behind)
{
int ahead = behind + length; // Maximal length uncovered so far.
// After sorting, see if lower point of the maximal length subinterval is within r of the uppermost point
// If so we can extend the length and move to the next point for testing.
while (ahead < vec.size() && (long long)vec[behind] + r >= vec[ahead])
++ahead, ++length;
}
return length;
}

// Randomly generate a testing vector
// Default to a length of ten million.
std::vector<int> generate(int length = 100'000'000)
{
std::vector<int> vec(length);
for (int& i : vec)
i = std::rand();

return vec;
}

// A given vector is tested using either the sorting method
// or the hashing method.
// A bool is true for the hashing method and false otherwise.
// Returned is a pair whose first value is the maximum length
// according to the problem constraints, and whose second value
// is the number of microseconds taken.
std::pair<int, int> longest(std::vector<int>& vec, int r, bool hash)
{
auto start = std::chrono::high_resolution_clock::now();
int maxLength = hash ? hashLongest(vec, r) : sortLongest(vec, r);
auto stop = std::chrono::high_resolution_clock::now();
int time = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
return { maxLength, time };
}


// A display function to display the information from a run
void display(bool hash, std::pair<int, int> info, int length = 10'000'000, int r = 1)
{
std::cout << "Experiment done on a randomly generated vector of length " << length;
std::cout << "\nAn attempt was made to find the maximum length of a subsequence of range " << r;
std::cout << "\nThe method used was " << (hash ? "hashing" : "sorting");
std::cout << "\nThe result is " << info.first << " and the time taken in microseconds is " << info.second << std::endl;
}

// Test both methods.
int main()
{
std::vector<int> vec = generate();

std::pair<int, int> hashResult = longest(vec, 100, true);
display(true, hashResult, vec.size(), 100);

std::pair<int, int> sortResult = longest(vec, 100, false);
display(false, sortResult, vec.size(), 100);

}

[Öö Tiib]

On Sunday, 24 November 2019 01:02:33 UTC+2, Paul wrote:
> On Saturday, November 23, 2019 at 10:20:57 PM UTC, Öö Tiib wrote:
> > On Friday, 22 November 2019 19:31:22 UTC+2, Paul wrote:
> > > I solved the following problem:
> > > Given a sequence in the form of a vector<int> and a non-negative integer r,
> > > find the length of the longest subsequence which has range <= r.
> > > By "range", I mean the stats definition of max - min.
> > >
> > > The code is below.
> > > I solved it by hashing as this is much faster than sorting for long vectors.
> > > (I tested for vectors of size >= 10 million).
> >
> > Perhaps your vectors were biased to have only narrow
> > range of integers in those and searched for ranges were very low (like
> > 1 or 2) otherwise your solution is clearly sub-optimal solution of the
> > given problem.
> >
> > The std::sort of vector of 10 millions of really random integers
> > tends to be about twice faster than counting equal elements of it into
> > hash table. Also searching for longest subsequence in sorted vector is
> > O(length) linear while your search from hashtable is O(length*range)
> > rectangular.
>
> Thanks for your interest.
> My experimental results don't agree with your post.
> ***However, there is definitely the possibility that my testing is flawed.***

Note that 100 millions and 10 millions are different counts.
Also the randomness can be biased, IIRC then RAND_MAX was 32767 in
some Visual Studio. What it is in yours? With such tiny RAND_MAX
the winner algorithm would count into
std::array<int,RAND_MAX+1> allCounts; hash table is wasteful there.

[Bonita Montero]

> The std::sort of vector of 10 millions of really random integers
> tends to be about twice faster than counting equal elements of it

> into hash table. ...

LOL.

[Öö Tiib]

On Sunday, 24 November 2019 01:02:33 UTC+2, Paul wrote:
>

> Thanks for your interest.

Can you report results of that on your platform:

#include <algorithm> // generate and sort
#include <chrono> // chrono
#include <iostream> // cout
#include <random> // random_device and mt19937
#include <unordered_map> // unordered_map
#include <vector> // vector

// note that std::random_device does nothing good on lot of platforms
// here it is just used for toy example that it is
static std::random_device rnd_device;
static std::mt19937 engine {rnd_device()};
static std::uniform_int_distribution<int> dist {0, INT_MAX};

int gen()
{
return dist(engine);
};


size_t hashcount(const std::vector<int>& vec)

{
// For each int in the vector, count how many times it occurs.
std::unordered_map<int, int> allCounts;

for (int v : vec)
++allCounts[v];

return allCounts.size();
}

int main()
{
std::vector<int> vec(10000000);
std::generate(begin(vec), end(vec), gen);

auto t1 = std::chrono::high_resolution_clock::now();
hashcount(vec);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "hash " << std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count() << " ";

std::vector<int> vec2(10000000);
std::generate(begin(vec2), end(vec2), gen);

t1 = std::chrono::high_resolution_clock::now();
std::sort(begin(vec2),end(vec2));
t2 = std::chrono::high_resolution_clock::now();
std::cout << "sort " << std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count() << " ";

return 0;
}

[Paul]

Yes, I too was very surprised by this claim, and my initial surprise
is backed up by my experiment. I didn't feel confident enough to
challenge the claim so directly, though.

Paul

[Paul]

I started testing with a length of 10 million and tested with
a length of 100 million at a later stage.
Carelessly, I didn't update the comments and all defaults to reflect
this change but this is basically a documentation error.

RAND_MAX is indeed 32767 in my version of Visual Studio.
My intent is to treat the processes of testing the algos and designing the
algos as separate.
The vector generation with std::rand() is part of the testing, not
part of the algorithm.
Changing allCounts as you suggest would tie the algorithms to the testing.
In test driven development, people do indeed tie the algorithms to the
testing.
But I don't want to do it that way.
The algorithms should be independent of the methods used to test them.

Paul

[Öö Tiib]

Then use random engines like std::mt19937 for generating test data.
These behave more similarly between platforms than std::rand and
so avoid confusion. Usage of std:rand with so low max and cycle size
does cause odd artifacts and effects so people do avoid it
even for dice rolling in entertainment.

[Öö Tiib]

Note also that the claim keeps being true and your experiments used
narrow range of test values like I predicted.

[Paul]

Good advice, here.
Thanks.

Paul

[Paul]

Yes, your claim is vindicated by your code that I tested on my platform
as requested.
I will report the results in my reply to the post of yours that contains
your code.

Paul

[Paul]

The console output was hash 5559216 sort 1263252
which vindicates your initial response.

It's an interesting example of big O analysis not being the whole story.
Although sorting is O(n * log (n) ), sorting seems best in this context
even though linear methods are available.

Paul

[Paul]

On Sunday, November 24, 2019 at 11:26:13 AM UTC, Öö Tiib wrote:

The line allCounts.reserve(vec.size()); gives a significantly improved
performance.
But this basically means that hashing becomes 3 times slower than sorting
instead of 4 times slower.

Paul

[Bonita Montero]

On my old Ryzen 7 1800X, sorting of 10'000'000 integters takes more
than twice the time than counting with VC++2019 and nearly twice the
time than counting with g++.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;
using namespace chrono;

int main()
{
size_t const N_ELEMENTS = 10'000'000;
random_device rd;
uniform_int_distribution<int> uid( numeric_limits<int>::min(),
numeric_limits<int>::max() );
vector<int> v;
unordered_set<int> s( N_ELEMENTS );
time_point<high_resolution_clock> start;
double seconds;
v.resize( N_ELEMENTS );
for( int &e : v )
e = uid( rd ),
s.insert( e );
start = high_resolution_clock::now();
size_t uniq = 0;
for( unordered_set<int>::iterator it = s.begin(); it != s.end(); )
{
++uniq;
int e = *it++;
for( ; it != s.end() && *it == e; ++it );
}
seconds = duration_cast<nanoseconds>( high_resolution_clock::now()
- start ).count() / 1.0E9;
cout << "unique elements: " << uniq << endl;
cout << "time to count: " << seconds << "s" << endl;
start = high_resolution_clock::now();
sort( v.begin(), v.end() );
seconds = duration_cast<nanoseconds>( high_resolution_clock::now()
- start ).count() / 1.0E9;
cout << "time to sort: " << seconds << "s" << endl;
}

And I reserved as equal buckets a there are values, which should speed
up counting anyway.

[Paul]

Thanks for this.
But your code seems to lose the context of the original task.
Fix r and fix a vector.
The task is to find the size of the largest subsequence of the vector
so that the range of that subsequence <= r.
As far as I know, non-sorting methods need to maintain a correspondence
in the form of key-value pairs {v, number of occurrences of v}
This is why Oo (sorry but I don't know how to create the diacritical marks)
and I both used unordered_map instead of unordered_set.
I am not surprised that unordered_set operations are quicker.

Oo's comment about relative speeds of hashing/sorting should be understood
in the context of the entire thread -- I don't think that he or she
intended the comment to be read as a standalone.

Paul

[Bonita Montero]

> But your code seems to lose the context of the original task.

I only wanted to falsify Öö Tiib statement.

[Paul]

On Sunday, November 24, 2019 at 2:42:43 PM UTC, Bonita Montero wrote:
> > But your code seems to lose the context of the original task.
>
> I only wanted to falsify Öö Tiib statement.

It's very easy (and IMO silly) to falsify statements by ignoring the context, as you did.
Example: A. "I prefer white wine to red wine."
B. "Not me. I only ever drink red wine."
C, after observing B taking ibuprofen pills with water:
"B said 'I only ever drink red wine, but I've just seen B drinking water.
B is a liar."

Paul

[Bonita Montero]

>> I only wanted to falsify Öö Tiib statement.

> It's very easy (and IMO silly) to falsify statements by ignoring the context, as you did.

I didn't respond to the OP but to Öö Tiib.
And at this place my response was in the correct context.

[Jorgen Grahn]

On Sat, 2019-11-23, Paul wrote:
> On Saturday, November 23, 2019 at 9:38:42 AM UTC, Jorgen Grahn wrote:
>> On Fri, 2019-11-22, Paul wrote:
>> > I solved the following problem:
>> > Given a sequence in the form of a vector<int> and a non-negative integer r,
>> > find the length of the longest subsequence which has range <= r.
>> > By "range", I mean the stats definition of max - min.
>>
>> Surely that problem must be possible to express in a more
>> understandable way. What does "the stats definition of max - min"
>> mean? What does "stats" mean, for that matter?
>>
>> Since max(subseq) <= max(seq) and min(subseq) >= min(seq), it seems to
>> me the answer is always "the full sequence" or "there isn't one".

I see now that I misread a part of your problem definition that /was/
clear. I read "... longest subsequence which has range >= r" which
led to the uninteresting problem.

Sorry! I must have been half asleep, or something.

> Thanks for your interest.
> The answer depends on both the vector and r.
> The vector can be considered as a sequence with vec[0], vec[1] being the
> first two terms for example.
> As a sequence it has lots of subsequences.
> Consider all the subsequences S which have the property that max(S) - min(S) <= r.
> The problem is to find the maximum length of S for all subsequences S which
> have that property.
>
> Another way to say it is that we want the maximum length of all subsequences
> with range <= r.
> However, that might be confusing because there's a set-theoretic definition
> of "range" and a statistical definition of "range" and these definitions
> are very different. I mean the statistical definition of "range".

Ah, ok. I was unaware of "stats" as an abbreviation of "statistics"
(not that I remember how "range" is used in statistics anyway). It
would have been easier to explain it as "range(seq) = max(seq) -
min(seq)".

Anyway: I know understand the problem and see why it's fun/interesting to
solve.

[Jorgen Grahn]

> Anyway: I [now] understand the problem and see why it's fun/interesting to
> solve.

But reading the other postings, I realize I don't understand it after all.

To me a subsequence is obviously ... well, like this:

A sequence [c, d) is a subsequence of [a, b) if it's a valid sequence
and if both c and d are in [a, b].

So the subsequences of ABC are A, B, C, AB, BC, ABC and "".

You seem to have a definition of subsequence where order doesn't
matter; your implementation took a vector<int> as input, but you
immediately discarded the ordering, as if the function had taken a
multi_set<int>.

Apologies for forking the thread and not discussing your code, but I
believe in clearly stating problems. It almost always pays off.

[Paul]

No apologies needed. I agree that the problem needs to be understood
first. "Subsequence" is more of a pure maths concept than a computer
science concept.
Suppose X is a given sequence.
A subsequence of X means a sequence that can be obtained as follows.
The first term s_0 can be any term of X.
The second term s_1 can be any term of X which occurs later in
X (larger index) than s_0.
The third term s_2 can be any term with a larger index in X than s_1 etc.

The subsequences of ABC are therefore:
""
A
B
C
AB
AC
BC
ABC

This is indeed different to your definition.
You seem to have in mind a subarray rather than a subsequence.
It is correct that, for this particular problem, the result is
always the same for any reordering of the vector.

However, it is not at all true that the subsequences of X are always
the same as the subsequences of a rearrangement of X.

In the ABC example above, AC is a subsequence. However, AC is
not a subsequence of BCA.
It's because we are only interested in the length that we can reorder
if we want.

Paul Epstein

[Öö Tiib]

Bonita is just trolling and so is best to ignore.

I don't know how what I wrote can be interpreted as "count unique
elements in unordered set in rather nonsensical way". AFAIK
unordered_set::size already is required to return that in O(1) and
it was no way under discussion.

[Jorgen Grahn]

On Sun, 2019-11-24, Paul wrote:
> On Sunday, November 24, 2019 at 4:29:28 PM UTC, Jorgen Grahn wrote:

...

I don't think it's /my/ definition, but the one that most programmers
would take for granted, at least in C++. Although it may be more
common to talk in terms of "range" and "subrange".

> You seem to have in mind a subarray rather than a subsequence.

I don't think I've heard the term "subarray" before.

Anyway, the bottom line is: you needed to define (or avoid) that term.

[Öö Tiib]

Wikipedia seems to agree with Paul:
https://en.wikipedia.org/wiki/Subsequence
The subsequence should not be confused with substring ⟨ A , B , C , D ⟩
which can be derived from the above string ⟨ A , B , C , D , E , F ⟩
by deleting substring ⟨ E , F ⟩. The substring is a refinement of
the subsequence.

[Bonita Montero]

> Bonita is just trolling and so is best to ignore.
> I don't know how what I wrote can be interpreted as "count unique
> elements in unordered set in rather nonsensical way". AFAIK
> unordered_set::size already is required to return that in O(1) and
> it was no way under discussion.

Sorry, I've confused set and multiset.
But even when having changed the code I can falsify your claim:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;
using namespace chrono;

int main()
{
size_t const N_ELEMENTS = 10'000'000;
random_device rd;
uniform_int_distribution<int> uid( numeric_limits<int>::min(),
numeric_limits<int>::max() );
vector<int> v;

unordered_multiset<int> s( N_ELEMENTS );

time_point<high_resolution_clock> start;
double seconds;
v.resize( N_ELEMENTS );
for( int &e : v )
e = uid( rd ),
s.insert( e );
start = high_resolution_clock::now();
size_t uniq = 0;

for( unordered_multiset<int>::iterator it = s.begin(); it != s.end(); )

{
++uniq;
int e = *it++;
for( ; it != s.end() && *it == e; ++it );
}
seconds = duration_cast<nanoseconds>(high_resolution_clock::now() -

start).count() / 1.0E9;

cout << "unique elements: " << uniq << endl;
cout << "time to count: " << seconds << "s" << endl;
start = high_resolution_clock::now();
sort( v.begin(), v.end() );
seconds = duration_cast<nanoseconds>(high_resolution_clock::now() -

start).count() / 1.0E9;

cout << "time to sort: " << seconds << "s" << endl;
}

The difference between sorting and counting remains almost the same.
I think the mutltiset doesn't really maintain linked buckets but just
has a counter for duplicate values on each bucket. So that's a good
explanation why the runtime of the modified code is so close to the
old code.

[Bonita Montero]

Sorry, I've drunken half a bolttle of chery-liqueur.
Better write tomorrow again.

[Paul]

The word "subsequence" is analogous to the word "pi" (when that word is
used in its mathematical sense). There's no matter of opinion or
ambiguity about what either of these words mean. I'd be very surprised if you
can find any definition of "subsequence" that is different from what I
said. However, as you say, many people are misinformed about these terms.
Many people think that pi is exactly 3.14 and many people think that
terms of a subsequence need to be contiguous.

So it seems wrong to say that I "needed" to define that term.
There's nothing to prevent interested people looking it up, and
it is _not_ the case that different references say different things.

Paul