SHARE
TWEET

Untitled

a guest May 22nd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <chrono>
  4.  
  5. int licznik = 0;
  6. /*
  7. int h(int x, int akt_i, int T)
  8. {
  9.     if (akt_i == 0) return x % T;
  10.  
  11.     return (h(x, 0, T) + akt_i) % T;
  12. }
  13. */
  14. int h1(int x, int T)
  15. {
  16.     return x%T;
  17. }
  18.  
  19. int h2(int x, int T)
  20. {
  21.     return (((x / T) %(T / 2)) * 2) + 1;
  22. }
  23.  
  24. int h(int x, int akt_i, int T)
  25. {
  26.     return (h1(x,T) + akt_i*h2(x,T)) % T;
  27. }
  28.  
  29. bool hash_al_wstaw(int* tab, int x, int T)
  30. {
  31.     for (int i = 0; i < T; i++)
  32.     {
  33.         int k = h(x, i, T);
  34.         licznik++;
  35.         if (tab[k] == -1 || tab[k] == -2)
  36.         {
  37.             tab[k] = x;
  38.             return true;
  39.         }
  40.     }
  41.     return false;
  42. }
  43.  
  44. bool hash_al_szukaj(int* tab, int x, int T)
  45. {
  46.     for (int i = 0; i < T; i++)
  47.     {
  48.         int k = h(x, i, T);
  49.         licznik++;
  50.         if (tab[k] == x) return true;
  51.         if (tab[k] == -1) return false;
  52.     }
  53.     return false;
  54. }
  55.  
  56. int main()
  57. {
  58.     int T = 1048576;
  59.     int* tab = new int[T];
  60.     for (int i = 0; i < T; i++)
  61.     {
  62.         tab[i] = -1;
  63.     }
  64.     //hash_al_wstaw(tab, 1048576, T);
  65.     //std::cout << tab[0];
  66.    
  67.     int rozmiar = 12000000;
  68.     int* tablica = new int[rozmiar];
  69.     for (int i = 0; i < rozmiar; i++)
  70.     {
  71.         tablica[i] = i;
  72.     }
  73.     //std::cout << tablica[515];
  74.     std::random_shuffle(tablica, tablica + rozmiar);
  75.     //std::cout << tablica[515];
  76.  
  77.     std::cout << "Wstawianie: " << std::endl;
  78.     std::cout << std::endl;
  79.  
  80.     std::cout << "0%: " << std::endl;
  81.     auto start = std::chrono::high_resolution_clock::now();
  82.  
  83.     for (int i = 0; i < 10000; i++)
  84.     {
  85.         hash_al_wstaw(tab, tablica[i], T);
  86.     }
  87.  
  88.     auto end = std::chrono::high_resolution_clock::now();
  89.     std::chrono::duration<double, std::micro> duration = end - start;
  90.     std::cerr << "Uplynelo: " << duration.count() << "us\n";
  91.     std::cout << "Wywolania: " << licznik << std::endl;
  92.     licznik = 0;
  93.     int pom = 1048576/10;
  94.     //std::cout << pom << std::endl;
  95.  
  96.    
  97.     for (int j = 1; j < 10; j++)
  98.     {
  99.         std::cout << j << "0%: " << std::endl;
  100.  
  101.  
  102.         for (int i = 0; i < T; i++)
  103.         {
  104.             tab[i] = -1;
  105.         }
  106.  
  107.         auto start = std::chrono::high_resolution_clock::now();
  108.  
  109.         for (int i = 0; i < pom*j; i++)
  110.         {
  111.             hash_al_wstaw(tab, tablica[i], T);
  112.         }
  113.         licznik = 0;
  114.         for (int i = pom * j; i < pom * j + 10000; i++)
  115.         {
  116.             hash_al_wstaw(tab, tablica[i], T);
  117.         }
  118.  
  119.         auto end = std::chrono::high_resolution_clock::now();
  120.         std::chrono::duration<double, std::micro> duration = end - start;
  121.         std::cerr << "Uplynelo: " << duration.count() << "us\n";
  122.         std::cout << "Wywolania: " << licznik << std::endl;
  123.         licznik = 0;
  124.     }
  125.  
  126.     std::cout << std::endl;
  127.     std::cout << "Szukanie: " << std::endl;
  128.     std::cout << std::endl;
  129.  
  130.     for (int j = 1; j < 10; j++)
  131.     {
  132.         std::cout << j << "0%: " << std::endl;
  133.  
  134.         for (int i = 0; i < T; i++)
  135.         {
  136.             tab[i] = -1;
  137.         }
  138.  
  139.  
  140.         for (int i = 0; i < pom*j; i++)
  141.         {
  142.             hash_al_wstaw(tab, tablica[i], T);
  143.         }
  144.  
  145.         auto start = std::chrono::high_resolution_clock::now();
  146.         licznik = 0;
  147.         for (int i = 0; i < pom * j; i+=pom*j/10000)
  148.         {
  149.             hash_al_szukaj(tab, tablica[i], T);
  150.         }
  151.  
  152.         auto end = std::chrono::high_resolution_clock::now();
  153.         std::chrono::duration<double, std::micro> duration = end - start;
  154.         std::cerr << "Uplynelo: " << duration.count() << "us\n";
  155.         std::cout << "Wywolania: " << licznik << std::endl;
  156.         licznik = 0;
  157.     }
  158.  
  159.     delete[] tab;
  160.     delete[] tablica;
  161.     system("pause");
  162.     return 0;
  163. }
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