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 ?](https://stackoverflow.com/q/31816095/560648) — Asteroids With Wings, May 23 '20 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, May 23 '20 at 13:05
You could try to allocate memory first, this would probably increase your code speed — Juliano Negri, May 23 '20 at 13:10
Does the code work within the given time limit if you use `std::set` instead of `std::unordered_set`? — sepp2k, May 23 '20 at 13:29
In your example any container will be much faster than user input you are waiting. — metablaster, May 23 '20 at 13:37

Maxim Egorushkin · Accepted Answer · 2020-05-27T18:54:28.477

3

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';
}

edited May 27 '20 at 18:54

answered May 23 '20 at 13:19

Maxim Egorushkin

131,725
17
180
271

What if `a` is `INT_MAX`? This is only applicable if we know bounds on `a`. – Aykhan Hagverdili May 23 '20 at 13:21
You can create a bitset with 2^32 elements, it occupies 2^29 bytes, or 512MB. – Maxim Egorushkin May 23 '20 at 13:24
1

What if `a` is -1? :D – Aykhan Hagverdili May 23 '20 at 13:31
I appreciate the example. – Aykhan Hagverdili May 23 '20 at 13:42
We could use `std::bitset` instead of vector here, since the size is constexpr. – Aykhan Hagverdili May 23 '20 at 13:46
1

@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. – Maxim Egorushkin May 23 '20 at 14:26
This Code is giving Run time error (No Output).Whats the fix? – Devansh Messon May 26 '20 at 12:53
@DEVANSHMESSON It fails because it uses too much memory. Since the range of `a` is (1≤a≤10^9), a fix is `std::vector bitset(1000000001);` (Uses 8 times less memory). – Maxim Egorushkin May 26 '20 at 13:36
@MaximEgorushkin Can you expain this line: static_cast(a) – Devansh Messon May 26 '20 at 13:47
@DEVANSHMESSON It cast `int` to `unsigned`, because vector indexes are non-negative. Since your inputs are non-negative numbers, the cast is not really needed, but it doesn't hurt either because it compiles to 0 instructions. – Maxim Egorushkin May 26 '20 at 13:59
@MaximEgorushkin so if i have the input -3 and next input is 3. But static_cast(a) will convert -3 to 3 and this will be a problem because there will be two 3's and my answer will be wrong? – Devansh Messon May 26 '20 at 14:08
`-3` is going to be a large positive number when converted to `unsigned` in 2's-complement system (x86, ARM). This is why the original bitset size covered all `unsigned` values. – Maxim Egorushkin May 26 '20 at 14:11
Thank you so much sir @MaximEgorushkin.You Helped a lot! – Devansh Messon May 26 '20 at 14:30
@MaximEgorushkin i submitted the code to the online judge its giving TLE for all test cases.Any reason for it? – Devansh Messon May 26 '20 at 14:36
@DEVANSHMESSON Post a link to the online judge and I will have a look. – Maxim Egorushkin May 27 '20 at 09:35
Link - https://cses.fi/problemset/result/474865/ @MaximEgorushkin But i think you not be able to see that result Its just showing TLE for all test cases thats it – Devansh Messon May 27 '20 at 15:44
@DEVANSHMESSON Added another version for you. – Maxim Egorushkin May 27 '20 at 15:53
1

Thank you so much @MaximEgorushkin.All Test Cases Passed(AC).You're genius.I learned a new technique! – Devansh Messon May 27 '20 at 16:15
@DEVANSHMESSON That grader is a bit too strict, IMO. – Maxim Egorushkin May 27 '20 at 16:17
Thats why i am practicing there.But i wanna ask why that previous code exceeded time limit? @MaximEgorushkin – Devansh Messon May 27 '20 at 16:21
@MaximEgorushkin Can You solve this- https://stackoverflow.com/questions/62048413/how-to-code-to-have-upper-bound-of-second-element-of-vector-pair-based-on-first – Devansh Messon May 27 '20 at 21:01

Avneet Singh · Answer 2 · 2020-05-23T13:39:13.003

1

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.

edited May 23 '20 at 13:39

answered May 23 '20 at 13:13

Avneet Singh

43
5

2

You mean O(1) instead of O(n)? O(n) insert is the worst case. [cppreference](https://en.cppreference.com/w/cpp/container/unordered_map/insert) – Aykhan Hagverdili May 23 '20 at 13:20

Juliano Negri · Answer 3 · 2020-05-23T13:22:47.217

1

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.

edited May 23 '20 at 13:22

answered May 23 '20 at 13:16

Juliano Negri

299
2
9

How can i allocate memory first ? – Devansh Messon May 26 '20 at 12:54

Why/Are unordered_map and unordered_set slower?

My Question is:

3 Answers3