У меня есть набор функций C ++. Я хочу отобразить эти функции в хэш-таблице, что-то вроде: unordered_map<function<ReturnType (Args...)> , SomethingElse>
, где SomethingElse
не имеет отношения к этому вопросу.
Этот набор функций ранее известен, маленький (скажем, менее 50) и статический (не изменится).
Поскольку производительность поиска имеет решающее значение (должны быть выполнены в O(1)
), Я хочу определить идеальную функцию хеширования.
Существует ли идеальный генератор хеш-функций для этого сценария?
Я знаю, что существуют совершенные генераторы хеш-функций (например, Gperf или же CMPH) но так как я никогда не использовал их, я не знаю, подходят ли они для моего случая.
ПРИЧИНА:
Я пытаюсь разработать структуру, где, учитывая программу, написанную на C ++, пользователь может выбрать подмножество F
функций, определенных в этой программе.
Для каждого f
принадлежность к F
, структура реализует мемоизации стратегия: когда мы называем f
с вводом i
мы храним (i,o)
внутри некоторой структуры данных. Итак, если мы собираемся позвонить снова f
с i
, мы вернемся o
без повторного выполнения (дорогостоящего времени) вычисления.
«Уже рассчитанные результаты» будут доступны для разных пользователей (возможно, в облаке), поэтому, если пользователь u1
уже вычислил o
пользователь u2
сэкономит время вычислений f
с i
(используя ту же аннотацию до).
Очевидно, нам нужно хранить множество пар (f,inputs_sets)
(где inputs_sets
это уже вычисленный набор результатов, о котором я говорил ранее), это оригинальный вопрос: как мне это сделать?
Таким образом, использование «трюка перечисления», предложенного в комментариях к этому сценарию, могло бы стать решением, предполагая, что все пользователи используют точно такой же перечисление, что может быть проблемой: предположим, что наша программа имеет f1
,f2
,f3
что, если u1
хочет только запомнить f1
а также f2
(так F={f1,f2}
), в то время как u2
хочет только запомнить f3
(так F={f3}
)? Решением излишней может быть перечисление всех функций, определенных в программе, но это может привести к огромным потерям памяти.
Хорошо, возможно, не то, что вы хотите услышать, но подумайте об этом: поскольку вы говорите о нескольких функциях, менее 50, поиск хеша должен быть незначительным даже при столкновениях. Вы на самом деле профилировали и видели, что поиск имеет решающее значение?
Поэтому я советую сосредоточить свою энергию на чем-то другом, скорее всего, идеальная хеш-функция не принесет какого-либо улучшения производительности в вашем случае.
Я собираюсь сделать еще один шаг вперед и сказать, что я считаю, что для менее чем 50 элементов плоская карта vector
) будет иметь аналогичную производительность (или, возможно, даже лучше из-за локальности кэша). Но опять же, измерения необходимы.
Других решений пока нет …