У меня есть требование (очень) быстро обрабатывать строки ограниченного диапазона, подсчитывая их значения. Входной файл имеет форму:
January 7
March 22
September 87
March 36
и т. Д. Поскольку ширина строк одинакова, я могу просто читать строку с fread достаточно быстро, и я разработал идеальную функцию хеширования, которая работает, но я хотел посмотреть, может ли кто-нибудь дать какой-нибудь совет о том, как сделать это даже Быстрее. Я опишу каждое предложение, чтобы увидеть, как оно идет.
Функция хеширования основана на названии месяца, чтобы обеспечить быстрое распределение значения в сегменте. Потерпи меня здесь. Сначала я выяснил минимальное количество символов для идеального хэша:
January
February
March
April
May
June
July
August
September
October
November
December
Имейте в виду, что месяцы все девять символов, потому что у меня есть вся строка ввода.
К сожалению, нет столбца single для пометки уникального месяца. Дубликаты столбца 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.