ローリングハッシュ備忘録

ローリングハッシュアルゴリズムのメモ

結論

Pythonのindex関数、inはかなり早い
C言語のstrstrでの検索が最強
付け焼刃でよくわからずアルゴリズムを実装したもので評価したので、間違ったことをしてるかもしれないが、
ローリングハッシュ別に速くはなく、価値がわからなかった。O(N+M)らしいのだけども
ネットで参考にしたハッシュ関数が悪いのかなあ。。

文字列の部分一致検索に使える模様
以下はSource(S)の何番目にマッチしたかを返す関数

Pythonの場合

C++の実装からPythonらしい書き方で実装してみた

def find(S:str, P:str, B1:int = 0x5f5e107, B2:int = 0x3b9aca07):
    """ find string match by rolling_hash algorithm
        [Argument]
            S : Search Target Source String
            P : Search Word String
            B1 : Hashing Base Number Primary
            B2 : Hashing Base Number Secondary
        [Return]
            int: match position index(zero start)
        [Return of Error]
            None
    """
    pow1 = 1
    pow2 = 1
    sh1 = sh2 = ph1 = ph2 = plen = 0
    eS = S.encode()
    eP = P.encode()

    if(not S or not P):
        return None

    for plen, (p, s) in enumerate(zip(P.encode(), eS), 1):
        if not s:
            return None

        # make `Bn ^ plen`
        pow1 *= B1
        pow2 *= B2

        # first hash `S and P`
        ph1 = ph1 * B1 + p
        ph2 = ph2 * B2 + p

        sh1 = sh1 * B1 + s
        sh2 = sh2 * B2 + s
    

    # rehash of slide `S`
    for i, s in enumerate(eS):
        if sh1 == ph1 and sh2 == ph2 and eP == eS[i: i+plen]: # more safety check for collision hash value
            return i
        
        sh1 = sh1 * B1 + eS[i+plen] - s * pow1
        sh2 = sh2 * B2 + eS[i+plen] - s * pow2
    
    return None



from timeit import timeit
def runtimeit(funcstr):
    rtime = int(timeit(funcstr, globals=globals(), number=1000) * 1000000)
    print("{}: {} ns".format(funcstr, rtime))

if __name__ == "__main__":
    # short word
    assert("bcd" in "abcde")
    runtimeit('"bcd" in "abcde"')

    assert("abcde".index("bcd") == 1)
    runtimeit('"abcde".index("bcd")')
    
    assert(find("abcde", "bcd") == 1)
    runtimeit('find("abcde", "bcd")')


    # long word
    assert("bcd" in "x" * 10000 + "abcde")
    runtimeit('"bcd" in "x" * 10000 + "abcde"')

    assert(("x" * 10000 + "abcde").index("bcd") == 10001)
    runtimeit('("x" * 10000 + "abcde").index("bcd")')
    
    assert(find("x" * 10000 + "abcde", "bcd") == 10001)
    runtimeit('find("x" * 10000 + "abcde", "bcd")')

    # make string cost
    runtimeit('"x" * 10000 + "abcde"')

"bcd" in "abcde"                    : 35 ns
"abcde".index("bcd")                : 139 ns
find("abcde", "bcd")                : 2716 ns
"bcd" in "x" * 10000 + "abcde"      : 3093 ns      
("x" * 10000 + "abcde").index("bcd"): 2980 ns
find("x" * 10000 + "abcde", "bcd")  : 4871957 ns
"x" * 10000 + "abcde"               : 588 ns <- 参考 文字列作成コスト

結果

めっちゃ遅かった。実装が無理やり感否めないけど、
encode の処理除外したり、eP == es[i: i+plen]で念押しチェックを外したりしても尚遅かった。
普通に標準関数のindexかinの方がかなり速いということは分かった。
おそらくはSの分割ループのオーバーヘッドが無駄すぎるのだろう。
内部的にPySequence_GetItemが呼ばれ新しくオブジェクトを生成しまくってる分遅いと思われる。

pythonでの実装は向いてないとなんとなくわかったのでC++で実装してみる。
はたしてPythonのindex関数 139nsに勝てるのか！？

C++の場合

#include <string>

/* find string match by rolling_hash algorithm
    [Argument]
        S : Search Target Source String
        P : Search Word String
        matchlength: matched String length
    [Return]
        std::size_t: match position index(zero start)
    [Return of Error]
        nullptr
 */
template <class CharT>
constexpr std::size_t find(const CharT* S, const CharT* P, std::size_t* matchlength) {
    std::size_t pow1 = 1, pow2 = 1;
    std::size_t sh1 = 0, sh2 = 0, ph1 = 0, ph2 = 0, plen = 0;
    const std::size_t B1 = 0x5f5e107, B2 = 0x3b9aca07;
    *matchlength = 0;

    if(!S || !P || !(*S) || !(*P))
        return -1;

    for(const CharT* p = P, *s = S; *p; ++s, ++p, ++plen) {
        if(!*s)
            return -1;

        /* make `Bn ^ plen` */
        pow1 *= B1, pow2 *= B2;

        /* first hash `S and P` */
        ph1 = ph1 * B1 + *p, ph2 = ph2 * B2 + *p;
        sh1 = sh1 * B1 + *s, sh2 = sh2 * B2 + *s;
    }

    /* rehash of slide `S` */
    for(const CharT* s = S; *s; ++s) {
        if(sh1 == ph1 && sh2 == ph2){// && memcmp(s, P, plen) == 0) { // memcmp is more safety check for collision hash value
            *matchlength = plen;
            return s - S;
        }
        sh1 = sh1 * B1 + s[plen] - *s * pow1;
        sh2 = sh2 * B2 + s[plen] - *s * pow2;
    }
    return -1;
}
template <class CharT>
constexpr std::size_t find(const CharT* S, const CharT* P) {
    std::size_t dummy = 0;
    return find(S, P, &dummy);
}
template <class CharT>
std::size_t find(const std::basic_string<CharT>& S, const std::basic_string<CharT>& P, std::size_t* matchlength = nullptr) {
    std::size_t len = 0;
    return find(S.data(), P.data(), matchlength ? matchlength : &len);
}
template <class CharT>
std::size_t find(const CharT* S, const std::basic_string<CharT>& P, std::size_t* matchlength = nullptr) {
    std::size_t len = 0;
    return find(S, P.data(), matchlength ? matchlength : &len);
}
template <class CharT>
std::size_t find(const std::basic_string<CharT>& S, const CharT* P, std::size_t* matchlength = nullptr) {
    std::size_t len = 0;
    return find(S.data(), P, matchlength ? matchlength : &len);
}

#include <iostream>
#include <chrono>
#include <algorithm>
#include <string.h>

using cc = std::chrono::system_clock;
int count = 1000;

void runtimeit(void (*func)(), const char* msg) {
    std::cout << msg;
    auto sa = cc::now();
    for (int i = 0; i < count; ++i)
        func();
    auto ea = std::chrono::duration_cast<std::chrono::nanoseconds>(cc::now() - sa);
    std::cout << ea.count() / ::count << " ns" << std::endl;
}


static char S_long[10006];
static wchar_t S_long_wchar[10006];

inline void blueforcefind() {
    const char* S = "abcde";
    const char* P = "bcd";
    auto slen = strlen(S);
    auto plen = strlen(P);
    for(int i = 0; *S && *P && i + plen < slen; ++S, ++i) {
        if(*S == *P && memcmp(S, P, plen) == 0)
            return;
    }
    if(*S && *P == 0)
        return;
    return;
}

inline void strstrfind() {
	auto x = strstr("abcde", "bcd");
}
inline void std_find() {
    const char* S = "abcde";
    const char* P = "bcd";
    auto endS = S + strlen(S);
    auto endP = P + strlen(P);
    auto x = std::find_first_of(S, endS, P, endP);
}
inline void rollinghash_find() {
	auto x = find("abcde", "bcd");
}

inline void wcsstrfind_wchar() {
	auto x = wcsstr(L"abcde", L"bcd");
}
inline void std_find_wchar() {
    const wchar_t* S = L"abcde";
    const wchar_t* P = L"bcd";
    auto endS = S + wcslen(S);
    auto endP = P + wcslen(P);
    auto x = std::find_first_of(S, endS, P, endP);
}
inline void rollinghash_find_wchar() {
	auto x = find(L"abcde", L"bcd");
}

inline void long_blueforcefind() {
    const char* S = (const char*)S_long;
    const char* P = "bcd";
    auto slen = strlen(S);
    auto plen = strlen(P);
    for(int i = 0; *S && *P && i + plen < slen; ++S, ++i) {
        if(*S == *P && memcmp(S, P, plen) == 0)
            return;
    }
    if(*S && *P == 0)
        return;
    return;
}

