fork(3) download
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3. #define isz(x) (int)(x).size()
  4. typedef unsigned long long ull;
  5. const uint64_t seed = (uint64_t)(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  6. const int mod = int((1LL << 31) - 1);
  7. int remainder(uint64_t x) {
  8. x = (x >> 31) + (x & mod) + 1;
  9. x = (x >> 31) + (x & mod);
  10. return int((x >> 31) + (x & mod) - 1);
  11. }
  12.  
  13. struct CustomHash {
  14. uint64_t operator()(uint64_t x) const {
  15. static const uint64_t a = remainder(seed);
  16. static const uint64_t b = remainder(a * a);
  17. static const uint64_t c = remainder(a * b);
  18. static const uint64_t d = remainder(a * c);
  19. static const uint64_t m = (1 << 16) - 1;
  20. return remainder((x&m)*a+((x>>16)&m)*b+((x>>32)&m)*c+((x>>48)&m)*d);
  21. }
  22. };
  23.  
  24. template<typename HashType>
  25. void report(const char * filename) {
  26. // This function reads numbers from file `filename` and counts number of collisios
  27. std::map<int,int> collisions;
  28. auto file = fopen(filename, "rt");
  29. for (ull num; fscanf(file, "%llu", &num) == 1; ) {
  30. auto res = HashType()(num);
  31. collisions[res & ((1 << 18) - 1)]++;
  32. }
  33. fclose(file);
  34. std::vector<int> vec;
  35. for (auto p : collisions) { vec.push_back(p.second-1); }
  36. std::sort(all(vec));
  37. auto median = vec[isz(vec)/2];
  38. auto average = std::accumulate(all(vec), 1.0) / isz(vec);
  39. std::cerr << "report for file " << filename << ":\n";
  40. std::cerr << "buckets = " << collisions.size() << "\n";
  41. std::cerr << "average collisions num = " << average << "\n";
  42. std::cerr << "median of collisions num = " << median << "\n";
  43. std::cerr << "max = " << vec.back() << "\n";
  44. std::cerr << "min = " << vec.front() << "\n";
  45. }
  46.  
  47. int main() {
  48. std::cout << std::fixed << std::setprecision(3);
  49. //report<CustomHash>("stat1.txt");
  50. // This part of code test CustomHash on runtime:
  51. double tin = (double)clock();
  52. std::mt19937 gen(seed);
  53. std::uniform_int_distribution<uint64_t> dist(ull(0), ~ull(0));
  54. ull sum = 0;
  55. const int numOper = 50 * 1000 * 1000;
  56. for (int i = 0; i < numOper; i++) {
  57. sum += CustomHash()(dist(gen));
  58. }
  59. double tout = ((double)clock() - tin) / CLOCKS_PER_SEC;
  60. std::cout << "checksum = " << sum << std::endl;
  61. std::cout << "number of operations is " << numOper << ", runtime is " << tout << "s" << std::endl;
  62. return 0;
  63. }
Success #stdin #stdout 0.85s 15240KB
stdin
Standard input is empty
stdout
checksum = 53685390368196199
number of operations is 50000000, runtime is 0.850s