日: 2021年7月22日

[C言語] 06 ハッシュ関数 FNVの外部関数化

FNVをPythonでも使えるようにするため、まずは外部関数化しました。

64バイトハッシュ値のフォーマット指定子は%luです。

#include <stdio.h>
#include <stdint.h>

uint32_t fnv_1_hash_32(char *s)
{
    unsigned int hash=2166136261U;

    while (*s) {
        hash*=16777619U;
        hash^=*(s++);
    }
    return hash;
}

uint64_t fnv_1_hash_64(char *s)
{
    long unsigned int hash=14695981039346656037U;

    while (*s) {
        hash*=1099511628211LLU;
        hash^=*(s++);
    }
    return hash;
}
#include <stdio.h>
#include <stdint.h>
#include "fnv_1.c"

int main(void)
{
    char *s = "シャフリヤール";

    printf("%u\n",fnv_1_hash_32(s));
    printf("%lu\n",fnv_1_hash_64(s));
}
--------------------------------------------------

出力
--------------------------------------------------
3687658616
7203286604922561048

[C言語] 05 簡易なハッシュ関数 FNV

[Python] 283の記事あたりまで取り組んでいたデータベース検索の高速化ですが、文字列比較ではなくハッシュ値比較でも試してみました。

ハッシュ関数によるハッシュ値算出の時間が余計に掛かっているものの、これまでの最速記録80秒に対して84秒となかなかの健闘でした。正確性も問題ありません。

その他では機械語変換手前のアセンブリ言語コードをチェックしたりもしましたが初級者にいじれるはずもなく、また最近の文字列比較機能(strcmpなど)は優秀のようで小手先の自作関数では歯が立ちませんでした。

ハッシュ関数についてはスキルアップのための余興みたいなもので、ここらで高速化検討は打ち切りにするつもりです。

#include <stdio.h>
#include <stdint.h>

uint32_t fnv_1_hash_32(char *s)
{
    unsigned int hash=2166136261UL;

    while (*s) {
        hash*=16777619UL;
        hash^=*(s++);
    }
    return hash;
}
＜該当箇所のみ＞
#include "fnv_1.c"

if (i != 0){
    if (fnv_1_hash_32(horse_name) - fnv_1_hash_32(horse_name_in) == 0){
        fp3 = fopen(fname3, "a");
        fprintf(fp3,"%s,%9s\n",horse_name_in,horseID);
        fclose(fp3);
        b ++;
        break;
    }
}