Идеальная хеш-функция для заранее известных строк
У меня 4000 строк, и я хочу создать идеальную хэш-таблицу с этими строками. Строки известны заранее, поэтому моей первой идеей было использовать серию if заявления:
if (name=="aaa")
return 1;
else if (name=="bbb")
return 2;
.
.
.
// 4000th `if' statement
Однако это было бы очень неэффективно. Есть ли способ лучше?
Решение
gperf это инструмент, который делает именно это:
GNU
gperfявляется идеальным генератором хеш-функций. Для заданного списка строк он создает хеш-функцию и хеш-таблицу в форме кода на C или C ++ для поиска значения в зависимости от входной строки. Хеш-функция идеальна, что означает, что хеш-таблица не имеет коллизий, а для поиска в хеш-таблице требуется только сравнение одной строки.
Согласно документации, gperf используется для генерации зарезервированного распознавателя ключевых слов для лексеров в GNU C, GNU C ++, GNU Java, GNU Pascal, GNU Modula 3 и отступе GNU.
Как это работает, описано в GPERF: идеальный генератор хеш-функций Дуглас С. Шмидт.
Другие решения
Я считаю, что ответ @ NPE очень разумный, и я сомневаюсь, что это слишком много для вашего приложения как вы, похоже, подразумеваете.
Рассмотрим следующий пример: предположим, что ваша логика «движка» (то есть функциональность вашего приложения) содержится в файле с именем engine.hpp:
// this is engine.hpp
#pragma once
#include <iostream>
void standalone() {
std::cout << "called standalone" << std::endl;
}
struct Foo {
static void first() {
std::cout << "called Foo::first()" << std::endl;
}
static void second() {
std::cout << "called Foo::second()" << std::endl;
}
};
// other functions...
и предположим, что вы хотите отправить различные функции в зависимости от карты:
"standalone" dispatches void standalone()
"first" dispatches Foo::first()
"second" dispatches Foo::second()
# other dispatch rules...
Вы можете сделать это, используя следующий входной файл gperf (я назвал его «lookups.gperf»):
%{
#include "engine.hpp"
struct CommandMap {
const char *name;
void (*dispatch) (void);
};
%}
%ignore-case
%language=C++
%define class-name Commands
%define lookup-function-name Lookup
struct CommandMap
%%
standalone, standalone
first, Foo::first
second, Foo::second
Затем вы можете использовать gperf для создания lookups.hpp файл с помощью простой команды:
gperf -tCG lookups.gperf > lookups.hpp
Как только я это сделаю, main Подпрограмма будет отправлять команды в зависимости от того, что я печатаю:
#include <iostream>
#include "engine.hpp" // this is my application engine
#include "lookups.hpp" // this is gperf's output
int main() {
std::string command;
while(std::cin >> command) {
auto match = Commands::Lookup(command.c_str(), command.size());
if(match) {
match->dispatch();
} else {
std::cerr << "invalid command" << std::endl;
}
}
}
Скомпилируйте это:
g++ main.cpp -std=c++11
и запустить его:
$ ./a.out
standalone
called standalone
first
called Foo::first()
Second
called Foo::second()
SECOND
called Foo::second()
first
called Foo::first()
frst
invalid command
Обратите внимание, что как только вы сгенерировали lookups.hpp Ваше приложение не имеет никакой зависимости от gperf.
Отказ от ответственности: я взял вдохновение для этого примера от этот сайт.
Поскольку на вопрос до сих пор нет ответа, и я собираюсь добавить ту же функциональность к моей платформе HFT, я поделюсь своим инвентарем для Идеальные алгоритмы хеширования в C ++. Сложнее было подумать о том, чтобы найти открытую, гибкую и свободную от ошибок реализацию, поэтому я делюсь тем, что еще не уронил:
- Библиотека CMPH, с коллекцией статей и таких алгоритмов — https://git.code.sf.net/p/cmph/git
- BBHash, еще одна реализация от автора статьи — https://github.com/rizkg/BBHash
- Адемакова — еще одна реализация из статьи выше — https://github.com/ademakov/PHF
- wahern / phf — в настоящее время я проверяю это и пытаюсь устранить некоторые ошибки выделения, которые есть при работе со строками C ++ на огромных наборах ключей — https://github.com/wahern/phf.git
- emphf — кажется, не поддерживается https://github.com/ot/emphf.git