newnon13 сен 2014 в 17:32

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

7 мин

21K

Программирование * C++ *

Комментарии 28

wait 13 сен 2014 в 18:42

Если я не путаю — подобный способ используется при работе со строками в Unreal Engine (второй версии).

zed_0xff 13 сен 2014 в 18:51

Вы изобрели то что в Ruby называется Symbol.

PS: en.wikipedia.org/wiki/String_interning

newnon 13 сен 2014 в 19:04

Да идея похожа слегка но служит немного другим целям, тем не менее программисты хотят поиск по int, а геймдизайнеры строковые ключи в конфигах.

Flux 14 сен 2014 в 18:20

Если нужна индексация по заранее неизвестным строковым ключам в рантайме то ничего быстрее чем Trie придумать нельзя. Вставка, поиск и удаление за О(|S|), а быстрее строку мы прочитать не можем.

newnon 14 сен 2014 в 18:30

Спасибо за наводку.

khim 14 сен 2014 в 20:11

Это теория. «В теории — теория и практика одинаковы, однако на практике это не так».

На практике у вас «O большое» может сработать на таких размерах, которые вы не увидите никогда и ни за что. Потому что за время, пока вы прочитаете один байт из оперативной памяти процессор может исполнять пару тысяч инструкций. Да и строки у вас, не случайны, а что-то типа английского или русского языка.

На эту тему достаточно много в последнее время есть материалов. Хотя всё вертится обычно всё равно вокруг какой-нибудь версии trie. Начиная с классических Judy tree и далее — к более практическим Judy Array и HatTrie.

Хотя всё это крохоборство: я бы не стал всем этим заморачиваться пока замеры бы не показали, что вот именно в map<string, int> у нас затык.

bak 13 сен 2014 в 19:41

Вы непонятно зачем изобрели какой-то темплейтный треш и привели бредовые тесты в качестве аргументации.
В случае с вашим хешом — вы делаете резолвинг строки в id-шник ровно один раз за тест.
В случае со обычным мапом — у вас делается поиск строки в rb-дереве на каждую итерацию.
Если ваш юзкейс — частое обращение по строкам, то в вашем тесте ошибка — сотрите static в test1 и test2 и убедитесь что ваш велосипед сливает.
Если ваш юзкейс — я готов хранить что-то, чтобы потом быстро обращаться — загрузите всё в вектор и храните указатели (или индексы элементов в векторе если вам важны именно чиселки от 0 и дальше по порядку).
P. S. Сори за резкость, у меня бэтхёрт от кривых велосипедов на ровном месте.

newnon 14 сен 2014 в 07:13

Да соглашусь пример не очень удачно иллюстрировал случай когда использование данного приема оправдано, заменил в статье на новую ссылку новый пример. Сразу уточню содержимое events заранее не известно, потому как в реальности поимо логики в коде сам класс Script тоже може добавлять туда элементы, так же не известны ни eventIds, ни список событий на который реагирует данный объект. Поэтому харанее включить указатель или ссылку на сущности не получится. Также на практике возможно укладывать в events сразу EventType так как во многих случаях он известен на этапе создания программы.

    if(some_condition)
    {
        static EventType::Type some_type = EventType::find("some_id");
        events.push_pack(some_type);
    }

В новом примере прирост производительности где-то около 3-х раз, если у вас есть мысли как сделать тоже самое проще или быстрее буду очень благодарен за совет.

bak 14 сен 2014 в 10:05

А… я понял. У вас есть следующая архитектура (с описания которой и стоило начать статью, а не заставлять читателей пытаться понять, что же вы хотели сказать):
— у вас есть три сущности — набор событий, набор объектов и набор скриптов.
— события — строковые наименования. объекты — некоторые внутриигровые объекты которые умееют выполнять скрипты
— вы хотите чтобы каждый объект мог подписаться на некоторые события по которым он будет выполнять разные скрипты.
Но тогда, во первых, даже тот механизм что вы описали записывается намного компактней с использованием тех же указателей: pastebin.com/pi20L4JN && ideone.com/adx4v8 (весь ваш монструозные stringcache уложился в 10-и строчную обвязку над хеш-сетом).
И во вторых, на мой взгляд, у вас проблемы с архитектурой (для конкретики надо смотреть код проекта в котором вы это используете).

