C++ 9ms vs. 16ms


  • 0
    M

    I thought the latter solution is faster since I use reference for vector elements and that I don't access to hash elements each time with [], but it turned out to be different.
    Does anyone know why?

    9ms solution

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            unordered_map<int, bool> counter;
            for (auto num1 : nums1) {
                counter[num1] = true;
            }
            vector<int> result;
            for (auto num2 : nums2) {
                if (counter.find(num2) != counter.end()) {
                    if (counter[num2]) {
                        result.push_back(num2);
                        counter[num2] = false;
                    }
                }
            }
            return result;
        }
    

    16ms solution

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            unordered_map<int, bool> counter;
            for (auto num1 : nums1) {
                counter[num1] = true;
            }
            vector<int> result;
            for (const auto& num2 : nums2) {
                auto iter = counter.find(num2);
                if (iter != counter.end()) {
                    if (iter->second) {
                        result.push_back(num2);
                        iter->second = false;
                    }
                }
            }
            return result;
        }
    

  • 1
    J

    I think creating the new iterator each time in the second loop taxes your registers.

    While looking at the code it looks like very similar code, however in the first version you don't store the iterator, so the jump determination is done without register swaps. I'd have to look at the Asm to be sure but that's my guess.

    I haven't taken a compilers course yet so I'm not sure if the compiler would optimize them out to the same, or what -O options leetcode defaults to.

    auto iter = counter.find(num2); //culprit
    

  • 0
    M

    @jbrennan3 Right...! Thanks :)


Log in to reply
 

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