LeetCode 771 execution time comparison

CMakeLists.txt

cmake_minimum_required(VERSION 3.14)
project(prac_closure)

set(CMAKE_CXX_STANDARD 17)

add_executable(prac_closure main.cpp)

main.cpp

// LeetCode 771 performance comparison

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>    // std::shuffle
#include <map>
#include <chrono>

using namespace std;

void getRandVecWithoutDuplicate(int numMax, int Vec_len, std::vector<int> &Vec) {
    std::mt19937 rng(std::random_device{}());

    std::vector<int> tmpVec(numMax);
    std::iota(tmpVec.begin(), tmpVec.end(), 0);

    std::shuffle(tmpVec.begin(), tmpVec.end(), rng);
    std::copy(tmpVec.begin(), tmpVec.begin() + Vec_len, Vec.begin());
}

void init(std::vector<int> &J, int J_len, std::vector<int> &S, int S_len) {
    std::random_device dev;
    std::mt19937 rng(dev());
    int numMax = 1e3;
    std::uniform_int_distribution<std::mt19937::result_type> dist(1,numMax); // distribution in range [1, 10000]

    for(int i=0; i< S_len; i++) {
        S.push_back( dist(rng) );
    }

    getRandVecWithoutDuplicate(numMax, J_len, J);
}

int algo1(std::vector<int> &J, std::vector<int> &S) {
    int count = 0;
    for(auto& itS: S) {
        for(auto& itJ: J) {
            if(itS == itJ) {
                count++;
                break;
            }
        }
    }
    return count;
}

int algo2(std::vector<int> &J, std::vector<int> &S) {
    std::map<int, int> dict;
    for(auto& itS: S) {
        dict[itS]++;
    }
    int count = 0;
    for(auto& itJ: J) {
        count += dict[itJ];
    }
    return count;
}

int algo3(std::vector<int> &J, std::vector<int> &S) {
    std::map<int, int> dict;
    std::vector<int> Jcopy(J);
    std::cout << Jcopy.size();

    std::sort (Jcopy.begin(), Jcopy.end());

    int count = 0;
    for(auto& itS: S) {
        bool isFound = std::binary_search(Jcopy.begin(), Jcopy.end(), itS);
        if(isFound) {
            count++;
        }
    }
    return count;
}

int main(){
    int J_len = 1000;
    int S_len = 1e6;
    std::vector<int> J(J_len);
    std::vector<int> S;
    init(J, J_len, S, S_len);

    auto algo1_t1 = std::chrono::high_resolution_clock::now();
    int ans1 = algo1(J, S);
    auto algo1_t2 = std::chrono::high_resolution_clock::now();
    std::cout << "Ans1=" << ans1 << std::endl;

    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>( algo1_t2 - algo1_t1 ).count();
    std::cout << "Algo1 execution time: " << duration1 << " microseconds" << std::endl;

    auto algo2_t1 = std::chrono::high_resolution_clock::now();
    int ans2 = algo2(J, S);
    auto algo2_t2 = std::chrono::high_resolution_clock::now();
    std::cout << "Ans2=" << ans2 << std::endl;

    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>( algo2_t2 - algo2_t1 ).count();
    std::cout << "Algo2 execution time: " << duration2 << " microseconds" << std::endl;

    std::cout << "The execution time of Algo1 is " << double(duration1) / double(duration2) << " of Algo2 exec time." << std::endl;

    auto algo3_t1 = std::chrono::high_resolution_clock::now();
    int ans3 = algo3(J, S);
    auto algo3_t2 = std::chrono::high_resolution_clock::now();
    std::cout << "Ans3=" << ans3 << std::endl;

    auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>( algo3_t2 - algo3_t1 ).count();
    std::cout << "Algo3 execution time: " << duration3 << " microseconds" << std::endl;


    return 0;
}

result.txt

When J_len = 10

Ans1=9945
Algo1 execution time: 93636 microseconds
Ans2=9945
Algo2 execution time: 258378 microseconds
The execution time of Algo1 is 0.362399 of Algo2 exec time.

When J_len = 1000

Ans1=998970
Algo1 execution time: 3052571 microseconds
Ans2=998970
Algo2 execution time: 250028 microseconds
The execution time of Algo1 is 12.2089 of Algo2 exec time.
1000Ans3=998970
Algo3 execution time: 244847 microseconds