Advertisement
fsb4000

c++ hashmap

Feb 28th, 2020
674
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.29 KB | None | 0 0
  1. // This is a personal academic project. Dear PVS-Studio, please check it.
  2. // PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
  3. #include <numeric>
  4. #include <algorithm>
  5. #include <string>
  6. #include <vector>
  7. #include <chrono>
  8. #include <random>
  9. #include <iostream>
  10. #include <array>
  11. #include <mutex>
  12. #include <thread>
  13. #include <unordered_set>
  14. #include <string_view>
  15. #include <cassert>
  16.  
  17. using namespace std;
  18.  
  19. void update_str(string& s)
  20. {
  21.     constexpr array<char, 63> alphabet{ "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" };
  22.     random_device r;
  23.     default_random_engine gen(r());
  24.     uniform_int_distribution<size_t> dis(0, alphabet.size() - 2); // оба конца диапазона включаются, не учитываем '\0'
  25.  
  26.     for_each(s.begin(), s.end(),
  27.         [&](auto& c)
  28.         {
  29.             c = alphabet.at(dis(gen));
  30.         }
  31.     );
  32. }
  33.  
  34. class random_string20 : public string
  35. {
  36. public:
  37.     random_string20()
  38.     {
  39.         resize(20);
  40.         update_str(*this);
  41.     }
  42. };
  43.  
  44.  
  45. void update_vector(vector<string>& v)
  46. {
  47.     for_each(
  48.         v.begin(), v.end(),
  49.         [](string& s)
  50.         {
  51.             update_str(s);
  52.         }
  53.     );
  54. }
  55.  
  56. size_t test(vector<string>& vector_string100)
  57. {
  58.     auto result = size_t(0);
  59.     auto begin = chrono::high_resolution_clock::now();
  60.     update_vector(vector_string100);
  61.     auto end = chrono::high_resolution_clock::now();
  62.     {
  63.         cout << "String generation time: "
  64.             << chrono::duration_cast<chrono::milliseconds>
  65.             (end - begin).count() << '\n';
  66.         // как будут готовы range, заменить на ranges
  67.         array<int, 1000> const range{};
  68.         /////////////////////////////////////////////////////
  69.         begin = chrono::high_resolution_clock::now();
  70.         unordered_set<string_view> hash_set;
  71.         hash_set.reserve(81 * vector_string100.size());
  72.         for (auto&& s : vector_string100)
  73.         {
  74.             assert(s.size() >= 19);
  75.             for (size_t i = 0; i < s.size() - 19; ++i)
  76.             {
  77.                 hash_set.insert(string_view(&s.at(i), 20));
  78.             }
  79.         }
  80.         end = chrono::high_resolution_clock::now();
  81.         cout << "Hash generation time: "
  82.             << chrono::duration_cast<chrono::milliseconds>
  83.             (end - begin).count() << '\n';
  84.         /////////////////////////////////////////////////////
  85.         begin = chrono::high_resolution_clock::now();
  86.         result = accumulate(
  87.             range.begin(), range.end(),
  88.             size_t(0),
  89.             [&](size_t acc, size_t)
  90.             {
  91.                 random_string20 const s20;
  92.                 auto const iter = hash_set.find(s20);
  93.                 bool const found = (iter != hash_set.end());
  94.                 return found ? acc + 1 : acc;
  95.             }
  96.         );
  97.         end = chrono::high_resolution_clock::now();
  98.         cout << "Substring search time: "
  99.             << chrono::duration_cast<chrono::milliseconds>
  100.             (end - begin).count() << '\n';
  101.         begin = chrono::high_resolution_clock::now();
  102.     }
  103.     end = chrono::high_resolution_clock::now();
  104.     cout << "Hashmap destructor time: "
  105.         << chrono::duration_cast<chrono::milliseconds>
  106.         (end - begin).count() << '\n';
  107.     return result;
  108. }
  109.  
  110. int main()
  111. {
  112.     for (int i = 0; i < 10; ++i)
  113.     {
  114.         auto const begin = chrono::high_resolution_clock::now();
  115.         vector<string> vector_string100(100000, string(100, ' '));
  116.         size_t const matches = test(vector_string100);
  117.         auto const end = chrono::high_resolution_clock::now();
  118.         cout << matches << " strings matches, time = "
  119.             << chrono::duration_cast<chrono::milliseconds>
  120.             (end - begin).count() << "\n\n\n";
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement