C++ unordered_set is so much slower than vector


  • 0
    A

    Completely same code.
    If I use unordered_set, although I have the advantage of removing used edges to reduce iteration time in next loop, the performance isn't satisfactory at all.

    66 / 66 test cases passed
    Status: Accepted
    Runtime: 169 ms
    Beats 35.44%

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n < 2) return vector<int>(n);
            vector<unordered_set<uint>> neighbor(n);
            vector<uint> degree(n, 0);
            vector<uint> leaf(n);
            vector<uint>::iterator p = leaf.begin(), q = p, e = leaf.end();
            for (auto& i : edges) {
                neighbor[i.first].insert(i.second);
                neighbor[i.second].insert(i.first);
                degree[i.first]++;
                degree[i.second]++;
            }
            for (uint i = 0; i < n; i++) {
                if (degree[i] < 2) *(p++) = i;
            }
            while (p != e) {
                for (auto qq = p ; q != qq; q++) {
                    for (uint nbr : neighbor[*q]) {
                        neighbor[nbr].erase(*q);
                        if (degree[nbr]-- == 2) *(p++) = nbr;
                    }
                }
            }
            return vector<int>(q, e);
        }
    };
    

    Then if I use vector, which means I can't easily remove used edges, so there should be quite a few redundant loops, yet I get a huge unexpected performance boost.

    66 / 66 test cases passed
    Status: Accepted
    Runtime: 66 ms
    Beats 99.18%

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n < 2) return vector<int>(n);
            vector<vector<uint>> neighbor(n);
            vector<uint> degree(n, 0);
            vector<uint> leaf(n);
            vector<uint>::iterator p = leaf.begin(), q = p, e = leaf.end();
            for (auto& i : edges) {
                neighbor[i.first].push_back(i.second);
                neighbor[i.second].push_back(i.first);
                degree[i.first]++;
                degree[i.second]++;
            }
            for (uint i = 0; i < n; i++) {
                if (degree[i] < 2) *(p++) = i;
            }
            while (p != e) {
                for (auto qq = p ; q != qq; q++) {
                    for (uint nbr : neighbor[*q]) {
                        if (degree[nbr]-- == 2) *(p++) = nbr;
                    }
                }
            }
            return vector<int>(q, e);
        }
    };
    

    I suspect it is due to the fact when the number of nodes grows, the collisions happen so frequent that unordered_set degenerates from O(1) to O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.