Best tools no one uses: gperf

В природе есть масса отличных инструментов, которые мало кто использует. Очередной раз применив в бою один из таких, решил начать про них рассказывать. Сегодня на повестке программа с обманчивым именем gperf – GNU is not Unix, and gperf is not a performance profiler.

gperf это генератор идеальных хеш-функций. Идеальность заключается в том, что в хеш таблице не будет ни одной коллизии, те. поиск ключа стоит примерно одно строковое сравнение (иногда меньше). На входе gperf хочет тупой список ключевых слов, для которых строится хеш:

[code lang="cpp"]
struct month { char *name; int number; int days; int leap_days; };
%%
january, 1, 31, 31
february, 2, 28, 29
march, 3, 31, 31
april, 4, 30, 30
may, 5, 31, 31
june, 6, 30, 30
july, 7, 31, 31
august, 8, 31, 31
september, 9, 30, 30
october, 10, 31, 31
november, 11, 30, 30
december, 12, 31, 31
[/code]

На выходе несложной команды gperf -t sample.p –output-file sample.c получается вот такое (код слегка очищен от #if для простоты восприятия):

[code lang="cpp"]
struct month { char *name; int number; int days; int leap_days; };

#define TOTAL_KEYWORDS 12
#define MIN_WORD_LENGTH 3
#define MAX_WORD_LENGTH 9
#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 18

static unsigned int hash ( const char * str, int len )
{
static unsigned char asso_values[] =
{
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 5, 5, 5,
0, 19, 5, 0, 19, 19, 0, 19, 10, 0,
0, 5, 0, 19, 0, 0, 0, 19, 0, 19,
19, 0, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19
};
return len + asso_values[(unsigned char)str[2]] + asso_values[(unsigned char)str[0]];
}

struct month * in_word_set ( const char * str, int len )
{
static struct month wordlist[] =
{
{""}, {""}, {""},
{"may", 5, 31, 31},
{"june", 6, 30, 30},
{"march", 3, 31, 31},
{""},
{"january", 1, 31, 31},
{"november", 11, 30, 30},
{"september", 9, 30, 30},
{"april", 4, 30, 30},
{"august", 8, 31, 31},
{"october", 10, 31, 31},
{"december", 12, 31, 31},
{"july", 7, 31, 31},
{""}, {""}, {""},
{"february", 2, 28, 29}
};

if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
{
register int key = hash (str, len);

if (key <= MAX_HASH_VALUE && key >= 0)
{
register const char *s = wordlist[key].name;

if (*str == *s && !strcmp (str + 1, s + 1))
return &wordlist[key];
}
}
return 0;
}
[/code]

Основная радость в мега-быстром вычислении хеш-функции и ровно одном сравнении строк в “худшем” случае, когда ключ таки найден. Разумеется, есть всякие опции для контроля над выходным файлом: задание языка (можно генерировать функции, можно C++ класс); задание имен и видимости функций; поддержка ключей с нулевыми байтами внутри (!); контроль за размером таблицы (обмен размера таблицы на время поиска); итп. Применимо, понятно, для случаев, когда набор ключей фиксирован и известен заранее – для абсолютно случайных данных идеальный хеш не построить. Для всяческих текстовых парсеров, где больше десятка ключевых слов, самое то.

  • http://thinkgeek.org.ua Yuriy Volkov

    тул хороший. его в gcc используют для распознавания ключевых слов языка. Да и вообще в text processing его много используют, так что это совсем не “no one use” ;-)

  • shodan

    Well obviously “no one” is an exaggeration.

  • http://aruslan.livejournal.com/ aruslan

    А если у тебя очень много строчек – тогда идеален http://cmph.sourceforge.net/
    Одного поля ягодки, впрочем.

  • http://kss.livejournal.com/ Joes

    А оно с уникодом дружит? Я сходу не нашел.

  • shodan

    Я думаю (лично не проверял) что оно дружит тупо с бинарными строчками, и соотв-но все равно какая внутри кодировка.

  • cppg

    Сравнение происходит не тогда, когда ключ найден, а тогда, когда хеш успешно сымитирован.

    Мне не понравился сабж из-за таблицы квадратичного размера. Поэтому написалась своя тулза, дающая такую же почти функцию, но с таблицей линейного размера. Цена – довольно долгий перебор, и следовательно поддержка не слишком больших наборов строк (максимум – десятки строк).

    Однако, gperf тоже лажает на больших наборах строк – был набор в 700 строк, на котором gperf ничего не смог сгенерить.

  • Pingback: highly professional scums » Blog Archive » Best tools noone uses: autoexp.dat()

  • http://-winnie.livejournal.com _winnie

    А как сунуть туда бинарные строки? Никак не могу понять, как сунуть ему в stdin нулевые байты и переносы строк \n

  • http://www.leningrad.spb.ru/ shodan

    дык возьми сорсы да посмотри, как :)

  • http://-winnie.livejournal.com _winnie

    Разобрался, кавычки надо поставить, и дальше можно писать “\n” как ключи.