pax*_*blo 19 c optimization perfect-hash
我要求(非常)快速处理有限范围的字符串,统计它们的值.输入文件的格式如下:
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.理论仍然有效,但由于角色具有不同的代码点,因此AND操作可能会略有变化.我会很乐意在ASCII前面提供任何帮助,因为我相信无论提供哪些建议都可以转换成EBCDIC.
我同意其他人的意见,认为没有太大的改进空间.我可以建议的是一个较小的查找表,它使用相同数量的操作,这可能使它在CPU缓存中保持更长时间.此外,它不依赖于末尾的空间填充字符,它适用于大写和小写字符的任何混合.我发现,为了对需求的可能变化添加一些合理的稳健性通常会在未来得到回报,特别是当实施被优化到不再那么容易变化的程度时.
#define __ -1
static unsigned int hash (const char *str)
{
static unsigned char tab[] = {
__, __, 1, 11, __, __, __, __, 7, __, __, __, __, 6, 0, 5,
8, __, 2, 3, 9, __, 10, __, __, 4, __, __, __, __, __, __
};
return tab[ ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f ) ];
}
这与您原来的想法类似,但占用空间较小:
Month s[1] s[2] s[1].4 s[2].4-0 sum lookup
----- ------------ ------------ ------ -------- --- ------
Jan 61:0110 0001 6e:0110 1110 0 14 14 0
Feb 65:0110 0101 62:0110 0010 0 2 2 1
Mar 61:0110 0001 72:0111 0010 0 18 18 2
Apr 70:0111 0000 72:0111 0010 1 18 19 3
May 61:0110 0001 79:0111 1001 0 25 25 4
Jun 75:0111 0101 6e:0110 1110 1 14 15 5
Jul 75:0111 0101 6c:0110 1100 1 12 13 6
Aug 75:0111 0101 67:0110 0111 1 7 8 7
Sep 65:0110 0101 70:0111 0000 0 16 16 8
Oct 63:0110 0011 74:0111 0100 0 20 20 9
Nov 6f:0110 1111 76:0111 0110 0 22 22 10
Dec 65:0110 0101 63:0110 0111 0 3 3 11
^ ^ ^^^^
bits: 4 4 3210
这是我能为EBCDIC-US找到的最小序列:
它在存储桶中有24个元素,仅使用2个操作来计算索引:
static unsigned int hash (const char *str)
{
static unsigned char tab[] = {
11, 4,__, 7,__,__, 9, 1,
__,__,__,__,__,__,__,__,
3, 5, 2,10, 8,__, 0, 6
};
return tab[0x17 & (str[ 1 ] + str[ 2 ])];
}
第二好,有xor的25项:
static unsigned int hash(const char *str)
{
static unsigned char tab[] = {
9,__,__, 7,__,__,11, 1,
__, 4,__,__,__,__, 3,__,
__, 5, 8,10, 0,__,__, 6, 2
};
return tab[0x1f & (str[ 1 ] ^ str[ 2 ])];
}
(实际上,tab []在这里应该是32个条目,因为0x1f可以为不正确的输入生成溢出).
来自Pax的更新:对于它的价值,第一个选项适用于EBCDIC代码页500:
## Month str[1] str[2] Lookup
-- --------- ------ ------ ------
0 January a (81) n (95) 0
1 February e (85) b (82) 1
2 March a (81) r (99) 2
3 April p (97) r (99) 3
4 May a (81) y (a8) 4
5 June u (a4) n (95) 5
6 July u (a4) l (93) 6
7 August u (a4) g (87) 7
8 September e (85) p (97) 8
9 October c (83) t (a3) 9
10 November o (96) v (a5) 10
11 December e (85) c (83) 11