fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <cstdlib>
  5. #include <algorithm>
  6. #include <ctime>
  7. #include <map>
  8.  
  9. typedef unsigned value;
  10. typedef unsigned index;
  11.  
  12. #ifdef _DEBUG
  13. const index datacount = 10000;
  14. const index lookupcount = 10000;
  15. #else
  16. const index datacount = 10000000;
  17. const index lookupcount = 100000;
  18. #endif
  19.  
  20. int main() {
  21. std::vector<value> a(datacount); //amount of data
  22. for(index i=0; i<a.size(); ++i)
  23. a[i] = 2*i+rand()%2; //values are unique and ordered, but sparse
  24. std::random_shuffle(a.begin(), a.end()); //shuffle them
  25. std::vector<value> findme(lookupcount); //number of finds to do
  26. for(index i=0; i<findme.size(); ++i) //predecide which need to be found,
  27. findme[i] = a[rand()%a.size()]; //removes so all tests are equal
  28.  
  29. {
  30. std::cout << "unsorted vector ";
  31. index result = 0;
  32. clock_t begin = clock();
  33. for(index i=0; i<findme.size(); ++i) {
  34. auto iter = std::find(a.begin(), a.end(), findme[i]); //linear find
  35. result += (iter-a.begin()); //add it's index
  36. }
  37. clock_t end = clock();
  38. std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
  39. }
  40.  
  41. {
  42. std::cout << "sorted vector ";
  43. index result = 0;
  44. clock_t begin = clock();
  45. std::vector<std::pair<value, index>> sorted(a.size()); //reverse lookup vector
  46. for(index i=0; i<sorted.size(); ++i)
  47. sorted[i] = std::pair<value, index>(a[i], i);
  48. std::sort(sorted.begin(), sorted.end()); //that is sorted
  49. for(index i=0; i<findme.size(); ++i) { //binary search
  50. auto iter = std::lower_bound(sorted.begin(), sorted.end(), std::pair<value, index>(findme[i], 0));
  51. result += iter->second; //add it's index
  52. }
  53. clock_t end = clock();
  54. std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
  55. }
  56.  
  57. {
  58. std::cout << "unordered_map ";
  59. index result = 0;
  60. clock_t begin = clock();
  61. std::unordered_map<value, index> lookup(a.size()); //reverse lookup hash
  62. for(index i=0; i<a.size(); ++i)
  63. lookup[a[i]] = i;
  64. for(index i=0; i<findme.size(); ++i) {
  65. result += lookup[findme[i]]; //add it's index
  66. }
  67. clock_t end = clock();
  68. std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
  69. }
  70.  
  71. {
  72. std::cout << "std::map ";
  73. index result = 0;
  74. clock_t begin = clock();
  75. std::map<value, index> lookup; //reverse lookup map
  76. for(index i=0; i<a.size(); ++i)
  77. lookup[a[i]] = i;
  78. for(index i=0; i<findme.size(); ++i) {
  79. result += lookup[findme[i]]; //add it's index
  80. }
  81. clock_t end = clock();
  82. std::cout << " found " << result << " in " << (end-begin) << " ticks.\n";
  83. }
  84.  
  85. return 0;
  86. }
Time limit exceeded #stdin #stdout 5s 42296KB
stdin
Standard input is empty
stdout

Standard output is empty