Guest User

ha

a guest
Mar 18th, 2021
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. /*
  2.  * Built with g++ -O2 -std=c++11 -Wall -Wpedantic
  3.  * produces results like:
  4.  
  5. Linear Scan: 5 ms
  6. Hashmap:     14 ms
  7.  
  8.  * Probably due to the higher cost of computing the hash than to
  9.  * comparing the strings.
  10. */
  11.  
  12.  
  13. #include <string>
  14. #include <vector>
  15. #include <unordered_map>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <iostream>
  19. #include <stdexcept>
  20.  
  21. typedef unsigned char day_t;
  22.  
  23. // vector is an array, so equivilent to Java's ArrayList
  24. std::vector<std::string> days_vector {
  25.     "Monday",
  26.     "Tuesday",
  27.     "Wednesday",
  28.     "Thursday",
  29.     "Friday",
  30.     "Saturday",
  31.     "Sunday"
  32. };
  33.  
  34. // unorderd map is a hash map implementation.
  35. std::unordered_map<std::string, day_t> days_map {
  36.     {"Monday", 0},
  37.     {"Tuesday", 1},
  38.     {"Wednesday", 2},
  39.     {"Thursday", 3},
  40.     {"Friday", 4},
  41.     {"Saturday", 5},
  42.     {"Sunday", 6}
  43. };
  44.  
  45. // use a separate vector to avoid pointer equality.
  46. std::vector<std::string> days_vector2 {
  47.     "Monday",
  48.     "Tuesday",
  49.     "Wednesday",
  50.     "Thursday",
  51.     "Friday",
  52.     "Saturday",
  53.     "Sunday"
  54. };
  55.  
  56. bool GetDayOfWeekFromString_LinearScan(const std::string& text, day_t& day) {
  57.  
  58.     auto r = std::find(days_vector.begin(), days_vector.end(), text);
  59.     if (r != days_vector.end()) {
  60.         day = (day_t)( r - days_vector.begin() );
  61.         return true;
  62.     }
  63.     else {
  64.         return false;
  65.     }
  66. }
  67.  
  68. bool GetDayOfWeekFromString_HashMap(const std::string& text, day_t& day) {
  69.    
  70.     auto r = days_map.find(text);
  71.     if (r != days_map.end()) {
  72.         day = r->second;
  73.         return true;
  74.     } else {
  75.         return false;
  76.     }
  77.        
  78. }
  79.  
  80. typedef bool foo_t(const std::string& text, day_t& day);
  81.  
  82. double test(const foo_t& alg, int iterations) {
  83.    
  84.     std::clock_t start_time = std::clock();
  85.    
  86.     for (int i = 0; i < iterations; ++i) {
  87.        
  88.         int idx = std::rand() % 7;
  89.         std::string& dayString = days_vector2[idx];
  90.         day_t foundDay;
  91.         bool ok = alg(dayString, foundDay);
  92.         if (!ok || (foundDay != idx)) throw std::runtime_error("fail");
  93.     }
  94.    
  95.     std::clock_t end_time = std::clock();
  96.     double duration = (end_time - start_time) / (double) CLOCKS_PER_SEC;
  97.     return duration * 1000.0; // ms
  98. }
  99.  
  100.  
  101. int main(void) {
  102.    
  103.     const int iterations = 100000;
  104.     try {
  105.  
  106.         std::cout << "Linear Scan: "
  107.             << test(GetDayOfWeekFromString_LinearScan, iterations)
  108.             << " ms" << std::endl;
  109.            
  110.         std::cout << "Hashmap:     "
  111.             << test(GetDayOfWeekFromString_HashMap, iterations)
  112.             << " ms" << std::endl;
  113.  
  114.     } catch (const std::exception& e) {
  115.         std::cerr << e.what() << std::endl;
  116.     }
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment