fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <unordered_set>
  5. #include <cstdlib>
  6. #include <ctime>
  7. #include <cassert>
  8. #include <set>
  9.  
  10. typedef unsigned long long ull;
  11. typedef std::pair<int,ull> Hash;
  12.  
  13. struct getHash {
  14. public:
  15. 	template <typename T, typename U>
  16. 	std::size_t operator()(const std::pair<T, U> &x) const
  17. 	{
  18. 		return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  19. 	}
  20. };
  21.  
  22. ull rand_ull() {
  23. 	ull res = 0;
  24. 	for (int i = 0; i < 6; ++i) {
  25. 		(res *= 1000) += (std::rand() % 1000);
  26. 	}
  27. 	return res;
  28. }
  29.  
  30. int main() {
  31. 	std::srand(std::time(0));
  32.  
  33. 	const int n = (int)1e6;
  34.  
  35. 	std::vector<Hash> array(n);
  36.  
  37. 	for (auto& it : array) {
  38. 		it = std::make_pair(std::rand() % (int)1e9, rand_ull());
  39. 	}
  40.  
  41. 	std::vector<Hash> queries(n);
  42.  
  43. 	for (auto& it : queries) {
  44. 		it = std::make_pair(std::rand() % (int)1e9, rand_ull());
  45. 	}
  46.  
  47. 	double t = clock();
  48.  
  49. 	std::set<Hash> hashtable;
  50.  
  51. 	for (auto it : array) {
  52. 		hashtable.insert(it);
  53. 	}
  54.  
  55. 	int count1 = 0;
  56.  
  57. 	for (auto hash : queries) {
  58. 		count1 += hashtable.find(hash) != hashtable.end();
  59. 	}
  60.  
  61. 	double time1 = (clock() - t) / CLOCKS_PER_SEC;
  62.  
  63. 	t = clock();
  64.  
  65. 	std::sort(array.begin(), array.end());
  66.  
  67. 	int count2 = 0;
  68.  
  69. 	for (auto hash : queries) {
  70. 		count2 += std::binary_search(array.begin(), array.end(), hash);
  71. 	}
  72.  
  73. 	double time2 = (clock() - t) / CLOCKS_PER_SEC;
  74.  
  75. 	assert(count1 == count2);
  76.  
  77. 	fprintf(stdout, "size & queries = %d\n", n);
  78. 	fprintf(stdout, "      std::set = %0.3fs\n", time1);
  79. 	fprintf(stdout, "sort+binsearch = %0.3fs\n", time2);
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 1.82s 96300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size & queries = 1000000
      std::set = 1.269s
sort+binsearch = 0.271s
https://ideone.com/DYLNa6
language:
C++14 (gcc 8.3)
created:
6 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!