fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <chrono>
  6. using namespace std;
  7.  
  8. auto vandenman(const vector<int>& x, const int k) {
  9.     auto y = x;
  10.     std::nth_element(y.begin(), y.begin() + k, y.end());
  11.     const auto kthValue = y[k];
  12.     auto idxK = std::find(x.begin(), x.end(), kthValue);
  13.     return idxK;
  14. }
  15.  
  16. template<typename It>
  17. auto miscco(It first, It last, const int k) {
  18.     auto cmp_it_values = [](It lt, It rt){ return *lt < *rt;};
  19. 	vector<It> y;
  20. 	for(auto it = first; it != last; ++it){
  21. 		y.emplace_back(it);
  22. 	}
  23.     std::nth_element(y.begin(), y.begin() + k, y.end(), cmp_it_values);
  24.     return y[k];
  25. }
  26.  
  27. template<typename It>
  28. It min_k(It first, It last, int k){
  29.    auto cmp_it_values = [](It lt, It rt){ return *lt < *rt;};
  30.    auto max_copy = std::min<long>(k, std::distance(first, last));
  31.    auto start_it = first;
  32.    std::advance(start_it, max_copy);
  33.  
  34. 	k++; // k == 0 has to return smallest one element.
  35.     std::vector<It> k_smallest;
  36.     k_smallest.reserve(k+1);
  37.     for(auto it = first; it != start_it; ++it){
  38.     	k_smallest.push_back(it);
  39.     }
  40.     std::sort(k_smallest.begin(), k_smallest.end(), cmp_it_values);
  41.  
  42.     for(auto it = start_it; it != last; ++it){
  43.         if(k_smallest.empty() || *it < *k_smallest.back()){
  44.             auto insertion_point = std::lower_bound(k_smallest.begin(), k_smallest.end(), 
  45.                                                     it, cmp_it_values);
  46.             k_smallest.insert(insertion_point, it);
  47.             if(k_smallest.size() > k){
  48.                 k_smallest.pop_back(); // Remove the largest value
  49.             }
  50.         }
  51.     }    
  52.     return k_smallest.back(); // The iterator to the min(k, n) smallest value 
  53. }
  54.  
  55.  
  56. template<typename It>
  57. It min_k_heap(It first, It last, int k){
  58. 	k++; // k == 0 has to return smallest one element.
  59.     auto cmp_it_values = [](It lt, It rt){ return *lt < *rt;};
  60.     auto max_copy = std::min<long>(k, std::distance(first, last));
  61.     auto start_it = first;
  62.     std::advance(start_it, max_copy);
  63.  
  64.     std::vector<It> k_smallest;
  65.     k_smallest.reserve(k+1);
  66.     for(auto it = first; it != start_it; ++it){
  67.     	k_smallest.push_back(it);
  68.     }
  69.     std::make_heap(k_smallest.begin(), k_smallest.end(), cmp_it_values);
  70.  
  71. 	for(auto it = start_it; it != last; ++it){
  72.         if(*it < *k_smallest.front()){
  73.         	k_smallest.push_back(it);
  74.         	push_heap(k_smallest.begin(), k_smallest.end(), cmp_it_values);
  75.        	    pop_heap(k_smallest.begin(), k_smallest.end(), cmp_it_values);
  76.        	    k_smallest.pop_back();
  77.         }
  78.     }    
  79.     return k_smallest.front(); // The iterator to the min(k, n) smallest value 
  80. }
  81.  
  82. int main() {
  83.     std::vector<int> v(10000);
  84.     std::iota (std::begin(v), std::end(v), 0);
  85.     std::mt19937 g(3);
  86.     std::shuffle(v.begin(), v.end(), g);
  87.  
  88. 	{
  89. 	    auto start = chrono::steady_clock::now();
  90. 	    auto ans1 = *vandenman(v, 50);
  91. 	    auto time1 = chrono::steady_clock::now() - start;
  92. 	    cout << "Orig " << ans1<< " time: ";
  93. 	    cout << chrono::duration <double, nano> (time1).count() << " ns" << endl;
  94. 	}
  95. 	{
  96. 	    auto start = chrono::steady_clock::now();
  97. 	    auto ans1 = *miscco(v.begin(), v.end(), 50);
  98. 	    auto time1 = chrono::steady_clock::now() - start;
  99. 	    cout << "Miscco " << ans1<< " time: ";
  100. 	    cout << chrono::duration <double, nano> (time1).count() << " ns" << endl;
  101. 	}
  102. 	{
  103. 		auto start = chrono::steady_clock::now();
  104. 	    auto ans1 = *min_k(v.begin(), v.end(), 50);
  105. 	    auto time1 = chrono::steady_clock::now() - start;
  106. 	    cout << "Emily Binary insertion " << ans1<< " time: ";
  107. 	    cout << chrono::duration <double, nano> (time1).count() << " ns" << endl;
  108. 	}
  109. 	{
  110. 		auto start = chrono::steady_clock::now();
  111. 	    auto ans1 = *min_k_heap(v.begin(), v.end(), 50);
  112. 	    auto time1 = chrono::steady_clock::now() - start;
  113. 	    cout << "Emily Heap " << ans1<< " time: ";
  114. 	    cout << chrono::duration <double, nano> (time1).count() << " ns" << endl;
  115. 	}
  116.     return 0;
  117. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Orig 50 time: 70707 ns
Miscco 50 time: 128430 ns
Emily Binary insertion 50 time: 38554 ns
Emily Heap 50 time: 35296 ns
https://ideone.com/B81Hs4
language:
C++14 (gcc 8.3)
created:
8 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!