Facebook
From Gray Crow, 7 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 278
  1. #include <iostream>
  2. #include <ctime>
  3. #include <stdio.h>
  4. #include <conio.h>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. bool wstawianie(int x, int rozmiar, int tab[], int &licznik, int q)
  10. {
  11.         for (int i = 0; i < rozmiar; i++) {
  12.                 int k;
  13.                 if (q == 0)
  14.                 {
  15.                         k = ((x % rozmiar + i) % rozmiar);
  16.                 }
  17.                 if (q == 1)
  18.                 {
  19.                         k = ((x % rozmiar) + i*((((x / rozmiar) % ((rozmiar / 2)) * 2)) + 1)) % rozmiar;
  20.                 }
  21.                 licznik++;
  22.                 if (tab[k] <= -1)
  23.                 {
  24.                         tab[k] = x;
  25.  
  26.                         return true;
  27.                 }
  28.         }
  29.         return false;
  30. }
  31.  
  32. bool szukanie(int x, int rozmiar, int tab[], int &licznik1, int q)
  33. {
  34.         int i = 0;
  35.         for (i = 0; i < rozmiar; i++) {
  36.                 int k;
  37.                 if (q == 0)
  38.                 {
  39.                         k = ((x %rozmiar + i) % rozmiar);
  40. //                      k = x % rozmiar;
  41.                 }
  42.                 if (q == 1)
  43.                 {
  44.                         k = ((x % rozmiar) + i*((((x / rozmiar) % ((rozmiar / 2)) * 2)) + 1)) % rozmiar;
  45. //                      k= ((x %rozmiar + i) % rozmiar);
  46.                 }
  47.  
  48.  
  49.                 licznik1++;
  50.                 if (tab[k] == x)
  51.                 {
  52.                         return true;
  53.                 }
  54.                 if (tab[k] == -1) {
  55.                         return false;
  56.                 }
  57.         }
  58.         return false;
  59. }
  60.  
  61. /*bool inne_szukanie(int x, int rozmiar, int tab[], int &licznik2, int q)
  62. {
  63.         int i = 0;
  64.         for (i = 0;i < rozmiar;i++)
  65.         {
  66.                 int k;
  67.                 if (q == 0)
  68.                 {
  69.                         k=
  70.                 }
  71.         }
  72. }*/
  73.  
  74.  
  75.  
  76.  
  77.  
  78. int main() {
  79.         clock_t start, stop;
  80.         double czas = 0;
  81.         double czas1 = 0;
  82.         double czas2 = 0;
  83.         int licznik = 0;
  84.         int     licznik1 = 0;
  85.         int licznik2 = 0;
  86.         int porownania = 0;
  87.         int     porownania1 = 0;
  88.         int i, j;
  89.         int dane = 10000000;
  90.         int rozmiar = 1048576;
  91.         float probka;
  92.         int *pusta = new int[rozmiar]; // pusta tablica, rozmiar
  93.         for (i = 0; i < rozmiar; i++)
  94.         {
  95.                 pusta[i] = -1;
  96.         }
  97.         int *tab = new int[dane];
  98.  
  99.         for (int i = 0; i < dane; i++)
  100.         {
  101.                 tab[i] = i;
  102.         }
  103.  
  104.         random_shuffle(tab, tab + dane);
  105.         int q;
  106.  
  107.         for (q = 0; q < 2; q++) {
  108.                 for (i = 0; i <= 9; i++)
  109.                 {
  110.                         probka = (0.1*i)*rozmiar;
  111.  
  112.                         if (i == 0)
  113.                         {
  114.                                 start = clock();
  115.                                 for (j = probka; j < 10000; j++)
  116.                                 {
  117.                                         wstawianie(tab[j], rozmiar, pusta, licznik, q);
  118.                                 }
  119.                                 stop = clock();
  120.                                 czas = float(stop - start) / CLOCKS_PER_SEC;
  121.                                 porownania = licznik;
  122.                                 for (j = 10000; j < (rozmiar / 10); j++) // 10000 - 10%
  123.                                 {
  124.                                         wstawianie(tab[j], rozmiar, pusta, licznik, q);
  125.                                 }
  126.  
  127.                         }
  128.                         else if (i>0)
  129.                         {
  130.                                 int k = 0;
  131.                                 int z = 0;
  132.                                 start = clock();
  133.                                 for (j = 0; j < 10000; j++)
  134.                                 {
  135.                                         k += probka / 10000;
  136.         //                              z = probka / 10000;
  137.         //                              k += (((rand() & 0x7FFF) << 15) | (rand() & 0xFFF)) % z;
  138.                                         szukanie(tab[k], rozmiar, pusta, licznik1, q);
  139.                                 }
  140.                                 stop = clock();
  141.                                 czas1 = float(stop - start) / CLOCKS_PER_SEC;
  142.                                 porownania1 = licznik1;
  143.  
  144.                                 start = clock();
  145.                                 for (int j = probka; j < probka + 10000; j++)
  146.                                 {
  147.                                         wstawianie(tab[j], rozmiar, pusta, licznik, q);
  148.                                 }
  149.                                 stop = clock();
  150.                                 porownania = licznik;
  151.                                 czas = float(stop - start) / CLOCKS_PER_SEC;
  152.  
  153.                                 if (i != 9)
  154.                                 {
  155.                                         for (int j = probka + 10000; j < ((i + 1) / 10)*rozmiar; j++)
  156.                                         {
  157.                                                 wstawianie(tab[j], rozmiar, pusta, licznik, q);
  158.                                         }
  159.                                 }
  160.  
  161.                         }
  162.                         cout << i * 10 << "%: czas: " << czas << "s" << endl;
  163.                         cout << "porownania: " << porownania << endl << endl;
  164.                         cout << i * 10 << "%:czas: " << czas1 << "s    Szukanie" << endl;
  165.                         cout << "porownania : " << porownania1 << "   Szukanie" << endl << endl;
  166.  
  167.                         licznik = 0;
  168.                         licznik1 = 0;
  169.                 }
  170.                 porownania1 = 0; //Zerowanie licznika do drugiej funkcji
  171.                 cout << endl << endl;
  172.                 for (int i = 0; i < rozmiar; i++)
  173.                 {
  174.                         pusta[i] = -1;
  175.                 }
  176.  
  177.         }
  178.         getchar();
  179.         delete[]tab;
  180.         delete[]pusta;
  181. }