У меня есть требование (очень) быстро обрабатывать строки ограниченного диапазона, подсчитывая их значения. Входной файл имеет вид:
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, дубликаты столбцов u и столбцы 5 повторяются дубликаты <space> (есть и другие дубликаты, но одного достаточно, чтобы предотвратить одностолбцовую хеш-ключ).
Однако, используя первый и четвертый столбцы, я получаю значения Ju, Fr, Mc, Ai, M<space>, Je, Jy, Au, St, Oo, Ne и De, которые являются уникальными. В этом файле не будет недопустимых значений, поэтому мне не нужно беспокоиться о некорректных кодах для входных данных.
Просмотрев шестнадцатеричные коды для символов, я обнаружил, что могу получить низкие уникальные значения только с помощью ANDing со стратегическими значениями:
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.
