SHARE
TWEET

LAB 4

Mary_99 Jan 30th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <fstream>
  4. #include <cmath>
  5. #include <ctime>
  6. using namespace std;
  7.  
  8. int hashing(string word) // hashing function
  9. {
  10.     int word_size = word.size(); //zwraca dĀ³ugosc stinga
  11.     int v = 0; //value
  12.     int ascii = 0;
  13.  
  14.     if(word_size > 4)
  15.     {
  16.       word_size = 4;
  17.     }
  18.  
  19.     for(int i = 0; i < word_size; i++)
  20.     {
  21.         ascii = word[i];
  22.         v = v + (pow(39, i+1) * ascii);
  23.     }
  24.     return v;
  25. }
  26.  
  27.  
  28. int main()
  29. {
  30.     double avr_1;
  31.     double avr_2;
  32.  
  33.     clock_t begin;
  34.     clock_t end;
  35.     ifstream file;
  36.     file.open("words20k.txt");
  37.     string word;
  38.     string A[20000];
  39.     string H[24000];
  40.     int v;//vale
  41.     for(int i = 0; i < 20000; i++)
  42.     {
  43.        file >> A[i];
  44.     }
  45.  
  46.     for(int i = 0; i < 24000; i++)
  47.     {
  48.          H[i] = "";
  49.     }
  50.  
  51.     for(int i = 0; i < 20000; i++)
  52.     {
  53.         if(i==0 || i==19499)
  54.         {
  55.             begin = clock();
  56.         }
  57.         word = A[i];
  58.         v = hashing(word)%24000;
  59.         while(H[v]!="" || v>=24000)
  60.         {
  61.             v++;
  62.             if(v>=24000)
  63.                 v=0;
  64.         }
  65.         H[v]=word;
  66.         if(i==499)
  67.         {
  68.             end = clock();
  69.             avr_1 = double(end - begin) / CLOCKS_PER_SEC;
  70.         }
  71.         if(i==19999)
  72.         {
  73.             end = clock();
  74.             avr_2 = double(end - begin) / CLOCKS_PER_SEC;
  75.         }
  76.  
  77.     }
  78.     for(int i = 0; i < 24000; i++)
  79.     {
  80.         cout<<H[i]<<" ";
  81.     }
  82.  
  83.     int remove_start = 14000;
  84.     int remove_end = 14999;
  85.     int avg = remove_end - remove_start;
  86.     for (int i = remove_start; i < remove_end; i++)
  87.     {
  88.         word = A[i];
  89.         v = hashing(word)%24000;
  90.         while(H[v]!=word || v>=24000)
  91.         {
  92.             v++;
  93.             if(v>=24000)
  94.                v=0;
  95.         }
  96.         cout<<"word: "<<word<<" removed: "<<H[v]<<endl;
  97.         H[v]="";
  98.     }
  99.     cout.precision(20);
  100.     cout<<avr_1<<" "<<avr_2;
  101.     return 0;
  102. }
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