Pull to refresh

Быстрый доступ к map по ключу строке

Reading time 7 min
Views 20K
В статье «String enum — строковые enum» я писал о том как связывать текстовые представления с enum class — метод хороший но только если все элементы заранее известны, но зачастую бывает что строки являются некими идентификаторами и конечно же заранее не известны, а зачастую будут добавляться позднее и причем без пересборки программы.

Требования к библиотеке все теже:

  • Кроссплатформенность;
  • Минимум зависимостей;
  • Скорость чтения;
  • Простой синтаксис;


Пример конфига
{
    "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;

Но опять же если это высоконагруженная часть программы то поиск по map может быть достаточно долгим, хэши могут дать колизии чего совсем не хочется.

Вторая идея парсить этот конфиг в 2 прохода тогда на 2-м проходе object1, object2, object3 будут уже известны и можно будет записать на них прямо указатели или ссылки. Но если зависимости еще более сложные то такой подход может и не сработать.

Я предлагаю способ позволяющий существенно сократить runtime издержки подобных конструкций


Основная идея в том чтобы каждая строка вычитываемая из конфига поподала в некую структуру а назад мы бы получали ее уникальный номер.
Минимальная реализаци данной идеи выглядит примерно так
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;
};


Идея не нова код подсмотрен в boost но как я уже писал, минимум зависимостей.

далее самое интересное
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;

+ ф-я поиска индекса без создания нового
ну и наконец ф-я для преобразования обратно в строку — она медленная и подходит только для логирования или подобных операций.

Ну и наконец пример использования вместе с оценами производительности 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;
}




P.S. Да в большинстве реальных задач значение для поиска либо берется из других переменных либо можно заранее подготовить.
class EventId:public StringCache<EventId:public>{};
if(something)
{
    static EventId:Type event1Val = EventId:public::find("event1");
    map.find(event1Val);
}


P.P.S этот код в отличие от прошлой статьи в реальных приложениях пока не использовался это концепт, поэтому критика и рац-предложения приветствуются особо.
Tags:
Hubs:
+8
Comments 28
Comments Comments 28

Articles