fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U0ufy
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!