我需要(非常)快速地处理有限范围内的字符串,计算它们的值。输入文件的格式为:
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
, 这是独一无二的。此文件中不会有无效值,因此我不必担心输入数据的桶不正确。
通过查看字符的十六进制代码,我发现我可以通过与战略值进行 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。该理论仍然成立,但由于字符具有不同的代码点,因此 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
关于c - 有没有办法使这个哈希查找更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3421881/