Quick access to map by key row
In the article “String enum - string enum” I wrote about how to associate textual representations with the enum class - a good method but only if all elements are known in advance, but it often happens that the strings are certain identifiers and of course are not known in advance, and often will be added later and without rebuilding the program.
Library requirements are all the same:
')
Config example
The first and simplest idea that begs is:
But again, if this is a high-loaded part of the program, then a search by map can be quite long, hashes can give the colisies something that you don’t want.
The second idea to parse this config in 2 passes then on the 2nd pass object1, object2, object3 will be already known and it will be possible to write down directly pointers or links on them. But if the dependencies are even more complex, then this approach may not work.
I propose a way to significantly reduce runtime costs of such structures.
The main idea is that each line readable from the config file will fit into a certain structure, and back we would get its unique number.
The minimal implementation of this idea looks like this.
The idea is simple there is such a line we give it an index, no, we create a new one
Next, take care of type safety.
The idea is not new code peeped in boost but as I already wrote, a minimum of dependencies.
further the most interesting
+ f-i search index without creating a new
and finally, the f-i to convert back to the string - it is slow and only suitable for logging or similar operations.
Well, finally, an example of use along with performance evaluations http://ideone.com/93fdsO
PS Yes, in most real-world problems, the value for the search is either taken from other variables or can be prepared in advance.
PPS this code, in contrast to the previous article, has not yet used this concept in real applications, so criticism and rac sentences are especially welcome.
Library requirements are all the same:
- Cross-platform;
- Minimum dependencies;
- Read speed;
- Simple syntax;
')
Config example
{ "objects": [ { "id": "object1", "events": { "event1":{ "give": {"object2": 4} }, } }, { "id": "object2", "events": { "event2":{ "give": {"object1": 3} }, }, { "id": "object3", "events": { "event3":{ "give": {"object3": 4} }, } }, The first and simplest idea that begs is:
std::map<std::string,script> events; But again, if this is a high-loaded part of the program, then a search by map can be quite long, hashes can give the colisies something that you don’t want.
The second idea to parse this config in 2 passes then on the 2nd pass object1, object2, object3 will be already known and it will be possible to write down directly pointers or links on them. But if the dependencies are even more complex, then this approach may not work.
I propose a way to significantly reduce runtime costs of such structures.
The main idea is that each line readable from the config file will fit into a certain structure, and back we would get its unique number.
The minimal implementation of this idea looks like this.
template <class T> class StringCache { public: static int get(const std::string &value) { return _values.insert(std::make_pair(value, _values.size() + 1)).first->second; } static int find(const std::string &value) { auto it =_values.find(value); return it != _values.end() ? it->second : 0; } private: static std::map<std::string,int> _values; }; template <class T> std::map<std::string,int> StringCache<T>::_values; The idea is simple there is such a line we give it an index, no, we create a new one
Next, take care of type safety.
template <class T, class ValueType> class StrongType { public: inline explicit operator ValueType() const { return _value;} inline bool operator == (const StrongType &other) const { return _value == other._value; } inline bool operator != (const StrongType &other) const { return _value != other._value; } inline bool operator < (const StrongType &other) const { return _value < other._value;; } inline bool operator > (const StrongType &other) const { return _value > other._value; } inline bool operator <= (const StrongType &other) const { return _value <= other._value; } inline bool operator >= (const StrongType &other) const { return _value >= other._value; } protected: explicit StrongType(ValueType value):_value(value) {} private: ValueType _value; }; The idea is not new code peeped in boost but as I already wrote, a minimum of dependencies.
further the most interesting
template <class T, class ValueType = int> class StringCache { public: static_assert(std::is_integral<ValueType>::value, "not integral type"); class Type: public StrongType<T,ValueType> { friend class StringCache; public: explicit Type(const std::string &value):StrongType<T,ValueType>(StringCache::get(value)){} private: explicit Type(ValueType value):StrongType<T,ValueType>(value){} }; static Type get(const std::string &value) { return Type(_values.insert(std::make_pair(value, _values.size() + 1)).first->second); } static Type find(const std::string &value) { std::map<std::string,int>::const_iterator it =_values.find(value); if(it == _values.end()) return Type(0); else return Type(it->second); } static const std::string& to_string(const Type &type) { static const std::string empty; if(static_cast<ValueType>(type)>=_values.size()) return empty; for(const auto &it:_values) if(it.second == static_cast<ValueType>(type)) return it.first; return empty; } private: static std::map<std::string,ValueType> _values; }; template <class T, class ValueType> std::map<std::string,ValueType> StringCache<T,ValueType>::_values; + f-i search index without creating a new
and finally, the f-i to convert back to the string - it is slow and only suitable for logging or similar operations.
Well, finally, an example of use along with performance evaluations http://ideone.com/93fdsO
Full test code
#include <iostream> #include <chrono> #include <map> #include <unordered_map> #include <string> #include <random> #include <algorithm> template <class T, class ValueType> class StrongType { public: inline explicit operator ValueType() const { return _value;} inline bool operator == (const StrongType &other) const { return _value == other._value; } inline bool operator != (const StrongType &other) const { return _value != other._value; } inline bool operator < (const StrongType &other) const { return _value < other._value;; } inline bool operator > (const StrongType &other) const { return _value > other._value; } inline bool operator <= (const StrongType &other) const { return _value <= other._value; } inline bool operator >= (const StrongType &other) const { return _value >= other._value; } protected: explicit StrongType(ValueType value):_value(value) {} private: ValueType _value; }; template <class T, class ValueType = int> class StringCache { public: static_assert(std::is_integral<ValueType>::value, "not integral type"); class Type: public StrongType<T,ValueType> { friend class StringCache; public: explicit operator bool() const { return static_cast<ValueType>(*this)!=0; } private: explicit Type(ValueType value):StrongType<T,ValueType>(value){} }; static Type get(const std::string &value) { return Type(_values.insert(std::make_pair(value, _values.size() + 1)).first->second); } static Type find(const std::string &value) { std::map<std::string,int>::const_iterator it =_values.find(value); if(it == _values.end()) return Type(0); else return Type(it->second); } static const std::string& to_string(const Type &type) { static const std::string empty; if(static_cast<ValueType>(type)>=_values.size()) return empty; for(const auto &it:_values) if(it.second == static_cast<ValueType>(type)) return it.first; return empty; } private: static std::map<std::string,int> _values; }; template <class T, class ValueType> std::map<std::string,int> StringCache<T,ValueType>::_values; class EventType:public StringCache<EventType>{}; class Script { public: Script(int val):_value(val) { } int execute() const { return _value; } private: int _value; }; class Object { public: int execute(const std::string &id) const { auto it = _events.find(id); if(it!=_events.end()) { return it->second.execute(); } return 0; } void addevent(const std::string &event, const Script &script) { _events.insert(std::make_pair(event, script)); } private: std::map<std::string, Script> _events; }; class HashObject { public: int execute(const std::string &id) const { auto it = _events.find(id); if(it!=_events.end()) { return it->second.execute(); } return 0; } void addevent(const std::string &event, const Script &script) { _events.insert(std::make_pair(event, script)); } private: std::unordered_map<std::string, Script> _events; }; class FastObject { public: int execute(EventType::Type id) const { auto it = _events.find(id); if(it!=_events.end()) { return it->second.execute(); } return 0; } void addevent(EventType::Type event, const Script &script) { _events.insert(std::make_pair(event, script)); } private: std::map<EventType::Type, Script> _events; }; std::vector<std::string> eventIds= { "event00", "event01", "event02", "event03", "event04", "event05", "event06", "event07", "event08", "event09", "event00", "event11", "event12", "event13", "event14", "event15", "event16", "event17", "event18", "event19", "event20", "event21", "event22", "event23", "event24", "event25" }; int main(int argc, const char * argv[]) { std::random_device rd; std::default_random_engine engine(rd()); std::vector<int> ids{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}; std::vector<Object> objects; std::vector<FastObject> fast_objects; std::vector<HashObject> hash_objects; const static int max_objects = 1000; const static int iter_count = 1000; const static int repeat_count = 1; objects.reserve(max_objects); fast_objects.reserve(max_objects); hash_objects.reserve(max_objects); for(int i=0;i<max_objects;++i) { std::shuffle(ids.begin(), ids.end(), engine); Object obj1; HashObject obj2; FastObject obj3; for(int j=0;j<10;++j) //add first 10 elemtnts not all object has all events { obj1.addevent(eventIds[ids[j]], Script(j)); obj2.addevent(eventIds[ids[j]], Script(j)); obj3.addevent(EventType::get(eventIds[ids[j]]), Script(j)); } objects.push_back(obj1); hash_objects.push_back(obj2); fast_objects.push_back(obj3); } std::vector<std::string> events; events.reserve(eventIds.size()*iter_count); for(int i=0;i<iter_count;++i) for(const auto &it:eventIds) { events.push_back(it); } int ret1 = 0; int ret2 = 0; int ret3 = 0; std::chrono::high_resolution_clock::time_point t = std::chrono::high_resolution_clock::now(); for(int i=0;i<repeat_count;++i) for(const auto &event:events) { for(const auto &object:objects) { ret1 += object.execute(event); } } auto duration = std::chrono::high_resolution_clock::now() - t; std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret1 << std::endl; t = std::chrono::high_resolution_clock::now(); for(int i=0;i<repeat_count;++i) for(const auto &event:events) { for(const auto &object:hash_objects) { ret2 += object.execute(event); } } duration = std::chrono::high_resolution_clock::now() - t; std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret2 << std::endl; t = std::chrono::high_resolution_clock::now(); for(int i=0;i<repeat_count;++i) for(const auto &event:events) { EventType::Type eventId = EventType::find(event); if(eventId) //possible that no one has this id for(const auto &object:fast_objects) { ret3 += object.execute(eventId); } } duration = std::chrono::high_resolution_clock::now() - t; std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << ":" << ret3 << std::endl; return 0; } PS Yes, in most real-world problems, the value for the search is either taken from other variables or can be prepared in advance.
class EventId:public StringCache<EventId:public>{}; if(something) { static EventId:Type event1Val = EventId:public::find("event1"); map.find(event1Val); } PPS this code, in contrast to the previous article, has not yet used this concept in real applications, so criticism and rac sentences are especially welcome.
Source: https://habr.com/ru/post/236697/
All Articles