Why/Are unordered_map and unordered_set slower?

Question

I was solving a simple problem of finding unique elements in an array. I used a std::unordered_map to count unique elements but it gave Time Limit Exceeded in one test case. Then I used a std::unordered_set with the same result.

PS: I used std::unordered_map and std::unordered_set because I read that these two are much much faster than std::map and std::set respectively.

#include<bits/stdc++.h> using namespace std; int main() { int n, a; cin >> n; unordered_set<int> s; for(int i = 0; i < n; i++) { cin >> a; s.insert(a); } cout << s.size(); }

Test 7 exceeded the time limit.

My Question is:

If std::unordered_map and std::unordered_set are faster why did they give TLE?

Recommended reading: Why should I not #include <bits/stdc++.h>? — Asteroids With Wings
– Asteroids With Wings, Commented May 23, 2020 at 13:01
std::unordered_map and utd::unordered_set are not inherently faster. Nothing is just "magic speed" in programming. You have to know how and when to use what. — Aykhan Hagverdili
– Aykhan Hagverdili, Commented May 23, 2020 at 13:05
You could try to allocate memory first, this would probably increase your code speed — Juliano Negri
– Juliano Negri, Commented May 23, 2020 at 13:10
In your example any container will be much faster than user input you are waiting. — metablaster
– metablaster, Commented May 23, 2020 at 13:37

Maxim Egorushkin · Accepted Answer · 2020-05-27 18:54:28Z

std::unordered_set<int> is a node-based container, where each element is stored in separately allocated list node. The list node contains an int element and two list node pointers, which, on a 64-bit platform, makes each list node occupy 24 bytes due to alignment. There is also allocator overhead for each allocated chunk of memory (8 bytes for GNU libc), so that there is at least 28 bytes of overhead for each 4-byte int element.

s.insert(a); makes a memory allocation for each new element and that is what makes the code slow.

To solve this problem efficiently you can use a bitset indexed by the integers, e.g. std::vector<bool>. Set the bit to 1 for each read integer and then count the number of set bits. If the elements are signed, covert them to unsigned to make the bit index a non-negative number.

A working example:

#include <vector> #include <iostream> #include <numeric> #include <limits> int main() { int n; std::cin >> n; std::vector<bool> bitset(1000000001); // a range is 1≤a≤10^9. for(int i = 0, a; i < n; ++i) { std::cin >> a; bitset[static_cast<unsigned>(a)] = true; } std::cout << std::accumulate(bitset.begin(), bitset.end(), 0u) << '\n'; }

A version that passes that grader:

#include <bitset> #include <iostream> #include <numeric> #include <limits> int main() { int n; std::cin >> n; std::bitset<1000000001> bitset; // a range is 1≤a≤10^9. unsigned unique = 0; for(int i = 0, a; i < n; ++i) { std::cin >> a; if(!bitset.test(a)) { ++unique; bitset.set(a); } } std::cout << unique << '\n'; }

What if a is INT_MAX? This is only applicable if we know bounds on a.
You can create a bitset with 2^32 elements, it occupies 2^29 bytes, or 512MB.
@Ayxan std::bitset stores elements inline (not in dynamically allocated memory). std::bitset with 2^32 bits would take 512MB on the stack, which your platform may not support. For example, on Linux, the default maximum stack size is around 8MB.
Thank you so much @MaximEgorushkin.All Test Cases Passed(AC).You're genius.I learned a new technique!

Juliano Negri · Accepted Answer · 2020-05-23 13:22:47Z

The unordered containers are optimized for retrieving values, not for inserting them.

You could take a look at this comparison https://medium.com/@nonuruzun/stl-container-performance-3ec5a8fbc3be. There, you can see that the unordered containers have the O(N) worst case for inserting while the ordered ones have O(log(N))

But you can fix that by allocating memory first, so you will have less collisions.

Avneet Singh · Accepted Answer · 2020-05-23 13:39:13Z

std::unordered_map gives result in o(1) most of the time , not always . Coming to the TLE issue , there might be a possibility that constraints are more than 10^18 and in this case o(n) complexity will not work . Try o(log(n)) approach.

You mean O(1) instead of O(n)? O(n) insert is the worst case. cppreference

Collectives™ on Stack Overflow

Why/Are unordered_map and unordered_set slower?

My Question is:

3 Answers 3

21 Comments

1 Comment

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

My Question is:

3 Answers 3

21 Comments

1 Comment

1 Comment

Linked

Related