SHARE
TWEET

aids

a guest May 23rd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <chrono>
  3. #include <thread>
  4. #include <random>
  5. #include <algorithm>
  6.  
  7. int h(int x, int i, int T)
  8. {
  9.     if (i == 0)
  10.         return x % T;
  11.  
  12.     return (h(x, 0, T) + i) % T;
  13. }
  14.  
  15. bool hash_al_wstaw(int *A, int x, int T, int &wywolanie)
  16. {
  17.     for (int i = 0; i < T; i++)
  18.     {
  19.         wywolanie++;
  20.         int k = h(x, i, T);
  21.         if (A[k] == -1)
  22.         {
  23.             A[k] = x;
  24.             return true;
  25.         }
  26.     }
  27.  
  28.     return false;
  29. }
  30.  
  31. bool hash_al_szukaj(int *A, int x, int T, int &wywolanie)
  32. {
  33.     for (int i = 0; i < T; i++)
  34.     {
  35.         wywolanie++;
  36.         int k = h(x, i, T);
  37.         if (A[k] == x)
  38.             return true;
  39.         else if (A[k] == -1)
  40.             return false;
  41.     }
  42.  
  43.     return false;
  44. }
  45.  
  46. int losowa_liczba(int min = 0, int max = std::numeric_limits<int>::max())
  47. {
  48.     static std::default_random_engine gen(std::random_device{}());
  49.     static std::uniform_int_distribution<int> dist;
  50.     return dist(gen, std::uniform_int_distribution<int>::param_type{ min, max });
  51. }
  52.  
  53.  
  54. int* restr(int *tab, int &T, int &wywolanie) {
  55.  
  56.     int *nowa_tab = new int[2*T];
  57.  
  58.     for (int i = 0; i < T; i++) {
  59.         if (tab[i] != -1)
  60.             hash_al_wstaw(tab, nowa_tab[i], T, wywolanie);
  61.     }
  62.     T = 2 * T;
  63.     delete[] tab;
  64.     return nowa_tab;
  65.     delete[] nowa_tab;
  66. }
  67.  
  68. bool new_hash_al_wstaw(int *A, int x, int T, int &wywolanie, &zapelnienie)
  69. {
  70.     for (int i = 0; i < T; i++)
  71.     {
  72.         wywolanie++;
  73.         int k = h(x, i, T);
  74.         if (A[k] == -1)
  75.         {
  76.             A[k] = x;
  77.             return true;
  78.         }
  79.     }
  80.  
  81.     return false;
  82. }
  83.  
  84. int main()
  85. {
  86.     const int T = 1048576;
  87.     int *tab_miesz = new int[T];
  88.  
  89.     for (int i = 0; i < T; i++)
  90.         tab_miesz[i] = -1;
  91.  
  92.     const int length = 12000000;
  93.     int *tab = new int[length];
  94.  
  95.     for (int i = 0; i < length; i++)
  96.         tab[i] = i;
  97.  
  98.     std::random_shuffle(tab, tab + length);
  99.  
  100.     int wywolanie = 0;
  101.     int procent10 = T / 10;
  102.     int procent = T / 10;
  103.     int zapelnienie = 10;
  104.  
  105.     for (int i = 0; i < T * 0.9; i++)
  106.     {
  107.         hash_al_wstaw(tab_miesz, tab[i], T, wywolanie);
  108.  
  109.         if (i == procent)
  110.         {
  111.             wywolanie = 0;
  112.             auto start = std::chrono::high_resolution_clock::now();
  113.  
  114.             for (int j = 0; j < procent; j += procent / 10000)
  115.                 hash_al_szukaj(tab_miesz, tab[j], T, wywolanie);
  116.  
  117.             auto end = std::chrono::high_resolution_clock::now();
  118.  
  119.             std::chrono::duration<double, std::micro> duration = end - start;
  120.  
  121.             std::cerr << zapelnienie << "% " << "Uplynelo: " << duration.count() << "us\n";
  122.             std::cerr << zapelnienie << "% " << "Wywolania: " << wywolanie << "\n" << "\n";
  123.  
  124.  
  125.             procent += procent10;
  126.             zapelnienie += 10;
  127.         }
  128.     }
  129. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top