日: 2021年7月25日

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

ハッシュ関数FNVの32bitで数件衝突が発生したため、64bitでも生成できるようにしました。

PythonのドキュメントにPy_BuildValueの引数について解説があり、unsigned long long intのフォーマットがKであることが分かりました。

unsigned intのフォーマットはiではなく大文字のIなので、32bitの方も修正しました。これでPython側での変換が不要になります。

#define PY_SSIZE_T_CLEAN
#include <Python.h>

extern uint32_t fnv_1_hash_32(const char*);
extern uint64_t fnv_1_hash_64(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 PyObject* fnv_64(PyObject* self, PyObject* args)
{
    const char* s;
    unsigned long long hash=14695981039346656037U;

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

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

static PyMethodDef fnvmethods[] = {
    {"fnv_1_hash_32", fnv_32, METH_VARARGS},
    {"fnv_1_hash_64", fnv_64, 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_list = ['シャフリヤール']

for name in name_list:
    hash = fnv.fnv_1_hash_64(name)
    print(hash)
--------------------------------------------------

出力
--------------------------------------------------
7203286604922561048
#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)
{
    unsigned long long hash=14695981039346656037U;

    while (*s) {
        hash*=1099511628211LLU;
        hash^=*(s++);
    }
    return hash;
}
from distutils.core import setup, Extension

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

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

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

[Python] 289 ハッシュ関数 FNV-1によるハッシュ値のばらつき

FNV-1により生成されたハッシュ値のばらつきをヒストグラムで確認しました。ハッシュ値は自製のC言語モジュールで生成しました。

上のグラフが1986年以降に生まれた競走馬26.2万頭の馬名ハッシュ値、下のグラフが馬名にシルクが含まれる1000頭のハッシュ値をヒストグラムにしたものです。

満遍なくハッシュ値が生成されており、冠名による偏りもほとんど見られませんでした。

ハッシュ値の重複については調査中です。重複があれば他のハッシュ関数を検討します。

import matplotlib.pyplot as plt
import datetime
import pandas as pd

df = pd.read_csv("name_hash.csv",encoding='UTF-8')
df2 = df[df['馬名'].str.contains('シルク',na=False)]
list = df2['horse_hash'].tolist()

datetime_now = datetime.datetime.now()
datetime_now_str = datetime_now.strftime('%y%m%d%H%M')

plt.hist(list, bins=20,color=['#7fffd4'])
plt.savefig(f"{datetime_now_str}_hist_silk.png")

[Python] 288 CSVファイルから改行コードを削除

一定の頻度で必要になりそうなので書いておきます。

import csv

print("開始年度を入力してください")
start_year = input()

print("終了年度を入力してください")
end_year = input()

for year in range(int(start_year),int(end_year)+1):
    file = f'{year}.csv'
    file_new= f'{year}_new.csv'

    with open (file, mode="r", encoding="UTF-8") as f1:
        with open(file_new, mode="w", encoding="UTF-8") as f2:
            writer = csv.writer(f2)
            for row in csv.reader(f1):
                rows = []
                for i in range(0,len(row)):
                    rows.append(row[i].replace('\n',''))
                writer.writerow(rows)