fork(4) 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
comments (?)
stdin 
Standard input is empty
stdout 
checksum = 53685390368196199
number of operations is 50000000, runtime is 0.850s
https://ideone.com/aBetYn
language:
C++14 (gcc 8.3)
created:
5 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!