19

我需要（非常）快速处理有限范围的字符串，计算它们的值。输入文件的格式为：

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。

4

8 回答 8

9

我同意其他人的观点，即没有太大的改进空间。我只能建议一个较小的查找表，它可以与相同数量的操作一起使用，这可能使其在 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
于 2010-08-06T08:47:53.573 回答
8

这是我能为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 ])];
}

次优，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
于 2010-08-06T11:00:14.677 回答
4

这是针对 EBDIC (CCSID 500) 测试的，表格 32 字节（比你的小，与 x4u 的大小相同）：

#define __ -1
static unsigned int hash(const char *str)
{
    static unsigned char bucket[] = {
        __, __, __, __, __, __,  1,  8,
        __,  7, __, __, __,  3, __, __,
        11,  6, __, __,  4, __,  2, __,
        __,  0, __,  5,  9, __, __, 10,
    }
    return bucket[(unsigned int)(str[0]|str[3]<<1)&0x1f];
}
于 2010-08-06T10:05:46.017 回答
3

我将从您的更大流程的详细配置文件开始，以确保您不会进行过早的优化。

从表面上看，这看起来相当快，但如果内存真的很便宜，最好只使用一个更稀疏的数组并让你的缓存来做一些工作。例如（并在这里考虑一下），如果您只是将short前两个字节中的find 添加到short接下来的两个字节中会怎样。这包括第一个和第四个字符，所以猜测它应该产生你的 12 个不同的值，并且它不涉及可能无法很好地优化的位字段提取。然后，使匹配的bucket[]数组有 64K 个条目，其中只有 12 个被命中。如果结果正确，那么这 12 个条目最终会占用您的一些 D 缓存，并且您已经用少量算术运算换取了缓存更大数组的索引。

但是，在任何试图使算术更快的问题之前和之后都要进行分析，并且不要费心优化它实际上不会节省时间的地方。（我知道 Pax 知道这一点，但它是任何优化讨论附带的强制性警告。）

于 2010-08-06T08:05:48.460 回答
2

好的，就像 SO 上的每个人一样，我全力以赴。 ;*) 正如我在上面的评论中所写，你的目标架构的低端缓存线大小为 256 字节，所以你最终可能会得到表查找中的一些缓存垃圾（您的表超过 256 个字节）。尝试使用一些廉价的技巧来折叠桌子实际上可能会获得一些性能。

我一直在玩弄你的数据。您还可以选择第 2 列和第 3 列。不过，还没有找到一种方法来将其降低到 8 位以下。

...和往常一样，配置文件，确保这是施加努力的最佳点，然后再次配置文件，确保它更快。

...而且您一次阅读不止一行，对吗？固定的记录大小这样就很好，您不必搜索分隔符（换行符），并且一次可以读取其中的一大块。

您可以使用以下方法减小数组大小：

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

将其从 16×26 更改为 16×13。

编辑

如果按照其他帖子的建议，您的字符串对齐，以便您可以将它们用作短裤，您可以将第一个和第二个短裤相加，将两个字节异或在一起，您将拥有一个唯一的 8 位密钥（嗯，七，实际上）。可能也值得你花时间。虽然这是 ASCII，所以在 EBCDIC 中可能不起作用。在 ASCII 中，键结果是：

6e Jan
7f Feb
7b Mar
6a Apr
47 May
62 Jun
58 Jul
42 Aug
1a Sep
11 Oct
10 Nov
6d Dec
于 2010-08-06T08:38:15.417 回答
1

你真的需要哈希和月份索引之间的映射来进行统计吗？如果不是返回返回哈希的月份并将其用于统计，则可以消除查找。在x4u 的回答中，哈希函数的最后一行可能看起来像

return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )

而且您仍然可以求和，仅在最后而不是在循环内对结果进行排序。

于 2010-08-06T12:22:38.317 回答
1

在 ASCII 中，如果你取，month[0] ^ month[2] ^ month[3]那么你会得到一个最大值为 95（7 月）的唯一哈希，这应该可以让你减少你的表大小相当多（最小值为 20（5 月），所以减法使它再次变小）。

在 EBCDIC 中可能不是这样，但可能是类似的。

于 2010-08-06T09:10:49.953 回答
1

对我来说已经足够好看了。问题是哈希函数本身是否足以成为一个瓶颈，以证明正在进行的消除一两个简单二进制操作的努力是合理的。鉴于似乎涉及文件访问，我对此表示怀疑，当然不知道有关整体处理的任何细节。

编辑：

也许您可以查看添加时是否找到任何导致唯一低位（4、5 或 6）的字符：

(str[1] + str[2]) & 0x1f

如果加法不行，可能是其他操作之一& | ^。如果这没有帮助，也许使用三个字符。

于 2010-08-06T07:59:54.090 回答