inline void long_strstrfind() {
	auto x = strstr((const char*)S_long, "bcd");
}
inline void long_std_find() {
    const char* S = (const char*)S_long;
    const char* P = "bcd";
    auto endS = S + strlen(S);
    auto endP = P + strlen(P);
    auto x = std::find_first_of(S, endS, P, endP);
}
inline void long_rollinghash_find() {
	auto x = find((const char*)S_long, "bcd");
}

inline void long_wcsstrfind_wchar() {
	auto x = wcsstr((const wchar_t*)S_long_wchar, L"bcd");
}
inline void long_std_find_wchar() {
    const wchar_t* S = (const wchar_t*)S_long_wchar;
    const wchar_t* P = L"bcd";
    auto endS = S + wcslen(S);
    auto endP = P + wcslen(P);
    auto x = std::find_first_of(S, endS, P, endP);
}
inline void long_rollinghash_find_wchar() {
	auto x = find((const wchar_t*)S_long_wchar, L"bcd");
}

int main() {
    std::cout << "tring `bcd in abcde`" << std::endl;
    runtimeit(&blueforcefind, "fblueforcefind : ");
    runtimeit(&strstrfind, "find_by_C_strstr : ");
    runtimeit(&std_find, "find_by_stl_find : ");
    runtimeit(&rollinghash_find, "find_by_rollinghash : ");
    runtimeit(&wcsstrfind_wchar, "find_by_C_wcsstr_wchar : ");
    runtimeit(&std_find_wchar, "find_by_stl_find_wchar : ");
    runtimeit(&rollinghash_find_wchar, "find_by_rollinghash_wchar : ");

    memset(S_long, 'x', 10000);
    memset(S_long_wchar, L'x', 10000);
    const char* S = "abcde";
    const wchar_t* Sw = L"abcde";
    for(int i = 10000; i < 10006; ++i) {
        S_long[i] = S[i - 10000];
        S_long_wchar[i] = Sw[i - 10000];
    }

    std::cout << "\ntring `bcd in ((x*10000) + abcde)`" << std::endl;
    runtimeit(&long_blueforcefind, "long_fblueforcefind : ");
    runtimeit(&long_strstrfind, "long_find_by_C_strstr : ");
    runtimeit(&long_std_find, "long_find_by_stl_find : ");
    runtimeit(&long_rollinghash_find, "long_find_by_rollinghash : ");
    runtimeit(&long_wcsstrfind_wchar, "long_find_by_C_wcsstr_wchar : ");
    runtimeit(&long_std_find_wchar, "long_find_by_stl_find_wchar : ");
    runtimeit(&long_rollinghash_find_wchar, "long_find_by_rollinghash_wchar : ");

    return 0;
}

結果(Windows環境 clang++でコンパイル)

最適化なし(-O0)

trying `bcd in abcde`
fblueforcefind            : 12 ns
find_by_C_strstr          : 13 ns
find_by_stl_find          : 37 ns
find_by_rollinghash       : 19 ns       
find_by_C_wcsstr_wchar    : 11 ns    
find_by_stl_find_wchar    : 96 ns    
find_by_rollinghash_wchar : 18 ns 

trying `bcd in ((x*10000) + abcde)`
long_fblueforcefind            : 26144 ns
long_find_by_C_strstr          : 968 ns
long_find_by_stl_find          : 82040 ns
long_find_by_rollinghash       : 23982 ns 
long_find_by_C_wcsstr_wchar    : 840 ns
long_find_by_stl_find_wchar    : 44590 ns
long_find_by_rollinghash_wchar : 12101 ns

最適化オプション(-O2)　→　×計測不能

最適化されまくって参考にならなかった

trying `bcd in abcde`
fblueforcefind            : 0 ns
find_by_C_strstr          : 0 ns
find_by_stl_find          : 0 ns
find_by_rollinghash       : 0 ns
find_by_C_wcsstr_wchar    : 14 ns       
find_by_stl_find_wchar    : 0 ns        
find_by_rollinghash_wchar : 0 ns     

trying `bcd in ((x*10000) + abcde)`   
long_fblueforcefind       : 0 ns
long_find_by_C_strstr     : 0 ns
long_find_by_stl_find     : 5143 ns      
long_find_by_rollinghash  : 0 ns      
long_find_by_C_wcsstr_wchar : 941 ns 
long_find_by_stl_find_wchar : 4321 ns
long_find_by_rollinghash_wchar : 0 ns