std::map is a commonly used C++ container in problem solving. But careless use of map
can cause Time Limit Exceeded
in some cases.
See Example 1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
map<int, int>mp;
int main() {
for ( int i = 1; i <= N; i++ ) mp[i]++;
clock_t t = clock();
for ( int i = 1; i <= N; i++ ) {
if ( mp.find ( i ) != mp.end() ) {
// found
}
}
t = clock() - t;
printf ( "Time 1: %lf\n", ( double ) t / CLOCKS_PER_SEC );
t = clock();
for ( int i = 1; i <= N; i++ ) {
if ( mp[i] ) {
// found
}
}
t = clock() - t;
printf ( "Time 2: %lf\n", ( double ) t / CLOCKS_PER_SEC );
return 0;
}
In my computer Time 1: 0.420439
and Time 2: 0.420225
. They are almost same!
Now, Example 2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
map<int, int>mp;
int main() {
// for ( int i = 1; i <= N; i++ ) mp[i]++;
clock_t t = clock();
for ( int i = 1; i <= N; i++ ) {
if ( mp.find ( i ) != mp.end() ) {
// found
}
}
t = clock() - t;
printf ( "Time 1: %lf\n", ( double ) t / CLOCKS_PER_SEC );
printf ( "Size 1: %d\n", ( int ) mp.size() );
t = clock();
for ( int i = 1; i <= N; i++ ) {
if ( mp[i] ) {
// found
}
}
t = clock() - t;
printf ( "Time 2: %lf\n", ( double ) t / CLOCKS_PER_SEC );
printf ( "Size 2: %d\n", ( int ) mp.size() );
return 0;
}
Time 1: 0.055969
and Time 2: 0.779736
. Here, Time 2
is almost 15 times greater
than Time 1
.
Now, what's the difference?
In Example 1
we checked N
numbers where they were mapped and caused no time difference. But, in Example 2
N
numbers weren't mapped and caused a huge time difference. What's the reason behind this effect?
When we use std::map::find it searches the container for an element with a key equivalent to k and returns an iterator to it if found, otherwise it returns an iterator to map::end
.
But, on the other hand using std::map::operator : if k matches the key of an element in the container, the function returns a reference to its mapped value. If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value.
So, in Example 2
every time we are using mp[i]
, we are not only checking the existence of i
but also mapping it with a value (more formally with 0
).
In Example 2
we edited couple of extra lines to proof the above statements. This lines will show the size of the map after performing this operations.
We get Size 1: 0
and Size 2: 1000000
. Look at Size 2
, isn't it exactly N (number of values)
?
Finally, we come to real time experience. Solve this problem, 732E - Sockets from Codeforces Round 377 (Div. 2) with using two different techniques of mapping
and you will see the results.
Advance Sorry for your Time Limit Exceeded
and Congrats for Accepted
.
I got tle for problem 722D - Generating Sets for same reason. TLE and AC.
Thanks bro . :) will keep in mind in the coming contests . :)
It's not that shocking. How on earth would statement like
mp[i]++
work if the map didn't add the element in the map(if absent) before incrementing (like you did in the first example).Hi, just my two cents: I think it is much nicer to write
rather than
Of course this works with
std::set
s as well.Sorry in advance for your TLE if you are using multiset :'(
Recently faced the same issue in Div 4 but wasn't able to figure this out. Thanks for pointing out this so clearly