Skip to content

Instantly share code, notes, and snippets.

@HTLife
Last active August 8, 2019 05:28
Show Gist options
  • Save HTLife/432f0217b7eb161ef0458c36c1357427 to your computer and use it in GitHub Desktop.
Save HTLife/432f0217b7eb161ef0458c36c1357427 to your computer and use it in GitHub Desktop.
LeetCode 771 execution time comparison
cmake_minimum_required(VERSION 3.14)
project(prac_closure)
set(CMAKE_CXX_STANDARD 17)
add_executable(prac_closure 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;
}
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment