vadimk772336

продолжение

Nov 23rd, 2021 (edited)
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib> // для функций rand() и srand()
  4. #include <list>
  5. #include <iterator>
  6. using namespace std;
  7.  
  8. const int c = 3; // O(n) ~ 3n
  9. const int p = 2000000033;
  10.  
  11. int rand_int(int min, int max)
  12. {
  13.     static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
  14.     return static_cast<int>(rand() * fraction * (max - min + 1) + min);
  15. }
  16.  
  17. int uni_hash(int a, int b, int m, int key)
  18. {
  19.     return ((a * key + b) % p) % m);
  20. }
  21.  
  22.  
  23. struct Node
  24. {
  25.     int a;
  26.     int b;
  27.     vector<int>* second_table = NULL;
  28.     vector<int> keys;
  29.     int count_keys = 0;
  30. };
  31.  
  32. class FixedSet
  33. {
  34.     vector<struct Node> nodes; //вектор ячеек первой хэш табл
  35.     vector<vector<int>> second_tables;
  36.     int count_numbers;
  37.     int table_size;
  38.     // vector<vector<int>> vec(2, vector<int>(10));
  39. public:
  40.     FixedSet();
  41.     void Initialize(const vector<int>& numbers);
  42.     bool Contains(int number) const;
  43.     void print();
  44. };
  45.  
  46. FixedSet::FixedSet()
  47. {
  48.     this->count_numbers = 0;
  49.     this->nodes;
  50.     this->table_size = 0;
  51. }
  52.  
  53. void FixedSet::Initialize(const vector<int>& numbers)
  54. {
  55.     this->count_numbers = numbers.size();
  56.     this->table_size = c * count_numbers;
  57.  
  58.     //Задаём размеры таблиц
  59.     this->nodes.resize(table_size);
  60.     this->second_tables.resize(table_size); //внутренние размера 0
  61.  
  62.     int m1 = c * count_numbers; //Размер 1 уровня
  63.     int hash, key;
  64.     bool flag = false; //Тру если простроили корректно
  65.  
  66.     while (!flag) //!!!!!!!!!!!!!!!!!!   Написать чистку вектора  мб работать с копией но тогда как
  67.                   //!указывать на нее
  68.     {
  69.         a = rand_int(1, p - 1);
  70.         b = rand_int(0, p - 1); //Глобальная ХФ
  71.  
  72.         //Закинули все ключи в таблицу
  73.         for (int i = 0; i < this->count_numbers; ++i)
  74.         {
  75.             key = numbers[i];
  76.             hash = uni_hash(a, b, table_size, key);
  77.             nodes[hash].keys.push_back(key);
  78.             nodes[hash].count_keys += 1;
  79.         }
  80.  
  81.         //Теперь считаю коллизии
  82.         int S = 0;
  83.         for (int i = 0; i < this->table_size; ++i)
  84.         {
  85.             S += (nodes[i].count_keys) * (nodes[i].count_keys);
  86.         }
  87.  
  88.         if (S <= this->table_size)
  89.         {
  90.             flag = true;
  91.         }
  92.  
  93.         else //Чистка
  94.         {
  95.             this->nodes.clear();
  96.             nodes.resize(this->table_size);
  97.         }
  98.     }
  99.  
  100.     //Вышли из вайл - значит успешно построили первый уровень, теперь второй:
  101.     int b_i;
  102.     for (int i = 0; i < this->table_size; ++i)
  103.     {
  104.  
  105.         flag = false;
  106.  
  107.         while (!flag) //Повторяю попытки пока не получится без коллизий (добавить проврку на пустоту)
  108.         {
  109.             b_i = nodes[i].count_keys;
  110.             second_table_size = b_i * b_i * c;
  111.  
  112.             this->second_tables[i].resize(
  113.                 second_table_size); //создать таблицу второго уровня для данного ключ
  114.  
  115.             a = rand_int(1, p - 1);
  116.             b = rand_int(0, p - 1); // i-ая ХФ для второго слоя
  117.  
  118.             //Для каждого ключа в ячейке генерю хэш и отправляю в соот табл
  119.             for (int j = 0; j < b_i; ++j)
  120.             {
  121.                 key = nodes[i].keys[j];
  122.                 hash = uni_hash(a, b, second_table_size, key);
  123.                 this->second_tables[i][hash] = key;
  124.             }
  125.  
  126.             //Теперь проверяю на коллизции
  127.             int z = 0;
  128.             for (int k = 0; k < second_table_size; ++k)
  129.             {
  130.                 //тут надо как то понять что уже такое встречалось
  131.                 if ()
  132.                     z++;
  133.                 break;
  134.             }
  135.  
  136.             if (z == 0)
  137.                 flag = true;
  138.         }
  139.     }
  140. }
  141.  
  142. void FixedSet::print()
  143. {
  144.     cout << "\n print: \n";
  145.     for (int i = 0; i < nodes.size(); ++i)
  146.     {
  147.         cout << "i= " << i << " : ";
  148.         for (int j = 0; j < nodes[i].keys.size(); ++j)
  149.             cout << nodes[i].keys[j] << endl;
  150.     }
  151.     cout << endl;
  152. }
  153.  
  154. int main()
  155. {
  156.     cout << "Hello World";
  157.     FixedSet f;
  158.  
  159.     vector<int> numbers = { 1, 2, 3 };
  160.     f.Initialize(numbers);
  161.     // f.print();
  162.  
  163.  
  164.     return 0;
  165. }
  166.  
Add Comment
Please, Sign In to add comment