fork 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
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