У меня есть требование (очень) быстро обрабатывать строки ограниченного диапазона, подсчитывая их значения. Входной файл имеет форму:

January    7
March     22
September 87
March     36

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

Функция хеширования основана на названии месяца, чтобы обеспечить быстрое распределение значения в сегменте. Потерпи меня здесь. Сначала я выяснил минимальное количество символов для идеального хэша:

January
February
March
April
May
June
July
August
September
October
November
December

Имейте в виду, что месяцывсе девять символов из-за того, что у меня есть вся строка ввода.

К сожалению, нетне замужем колонка для обозначения месяца уникальна. Колонка 1 дубликатовJстолбец 2 дубликатыaстолбец 3 дубликатыrстолбец 4 дубликатыu и столбцы 5 года повторяются<space> (есть другие дубликаты, но одного достаточно, чтобы предотвратить хеш-ключ с одним столбцом).

Однако, используя первый и четвертый столбец, я получаю значенияJu, Fr, Mc, Ai, M<space>, Je, Jy, Au, St, Oo, Ne а такжеDe, которые являются уникальными. В этом файле не будет недопустимых значений, поэтому мне не нужно беспокоиться о неправильных сегментах для входных данных.

Просматривая шестнадцатеричные коды для символов, я обнаружил, что могу получить низкие уникальные значения, просто используя AND со стратегическими значениями:

FirstChar  Hex  Binary     &0x0f
---------  ---  ---------  -----
   A       x41  0100 0001      1
   D       x44  0100 0100      4
   F       x46  0100 0110      6
   J       x4a  0100 1010     10
   M       x4d  0100 1101     13
   N       x4e  0100 1110     14
   O       x4f  0100 1111     15
   S       x53  0101 0011      3

SecondChar  Hex  Binary     &0x1f
----------  ---  ---------  -----
 <space>    x20  0010 0000      0
    c       x63  0110 0011      3
    e       x65  0110 0101      5
    i       x69  0110 1001      9
    o       x6f  0110 1111     15
    r       x72  0111 0010     18
    t       x74  0111 0100     20
    u       x75  0111 0101     21
    y       x79  0111 1001     25

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

#define __ -1
static unsigned int hash (const char *str) {
    static unsigned char bucket[] = {
        //   A       S   D       F               J           M   N   O
        __, __, __, __, __, __, __, __, __, __, __, __, __,  4, __, __, // space
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __,  2, __, __, // c
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, 11, __, __, __, __, __,  5, __, __, __, 10, __, // e
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __,  3, __, __, __, __, __, __, __, __, __, __, __, __, __, __, // i
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __,  9, // o
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __,  1, __, __, __, __, __, __, __, __, __, // r
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __,  8, __, __, __, __, __, __, __, __, __, __, __, __, // t
        __,  7, __, __, __, __, __, __, __, __,  0, __, __, __, __, __, // u
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
        __, __, __, __, __, __, __, __, __, __,  6, __, __, __, __, __  // y
    };
    return bucket[((unsigned int)(str[3]&0x1f)<<4)|(str[0]&0xf)];
}

Тестирование с помощью кода:

#include <stdio.h>
#include <string.h>

// Hash function here.

static char *months[] = {
    "January  ", "February ", "March    ", "April    ", "May      ", "June     ",
    "July     ", "August   ", "September", "October  ", "November ", "December "
};

int main (void) {
    int i;
    for (i = 0; i < sizeof(months)/sizeof(*months); i++)
        printf ("%-10s -> %2d\n", months[i], hash(months[i]));
    return 0;
}

показывает, что это функционально правильно:

January    ->  0
February   ->  1
March      ->  2
April      ->  3
May        ->  4
June       ->  5
July       ->  6
August     ->  7
September  ->  8
October    ->  9
November   -> 10
December   -> 11

но я хочу знать, можно ли это сделать быстрее.

Есть предложения? Я открыт для любых простых оптимизаций или даже полного переписывания, если с моей функцией хеширования есть что-то плохое.

Я не думаю, что это так важно, но окончательная версия будет использовать EBCDIC. Теория все еще остается в силе, но операция И может немного измениться, поскольку символы имеют разные кодовые точки. Я буду рад любой помощи только на фронте ASCII, так как я уверен, что любой совет, который будет предложен, будет хорошо переведен в EBCDIC.