newnon 14 сен 2014 в 15:23

Во первых в вашем случае нужно чтобы экземпляр TEventStorer был доступен из той же единицы трансляции, в заголовочном файле экземпляр объявить нельзя получим ошибку на этапе линковки. Поэтому придется делать некий синглтон и метод его получения. Мой вариант со статическими методами и static гарантирует что на этапе сборки в код попадет только один инстант шаблона для каждого типа. Далее половина моего кода это всего навсего безопасный тип, на скорость выполнения не влияющий. зато помогает найти ошибки еще на этапе компиляции. Если убрать из моего кода типобезопасность и дополнительные методы то получается 15 строк

bak 15 сен 2014 в 16:52

Чем плох хранить список допустимых event-ов в отдельном файле и генерить по нему perfect hash? При желании, можете скриптом все имена event-ов повыдёргивать из ваших игровых скриптов. Или у вас внутри игровых скриптов эти самые имена ивентов делаются с использованием сложной логики?

newnon 16 сен 2014 в 07:01

Perfect hash насколько я понимаю надо зашивать в код а конфиги живут отдельно от кода, придется каждый раз при изменении конфигов код пересобирать, а возможет вариант, когда на существующую версию приложения просто выходит патчик в ввиде правки конфигов.

Amomum 13 сен 2014 в 22:03

Для быстрого поиска по строке можно еще вспомнить про tries и TST.

Yfka 14 сен 2014 в 10:33

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

std::map<std::string, Script> _events;

Колизии? Ну-ну.
А если подумать? Или проверить НАСКОЛЬКО хэш контейнер в реальности быстрее чем дерево.

std::hash_map<std::string, Script> _events;

Или на C++11:

std::unordered_map<std::string, Script> _events;

И не надо глючных велосипедов.

(По секрету: есть ещё быстрее чем unordered_map)

newnon 14 сен 2014 в 15:29

Добавил для сравнения тот же код только с unordered_map новый пример а под MaC Os производительность с unrodered_map получилась даже на 5% хуже. А про колизии я говорил только в случае если хранить в качестве ключа только хэш.

Wyrd 15 сен 2014 в 10:07

Это потому что у вас хеш от строки при каждом поиске считается. Я бы попробовал обернуть std::string, чтобы хеш хранился вместе со «строкой».

newnon 15 сен 2014 в 14:07

Придется тогда и контейнер другой писать так как unordered_map после проверки по хэшу, если они совпали проверяет еще и на равенство элементов, поэтому ему нужно и хэш и элемент.

Wyrd 15 сен 2014 в 15:22

Мое предложение было хранить Хеш и элемент в одном месте, тогда можно использовать unordered_map:

что-то вроде:

#include <string>

#include <unordered_map>

#include <tuple>

#include <iostream>

struct Script { int Dummy; Script(int dummy = 0) { Dummy = dummy; } };

typedef const std::pair<const std::string, const size_t> descriptor;

struct descriptor_hasher

{

    size_t operator()(const descriptor& desc) const { return desc.second; };

};

descriptor make_descriptor(std::string arg)

{

    auto hash = std::hash<std::string>()(arg);

    return std::make_pair(std::move(arg), hash);

}

int main(int argc, const char * argv[])

{

    std::unordered_map<descriptor, Script, descriptor_hasher> hash_map;

    static const descriptor event_descriptor = make_descriptor("test");

    // insert

    hash_map[event_descriptor] = Script(42);

    // get

    auto it = hash_map.find(event_descriptor);

    std::cout << it->second.Dummy << std::endl;

}

newnon 16 сен 2014 в 07:50

Ваше решение дало некоторый выигрыш относительно обычных map и unordered_map, но оказался медленнее предложенного мною варианта. Сравнение Хотя хочу отметить что оно мне нравится за свою простоту.