限られた範囲の文字列を（非常に）迅速に処理し、それらの値を集計する必要があります。入力ファイルの形式は次のとおりです。
January 7
March 22
September 87
March 36
などなど。線幅が同じなので、適度に速い行を簡単に読み取ることができ、fread機能する完璧なハッシュ関数を開発しましたが、それをさらに速くする方法について誰かがアドバイスをくれるかどうかを確認したいと思いました。それぞれの提案のプロファイルを作成して、それがどのように行われるかを確認します。
ハッシュ関数は月の名前に基づいており、バケットへの値の迅速な割り当てを可能にします。ここで私と一緒に耐えなさい。私は最初に、完全なハッシュの最小文字数を見つけました。
January
February
March
April
May
June
July
August
September
October
November
December
入力行全体があるため、月はすべて9文字であることに注意してください。
残念ながら、1か月を一意としてマークする単一の列はありません。列1の重複J、列2の重複a、列3の重複r、列4の重複u、列5以降の重複<space>（他にも重複がありますが、単一列のハッシュキーを防ぐには1つで十分です）。
ただし、1列目と4列目を使用すると、一意の値、、、、、、、、、、、、、、Juが得られます。このファイルには無効な値が含まれないため、入力データのバケットが正しくないことを心配する必要はありません。FrMcAiM<space>JeJyAuStOoNeDe
文字の16進コードを表示することにより、戦略的な値と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演算がわずかに変わる可能性があります。提供されたアドバイスがEBCDICに問題なく変換されると確信しているので、ASCIIの面でのみ支援に満足します。