ライブラリの要件はすべて同じです。
- クロスプラットフォーム。
- 最小依存関係;
- 読み取り速度。
- 簡単な構文
構成例
{ "objects": [ { "id": "object1", "events": { "event1":{ "give": {"object2": 4} }, } }, { "id": "object2", "events": { "event2":{ "give": {"object1": 3} }, }, { "id": "object3", "events": { "event3":{ "give": {"object3": 4} }, } },
これを請う最初で最も簡単なアイデアは次のとおりです。
std::map<std::string,script> events;
しかし、これがプログラムの負荷が高い部分である場合、マップ検索は非常に長くなる可能性があり、ハッシュはまったく不要な衝突を引き起こす可能性があります。
2番目のアイデアは、2回のパスでこの構成を解析することです。2回目のパスでは、object1、object2、object3が既に認識されており、それらに直接ポインターまたはリンクを書き込むことができます。 しかし、依存関係がさらに複雑な場合、そのようなアプローチは機能しない可能性があります。
このような設計のランタイムコストを大幅に削減する方法を提案します
主なアイデアは、設定から減算された各行が特定の構造にヒットし、その固有の番号を取得することです。
このアイデアの最小限の実装は次のようになります
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;
アイデアは単純です;そのような行があります;そのインデックスを与えます;いいえ、新しいものを作成します
次に、タイプセーフティを処理します。
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 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番目-遅く、ロギングまたは同様の操作にのみ適しています。
そして最後に、パフォーマンスの評価とともに使用例http://ideone.com/93fdsO
完全なテストコード
#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はい、ほとんどの実際のタスクでは、検索の値は他の変数から取得されるか、事前に準備することができます。
class EventId:public StringCache<EventId:public>{}; if(something) { static EventId:Type event1Val = EventId:public::find("event1"); map.find(event1Val); }
PPSこのコードは、実際のアプリケーションの以前の記事とは異なり、この概念はまだ使用されていないため、批判とネズミの提案は特に歓迎されます。