fork download
copy 
  1. #include <iostream>
  2. #include <chrono>
  3. #include <map>
  4. #include <unordered_map>
  5. #include <string>
  6. #include <random>
  7. #include <algorithm>
  8.  
  9. template <class T, class ValueType>
  10. class StrongType
  11. {
  12. public:
  13.     inline explicit operator ValueType() const { return _value;}
  14.     inline bool operator == (const StrongType &other) const
  15.     {
  16.         return _value == other._value;
  17.     }
  18.     inline bool operator != (const StrongType &other) const
  19.     {
  20.         return _value != other._value;
  21.     }
  22.     inline bool operator < (const StrongType &other) const
  23.     {
  24.         return _value < other._value;;
  25.     }
  26.     inline bool operator > (const StrongType &other) const
  27.     {
  28.         return _value > other._value;
  29.     }
  30.     inline bool operator <= (const StrongType &other) const
  31.     {
  32.         return _value <= other._value;
  33.     }
  34.     inline bool operator >= (const StrongType &other) const
  35.     {
  36.         return _value >= other._value;
  37.     }
  38.  
  39. protected:
  40.     explicit StrongType(ValueType value):_value(value) {}
  41.  
  42. private:
  43.     ValueType _value;
  44. };
  45.  
  46. template <class T, class ValueType = int>
  47. class StringCache
  48. {
  49. public:
  50.     static_assert(std::is_integral<ValueType>::value, "not integral type");
  51.  
  52.     class Type: public StrongType<T,ValueType>
  53.     {
  54.         friend class StringCache;
  55.     public:
  56.         explicit operator bool() const { return static_cast<ValueType>(*this)!=0; }
  57.  
  58.     private:
  59.         explicit Type(ValueType value):StrongType<T,ValueType>(value){}
  60.     };
  61.  
  62.     static Type get(const std::string &value)
  63.     {
  64.         return Type(_values.insert(std::make_pair(value, _values.size() + 1)).first->second);
  65.     }
  66.  
  67.     static Type find(const std::string &value)
  68.     {
  69.         std::map<std::string,int>::const_iterator it =_values.find(value);
  70.         if(it == _values.end())
  71.             return Type(0);
  72.         else
  73.             return Type(it->second);
  74.     }
  75.  
  76.     static const std::string& to_string(const Type &type)
  77.     {
  78.         static const std::string empty;
  79.         if(static_cast<ValueType>(type)>=_values.size())
  80.             return empty;
  81.         for(const auto &it:_values)
  82.             if(it.second == static_cast<ValueType>(type))
  83.                 return it.first;
  84.         return empty;
  85.     }
  86.  
  87. private:
  88.     static std::map<std::string,int> _values;
  89. };
  90.  
  91. template <class T, class ValueType>
  92. std::map<std::string,int> StringCache<T,ValueType>::_values;
  93.  
  94.  
  95.  
  96. class EventType:public StringCache<EventType>{};
  97.  
  98. class Script
  99. {
  100. public:
  101.     Script(int val):_value(val)
  102.     {
  103.  
  104.     }
  105.     int execute() const
  106.     {
  107.         return _value;
  108.     }
  109. private:
  110.     int _value;
  111. };
  112.  
  113. class Object
  114. {
  115. public:
  116.     int execute(const std::string &id) const
  117.     {
  118.         auto it = _events.find(id);
  119.         if(it!=_events.end())
  120.         {
  121.             return it->second.execute();
  122.         }
  123.         return 0;
  124.     }
  125.     void addevent(const std::string &event, const Script &script)
  126.     {
  127.         _events.insert(std::make_pair(event, script));
  128.     }
  129. private:
  130.     std::map<std::string, Script> _events;
  131. };
  132.  
  133. class HashObject
  134. {
  135. public:
  136.     int execute(const std::string &id) const
  137.     {
  138.         auto it = _events.find(id);
  139.         if(it!=_events.end())
  140.         {
  141.             return it->second.execute();
  142.         }
  143.         return 0;
  144.     }
  145.     void addevent(const std::string &event, const Script &script)
  146.     {
  147.         _events.insert(std::make_pair(event, script));
  148.     }
  149. private:
  150.     std::unordered_map<std::string, Script> _events;
  151. };
  152.  
  153. class FastObject
  154. {
  155. public:
  156.     int execute(EventType::Type id) const
  157.     {
  158.         auto it = _events.find(id);
  159.         if(it!=_events.end())
  160.         {
  161.             return it->second.execute();
  162.         }
  163.         return 0;
  164.     }
  165.     void addevent(EventType::Type event, const Script &script)
  166.     {
  167.         _events.insert(std::make_pair(event, script));
  168.     }
  169. private:
  170.     std::map<EventType::Type, Script> _events;
  171. };
  172.  
  173. struct event_descriptor
  174. {
  175.     std::string str;
  176.     size_t hash;
  177.     bool operator ==(const event_descriptor&other) const
  178.     {
  179.         return other.hash == hash && other.str == str;
  180.     }
  181.     bool operator <(const event_descriptor&other) const
  182.     {
  183.         return (hash==other.hash)?str<other.str:(hash<other.hash);
  184.     }
  185. };
  186.  
  187. struct descriptor_hasher
  188. {
  189.     size_t operator()(const event_descriptor& desc) const { return desc.hash; };
  190. };
  191.  
  192. event_descriptor make_descriptor(const std::string &arg)
  193. {
  194.     auto hash = std::hash<std::string>()(arg);
  195.     return event_descriptor{arg, hash};
  196. }
  197.  
  198. class HashObject2
  199. {
  200. public:
  201.     int execute(const event_descriptor &id) const
  202.     {
  203.         auto it = _events.find(id);
  204.         if(it!=_events.end())
  205.         {
  206.             return it->second.execute();
  207.         }
  208.         return 0;
  209.     }
  210.     void addevent(const event_descriptor &event, const Script &script)
  211.     {
  212.         _events.insert(std::make_pair(event, script));
  213.     }
  214. private:
  215.     std::unordered_map<event_descriptor, Script, descriptor_hasher> _events;
  216. };
  217.  
  218. class HashObject3
  219. {
  220. public:
  221.     int execute(const event_descriptor &id) const
  222.     {
  223.         auto it = _events.find(id);
  224.         if(it!=_events.end())
  225.         {
  226.             return it->second.execute();
  227.         }
  228.         return 0;
  229.     }
  230.     void addevent(const event_descriptor &event, const Script &script)
  231.     {
  232.         _events.insert(std::make_pair(event, script));
  233.     }
  234. private:
  235.     std::map<event_descriptor, Script> _events;
  236. };
  237.  
  238. std::vector<std::string> eventIds= {
  239.     "event00",
  240.     "event01",
  241.     "event02",
  242.     "event03",
  243.     "event04",
  244.     "event05",
  245.     "event06",
  246.     "event07",
  247.     "event08",
  248.     "event09",
  249.     "event00",
  250.     "event11",
  251.     "event12",
  252.     "event13",
  253.     "event14",
  254.     "event15",
  255.     "event16",
  256.     "event17",
  257.     "event18",
  258.     "event19",
  259.     "event20",
  260.     "event21",
  261.     "event22",
  262.     "event23",
  263.     "event24",
  264.     "event25"
  265. };
  266.  
  267. int main(int argc, const char * argv[])
  268. {
  269.     std::random_device rd;
  270.     std::default_random_engine engine(rd());
  271.     std::vector<int> ids{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
  272.  
  273.     std::vector<Object> objects;
  274.     std::vector<FastObject> fast_objects;
  275.     std::vector<HashObject> hash_objects;
  276.     std::vector<HashObject2> hash_objects2;
  277.     std::vector<HashObject3> hash_objects3;
  278.  
  279.     const static int max_objects = 1000;
  280.     const static int iter_count = 100;
  281.     const static int repeat_count = 1;
  282.  
  283.     objects.reserve(max_objects);
  284.     fast_objects.reserve(max_objects);
  285.     hash_objects.reserve(max_objects);
  286.     hash_objects2.reserve(max_objects);
  287.  
  288.     for(int i=0;i<max_objects;++i)
  289.     {
  290.         std::shuffle(ids.begin(), ids.end(), engine);
  291.         Object obj1;
  292.         HashObject obj2;
  293.         FastObject obj3;
  294.         HashObject2 obj4;
  295.         HashObject3 obj5;
  296.         for(int j=0;j<10;++j) //add first 10 elemtnts not all object has all events
  297.         {
  298.             obj1.addevent(eventIds[ids[j]], Script(j));
  299.             obj2.addevent(eventIds[ids[j]], Script(j));
  300.             obj3.addevent(EventType::get(eventIds[ids[j]]), Script(j));
  301.             obj4.addevent(make_descriptor(eventIds[ids[j]]), Script(j));
  302.             obj5.addevent(make_descriptor(eventIds[ids[j]]), Script(j));
  303.         }
  304.         objects.push_back(obj1);
  305.         hash_objects.push_back(obj2);
  306.         fast_objects.push_back(obj3);
  307.         hash_objects2.push_back(obj4);
  308.         hash_objects3.push_back(obj5);
  309.     }
  310.  
  311.     std::vector<std::string> events;
  312.  
  313.     events.reserve(eventIds.size()*iter_count);
  314.  
  315.     for(int i=0;i<iter_count;++i)
  316.         for(const auto &it:eventIds)
  317.         {
  318.             events.push_back(it);
  319.         }
  320.  
  321.     int ret1 = 0;
  322.     int ret2 = 0;
  323.     int ret3 = 0;
  324.     int ret4 = 0;
  325.     int ret5 = 0;
  326.  
  327.     std::chrono::high_resolution_clock::time_point t = std::chrono::high_resolution_clock::now();
  328.     for(int i=0;i<repeat_count;++i)
  329.     for(const auto &event:events)
  330.     {
  331.         for(const auto &object:objects)
  332.         {
  333.             ret1 += object.execute(event);
  334.         }
  335.     }
  336.     auto duration = std::chrono::high_resolution_clock::now() - t;
  337.     std::cout << "map:                            " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret1 << std::endl;
  338.  
  339.     t = std::chrono::high_resolution_clock::now();
  340.     for(int i=0;i<repeat_count;++i)
  341.         for(const auto &event:events)
  342.         {
  343.             for(const auto &object:hash_objects)
  344.             {
  345.                 ret2 += object.execute(event);
  346.             }
  347.         }
  348.     duration = std::chrono::high_resolution_clock::now() - t;
  349.     std::cout << "unodered_map:                   " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret2 << std::endl;
  350.  
  351.     t = std::chrono::high_resolution_clock::now();
  352.     for(int i=0;i<repeat_count;++i)
  353.     for(const auto &event:events)
  354.     {
  355.         EventType::Type eventId = EventType::find(event);
  356.         if(eventId) //possible that no one has this id
  357.             for(const auto &object:fast_objects)
  358.             {
  359.                 ret3 += object.execute(eventId);
  360.             }
  361.     }
  362.     duration = std::chrono::high_resolution_clock::now() - t;
  363.     std::cout << "map+EventType:                  " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret3 << std::endl;
  364.  
  365.     t = std::chrono::high_resolution_clock::now();
  366.     for(int i=0;i<repeat_count;++i)
  367.         for(const auto &event:events)
  368.         {
  369.             event_descriptor eventId1 = make_descriptor(event);
  370.             for(const auto &object:hash_objects2)
  371.             {
  372.                 ret4 += object.execute(eventId1);
  373.             }
  374.         }
  375.     duration = std::chrono::high_resolution_clock::now() - t;
  376.     std::cout << "unordered_map+event_descriptor: " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret4 << std::endl;
  377.  
  378.     t = std::chrono::high_resolution_clock::now();
  379.     for(int i=0;i<repeat_count;++i)
  380.         for(const auto &event:events)
  381.         {
  382.             event_descriptor eventId2 = make_descriptor(event);
  383.             for(const auto &object:hash_objects3)
  384.             {
  385.                 ret5 += object.execute(eventId2);
  386.             }
  387.         }
  388.     duration = std::chrono::high_resolution_clock::now() - t;
  389.     std::cout << "map+event_descriptor:           " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret5 << std::endl;
  390.  
  391.  
  392.     return 0;
  393. }
  394.  
  395.  
Success #stdin #stdout 0.96s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
map:                            265:4652600
unodered_map:                   220:4652600
map+EventType:                  93:4652600
unordered_map+event_descriptor: 189:4652600
map+event_descriptor:           173:4652600
https://ideone.com/Dk1QNm
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!