- #include <iostream>
- #include <ctime>
- #include <stdio.h>
- #include <conio.h>
- #include <algorithm>
- using namespace std;
- bool wstawianie(int x, int rozmiar, int tab[], int &licznik, int q)
- {
- for (int i = 0; i < rozmiar; i++) {
- int k;
- if (q == 0)
- {
- k = ((x % rozmiar + i) % rozmiar);
- }
- if (q == 1)
- {
- k = ((x % rozmiar) + i*((((x / rozmiar) % ((rozmiar / 2)) * 2)) + 1)) % rozmiar;
- }
- licznik++;
- if (tab[k] <= -1)
- {
- tab[k] = x;
- return true;
- }
- }
- return false;
- }
- bool szukanie(int x, int rozmiar, int tab[], int &licznik1, int q)
- {
- int i = 0;
- for (i = 0; i < rozmiar; i++) {
- int k;
- if (q == 0)
- {
- k = ((x %rozmiar + i) % rozmiar);
- // k = x % rozmiar;
- }
- if (q == 1)
- {
- k = ((x % rozmiar) + i*((((x / rozmiar) % ((rozmiar / 2)) * 2)) + 1)) % rozmiar;
- // k= ((x %rozmiar + i) % rozmiar);
- }
- licznik1++;
- if (tab[k] == x)
- {
- return true;
- }
- if (tab[k] == -1) {
- return false;
- }
- }
- return false;
- }
- /*bool inne_szukanie(int x, int rozmiar, int tab[], int &licznik2, int q)
- {
- int i = 0;
- for (i = 0;i < rozmiar;i++)
- {
- int k;
- if (q == 0)
- {
- k=
- }
- }
- }*/
- int main() {
- clock_t start, stop;
- double czas = 0;
- double czas1 = 0;
- double czas2 = 0;
- int licznik = 0;
- int licznik1 = 0;
- int licznik2 = 0;
- int porownania = 0;
- int porownania1 = 0;
- int i, j;
- int dane = 10000000;
- int rozmiar = 1048576;
- float probka;
- int *pusta = new int[rozmiar]; // pusta tablica, rozmiar
- for (i = 0; i < rozmiar; i++)
- {
- pusta[i] = -1;
- }
- int *tab = new int[dane];
- for (int i = 0; i < dane; i++)
- {
- tab[i] = i;
- }
- random_shuffle(tab, tab + dane);
- int q;
- for (q = 0; q < 2; q++) {
- for (i = 0; i <= 9; i++)
- {
- probka = (0.1*i)*rozmiar;
- if (i == 0)
- {
- start = clock();
- for (j = probka; j < 10000; j++)
- {
- wstawianie(tab[j], rozmiar, pusta, licznik, q);
- }
- stop = clock();
- czas = float(stop - start) / CLOCKS_PER_SEC;
- porownania = licznik;
- for (j = 10000; j < (rozmiar / 10); j++) // 10000 - 10%
- {
- wstawianie(tab[j], rozmiar, pusta, licznik, q);
- }
- }
- else if (i>0)
- {
- int k = 0;
- int z = 0;
- start = clock();
- for (j = 0; j < 10000; j++)
- {
- k += probka / 10000;
- // z = probka / 10000;
- // k += (((rand() & 0x7FFF) << 15) | (rand() & 0xFFF)) % z;
- szukanie(tab[k], rozmiar, pusta, licznik1, q);
- }
- stop = clock();
- czas1 = float(stop - start) / CLOCKS_PER_SEC;
- porownania1 = licznik1;
- start = clock();
- for (int j = probka; j < probka + 10000; j++)
- {
- wstawianie(tab[j], rozmiar, pusta, licznik, q);
- }
- stop = clock();
- porownania = licznik;
- czas = float(stop - start) / CLOCKS_PER_SEC;
- if (i != 9)
- {
- for (int j = probka + 10000; j < ((i + 1) / 10)*rozmiar; j++)
- {
- wstawianie(tab[j], rozmiar, pusta, licznik, q);
- }
- }
- }
- cout << i * 10 << "%: czas: " << czas << "s" << endl;
- cout << "porownania: " << porownania << endl << endl;
- cout << i * 10 << "%:czas: " << czas1 << "s Szukanie" << endl;
- cout << "porownania : " << porownania1 << " Szukanie" << endl << endl;
- licznik = 0;
- licznik1 = 0;
- }
- porownania1 = 0; //Zerowanie licznika do drugiej funkcji
- cout << endl << endl;
- for (int i = 0; i < rozmiar; i++)
- {
- pusta[i] = -1;
- }
- }
- getchar();
- delete[]tab;
- delete[]pusta;
- }