日: 2021年7月24日

[Python] 287 引数ありのC言語モジュール ハッシュ関数 FNV

Pythonでもハッシュ関数FNVを使えるようにするためC言語モジュール化しました。

モジュールからの戻り値は整数の範囲でしか使えず、32ビットのunsigned intには対応できましたが、64ビットではうまくいきませんでした。

初めはPythonからポインタをどうやって渡すのか見当もつかなくて、戻り値の受け取り方もかなり試行錯誤しました。

これでC言語とPythonで同一文字列から同じハッシュ値を作成できるので色々使い道がありそうです。

2021/7/25追記：コードを改良して以下の記事にアップしています。

[Python] 290 引数ありのC言語モジュール ハッシュ関数 FNV 64bit
#define PY_SSIZE_T_CLEAN
#include <Python.h>

extern uint32_t fnv_1_hash_32(const char*);

static PyObject* fnv_32(PyObject* self, PyObject* args)
{
    const char* s;
    unsigned int hash=2166136261U;

    if (!PyArg_ParseTuple(args, "s", &s)){
        return NULL;
    }
    else{
        while (*s) {
        hash*=16777619U;
        hash^=*(s++);
        }

        return Py_BuildValue("i", hash);
    }
}

static PyMethodDef fnvmethods[] = {
    {"fnv_1_hash_32", fnv_32, METH_VARARGS},
    {NULL,NULL,0}
};

static struct PyModuleDef fnv = {
    PyModuleDef_HEAD_INIT,
    "fnv",
    "Python3 C API Module(Sample 1)",
    -1,
    fnvmethods
};

PyMODINIT_FUNC PyInit_fnv(void)
{
    return PyModule_Create(&fnv);
}
from c_module import fnv

name = 'シャフリヤール'

hash = fnv.fnv_1_hash_32(name)

# int から unsigned int 32bitへ変換
hash_unsigned32 = hash & 0xffffffff

print(hash_unsigned32)
--------------------------------------------------

出力
--------------------------------------------------
3687658616
#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;
}
from distutils.core import setup, Extension

setup(name='fnv',
    version='1.0',
    ext_modules=[Extension('fnv', sources = ['fnv.c','fnv_1.c'])]
)
＜セットアップコマンド＞

・自作ライブラリに配置するsoファイルを作成するコマンド "from c_module import fnv"
python setup.py build_ext -i

・既存のライブラリにインストールするコマンド "import fnv"
python setup.py install

[Python] 286 C言語実行ファイルの併用 その4 文字列のハッシュ化

これまでC言語を学習してきて、この言語は文字列の取り扱いが不得手というのがよく分かりました。そのような仕様でもstrcmp関数は1文字づつの比較しかできないながら相当速くなっていると思います。

さらなる高速化を検討した結果、文字列を数字に変換して加減計算等できるようにすれば処理が速くなるのではと考え、ハッシュ関数によるハッシュ化を試してみました。

データベースに馬名のハッシュ値を格納し検索に用いたところ、24000件の処理を80秒から55秒に短縮しました。

sscanf関数が扱いづらくatoi関数の必要性にもなかなか気がつかなかったため、かなり難航しました。

今回は比較する文字列の片方を前もってハッシュ化しましたが、両方処理していたらさらに速くなるはずです。

＜修正箇所＞
uint32_t horse_hash_int;

while(fgets(buf,2000,fp ) != NULL ) {
    if (i != 0){
        ret = sscanf(buf, " %[^,],%[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %s",horseID,horse_hash,horse_name,horse_name0,status,gender,hair,birthday,trainer,owner,info,breeder,area,price,prize_money,result,wining_race,relatives) ;
	
        horse_hash_int = atoi(horse_hash);
		
        if(horse_hash_int - 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;
        }
    }
    i ++ ;
}