fork(2) download
copy 
  1. #include <chrono>
  2. #include <iostream>
  3. #include <random>
  4. #include <set>
  5. #include <unordered_set>
  6. #include <vector>
  7. #include <algorithm>
  8.  
  9. using namespace std::chrono;
  10.  
  11. int main() {
  12.  
  13.     // Setup 1: Construct two vectors with random integers.
  14.     constexpr size_t num = 100000;
  15.  
  16.     std::random_device rd;
  17.     std::mt19937 gen(rd());
  18.     std::uniform_int_distribution<> dis(0, num);
  19.  
  20.     std::vector<int> random_vec_1;
  21.     std::vector<int> random_vec_2;
  22.     random_vec_1.reserve(num);
  23.     random_vec_2.reserve(num);
  24.     for (size_t i = 0u; i < num; ++i) {
  25.         random_vec_1.push_back(dis(gen));
  26.         random_vec_2.push_back(dis(gen));
  27.     }
  28.     // Setup 2: Make elements unique.
  29.     std::set<int> s1(random_vec_1.begin(), random_vec_1.end());
  30.     std::set<int> s2(random_vec_2.begin(), random_vec_2.end());
  31.     random_vec_1.assign(s1.begin(), s1.end());
  32.     random_vec_2.assign(s2.begin(), s2.end());
  33.  
  34.     std::random_shuffle(random_vec_1.begin(), random_vec_1.end());
  35.     std::random_shuffle(random_vec_2.begin(), random_vec_2.end());
  36.  
  37.     std::cout << "size random_vec_1: " << random_vec_1.size() << "\n";
  38.     std::cout << "size random_vec_2: " << random_vec_2.size() << "\n";
  39.  
  40. {
  41.     auto begin1 = high_resolution_clock::now();
  42.  
  43.     // Solve problem -------------------------------------------
  44.     std::vector<int> new_vec_1(random_vec_1);
  45.     std::sort(std::begin(new_vec_1), std::end(new_vec_1));
  46.     std::vector<size_t> match_index_2;
  47. 	match_index_2.reserve(random_vec_2.size());
  48.  
  49.     for (size_t i = 0; i < random_vec_2.size(); ++i) {
  50.     	if (std::binary_search(std::begin(new_vec_1), std::end(new_vec_1),
  51.     		                   random_vec_2[i])) {
  52.             match_index_2.push_back(i);
  53.   		}
  54.     }
  55.     // ---------------------------------------------------------
  56.  
  57.     auto end1 = high_resolution_clock::now();
  58.     auto ticks1 = duration_cast<microseconds>(end1-begin1);
  59.     std::cout << "Vector 1 approach took " << ticks1.count() << " microseconds.\n";
  60.     std::cout << "Number of common indices: " << match_index_2.size() << "\n";
  61.  
  62. }
  63.  
  64. {
  65.     auto begin1 = high_resolution_clock::now();
  66.  
  67.     // Solve problem -------------------------------------------
  68.     std::vector<int> new_vec_1(random_vec_1);
  69.     std::vector<int> new_vec_2(random_vec_2);
  70.     std::sort(std::begin(new_vec_1), std::end(new_vec_1));
  71.     std::sort(std::begin(new_vec_2), std::end(new_vec_2));
  72.     std::vector<size_t> match_index_2;
  73. 	match_index_2.reserve(random_vec_2.size());
  74.  
  75.     for (auto it1 = new_vec_1.begin(), it2 = new_vec_2.begin();
  76.     	 it1 != new_vec_1.end() && it2 != new_vec_2.end();
  77.     	 ++it2) {
  78.     	while (it1 != new_vec_1.end() && *it1 < *it2) ++it1;
  79.     	if (it1 != new_vec_1.end() && *it1 == *it2) {
  80.             match_index_2.push_back(it2 - new_vec_2.begin());
  81.   		}
  82.     }
  83.     // ---------------------------------------------------------
  84.  
  85.     auto end1 = high_resolution_clock::now();
  86.     auto ticks1 = duration_cast<microseconds>(end1-begin1);
  87.     std::cout << "Vector 2 approach took " << ticks1.count() << " microseconds.\n";
  88.     std::cout << "Number of common indices: " << match_index_2.size() << "\n";
  89.  
  90. }
  91.  
  92.     {
  93.     auto begin1 = high_resolution_clock::now();
  94.  
  95.     // Solve problem -------------------------------------------
  96.     std::unordered_set<int> my_set;
  97.     std::vector<size_t> match_index_2;
  98.  
  99.     for (size_t i = 0u; i < random_vec_1.size(); ++i) {
  100.         my_set.insert(random_vec_1[i]);
  101.     }
  102.     for (size_t i = 0u; i < random_vec_2.size(); ++i) {
  103.         if (my_set.count(random_vec_2[i]) == 1u)
  104.             match_index_2.push_back(i);
  105.     }
  106.     // ---------------------------------------------------------
  107.  
  108.     auto end1 = high_resolution_clock::now();
  109.     auto ticks1 = duration_cast<microseconds>(end1-begin1);
  110.     std::cout << "Set approach took " << ticks1.count() << " microseconds.\n";
  111.     std::cout << "Number of common indices: " << match_index_2.size() << "\n";
  112. }
  113.  
  114. }
Success #stdin #stdout 0.14s 7780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size random_vec_1: 63211
size random_vec_2: 63365
Vector 1 approach took 13941 microseconds.
Number of common indices: 40055
Vector 2 approach took 11054 microseconds.
Number of common indices: 40055
Set approach took 21819 microseconds.
Number of common indices: 40055
https://ideone.com/58qnPf
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!