fork(1) download 
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <random>
  6. #include <set>
  7. #include <vector>
  8. #include <ctime>
  9.  
  10. static const unsigned seek_count = 1000000;
  11. volatile int nocheat;
  12.  
  13. #ifndef _MSC_VER
  14.         template<typename C>
  15.         auto begin(C &&c) -> decltype(std::forward<C>(c).begin()) { return std::forward<C>(c).begin(); }
  16.         template<typename C>
  17.         auto end(C &&c) -> decltype(std::forward<C>(c).end()) { return std::forward<C>(c).end(); }
  18. #endif
  19.  
  20. clock_t search_set(int N) {
  21.         nocheat = 0;
  22.         auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
  23.         std::set<int> s;
  24.         for(int i=0;i<N;++i) {
  25.                 s.insert(i);
  26.         }
  27.         clock_t start = clock();
  28.         for(int i=0;i<seek_count;++i) {
  29.             int findme = r();
  30.             auto iter = s.find(findme);
  31.             nocheat += *iter;
  32.         }
  33.         clock_t end = clock();
  34.         return end-start;
  35. }
  36.  
  37. clock_t search_vector(int N) {
  38. 	    nocheat = 0;
  39.         auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
  40.         std::vector<int> s;
  41.         for(int i=0;i<N;++i) {
  42.                 s.push_back(i);
  43.         }
  44.         clock_t start = clock();
  45. 		for(int i=0;i<seek_count;++i) {
  46. 			int findme = r();
  47. 			auto iter = std::lower_bound(begin(s),end(s),findme);
  48. 			if (iter == s.end() || *iter<findme)
  49. 				iter = s.end();
  50. 			nocheat += *iter;
  51. 		}
  52.         clock_t end = clock();
  53.         return end-start;
  54. }
  55.  
  56. int main()
  57. {
  58.     const int N = 100000;
  59.         int time;
  60.  
  61. #if defined(WIN32)
  62.         std::cout.imbue(std::locale("English_United States.1251"));
  63. #endif
  64.  
  65.     std::cout << "Time for N searches where N = " << N << "\n";
  66.         time = search_set(N);
  67.     std::cout << "set returned " << nocheat<< " in " << time << " ticks\n";
  68.         time = search_vector(N);
  69.     std::cout << "vector returned " << nocheat<< " in " << time << " ticks\n";
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.61s 2964KB
comments (?)
stdin 
Standard input is empty
stdout 
Time for N searches where N = 100000
set returned -1537027134 in 400000 ticks
vector returned -1537027134 in 180000 ticks
https://ideone.com/vaI3v
language:
C++14 (gcc 8.3)
created:
12 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!