Entry

プログラミング・メモ - ハッシュ関数性能評価選手権(続き)

2009年03月13日

忘れた頃にやってくる,ハッシュ関数性能評価選手権。前回からかなり時間が経っちゃったんですけれど,少しだけ評価したので,結果をメモっておきます。

ただ,全部を評価するのはちと辛かったので,ここでは LibXML2 と SGI STL のハッシュ関数を評価してみました。あ,ついでにあたしがでっち上げたハッシュ関数も付けてみた。評価に使ったシンボルリスト代わりの辞書は,クラック辞書の ftp://ftp.openwall.com/pub/wordlists/all.gz です(コメント部分は削除)。やましいことには使わないように。

aian@TWEAKBOX ~/project/hash_check
$ ./a wordlist.txt
aian's hash func        : 18593 of 3917116 symbols conflicted. ( 0.47466 % )
LibXML2 hash func       : 5806 of 3917116 symbols conflicted. ( 0.148221 % )
SGI STL hash func       : 644868 of 3917116 symbols conflicted. ( 16.4628 % )

実行してみたところ,LibXML2 のハッシュ関数が,もっともいい成績でした(衝突(conflict)が少ないほどいい)。あたしが作ったでっち上げハッシュ関数は第2位。0.4% の衝突率なので,1000語に4語の割合か……結構高い。SGI STL の関数は,ハッシュ関数になってねいな,こりゃ。

検証に使ったコードは以下の通りです。ファイルを2つに分けたので,順番に紹介します。まず,ヘッダファイルの,hash_check.h です。

#define HASH_CHECK_H__INCLUDED

#include <map>
#include <stdexcept>
#include <string>

class HashFunc {
protected:
    HashFunc() {
    }
    virtual ~HashFunc() {
    }
private:
    HashFunc(const HashFunc& other);
    HashFunc& operator=(const HashFunc& rhs);
public:
    virtual unsigned long operator()(const char* str) = 0;
    const std::string& getName() const {
        return name_;
    }
protected:
    std::string name_;
};

class HashCheck {
public:
    HashCheck(const std::string& filename = "");
    virtual ~HashCheck();
private:
    HashCheck(const HashCheck& other);
    HashCheck& operator=(const HashCheck& rhs);
public:
    void setFilename(const std::string& filename);
    int check(HashFunc& fn) throw (std::runtime_error, std::logic_error);
    void clear();
private:
    void chomp(char* str);
private:
    std::string filename_;
    std::map<long, std::string> hashmap_;
};

#endif // HASH_CHECK_H__INCLUDED

続いて,本体の実装ファイル hash_check.cpp。ちと,ファイルの分け方がよろしくなかったんですが。

#include <cstdio>
#include <cstring>
#include <iostream>

#include "hash_check.h"

HashCheck::HashCheck(const std::string& filename) : filename_(filename) {
}

HashCheck::~HashCheck() {
}

void
HashCheck::setFilename(const std::string& filename) {
    filename_ = filename;
}

int
HashCheck::check(HashFunc& fn) throw (std::runtime_error, std::logic_error) {
    typedef std::map<long, std::string>::const_iterator Itr;
    const ::size_t bufsize = 512;
    char buf[bufsize] = {0};

    if (filename_.size() == 0) {
        throw std::logic_error("filename is not set.");
    }
    FILE* fp = ::fopen(filename_.c_str(), "r");
    if (fp == 0) {
        throw std::runtime_error("file open error.");
    }

    std::cout << fn.getName().c_str() << "\t: ";
    // calc hashes and add them to a map object
    int conflict = 0;
    int lineNum = 0;
    while (!feof(fp)) {
        if (fgets(buf, bufsize, fp) != 0) {
            ::size_t len = ::strlen(buf);
            if (buf[len - 1] == '\n') {
                buf[len - 1] = '\0';
            }
            unsigned long hash = fn(buf);
            Itr itr = hashmap_.find(hash);
            if (itr == hashmap_.end()) {
                hashmap_.insert(std::pair<long, std::string>(hash, buf));
            } else {
//                std::string cstr =  (*itr).second;
//                ::printf("C: %08x (%s) (%s)\n", hash, buf, cstr.c_str());
                conflict++;
            }
            lineNum++;
        }
    }
    ::fclose(fp);

    double rate = static_cast<double>(conflict) / static_cast<double>(lineNum);
    std::cout << conflict << " of " << lineNum << " symbols conflicted."
        << " ( " << (rate * 100)  << " % )" << std::endl;

    return conflict;
}

void
HashCheck::clear() {
    hashmap_.clear();
}

////////////////////////////////////////////////////////////////////////////////
/** aian's hash */
class MyHashFunc : public HashFunc {
public:
    MyHashFunc() {
        name_ = "aian\'s hash func";
    }
    virtual ~MyHashFunc() {
    }
private:
    MyHashFunc(const MyHashFunc& other);
    MyHashFunc& operator=(const MyHashFunc& other);
public:
    unsigned long operator()(const char* str) {
        unsigned long ret = 0;
        unsigned long key = 0;
        for (const char* ptr = str; *ptr != '\0'; ptr++) {
            key = static_cast<unsigned long>(*ptr);
            ret += (key) ^ (ret << (key % 16 + 1)) ^ (ret >> (key % 16 + 1));
        }
        return ret;
    }
};

/** LibXML2 hash */
class LibXmlHashFunc : public HashFunc {
public:
    LibXmlHashFunc() {
        name_ = "LibXML2 hash func";
    }
    virtual ~LibXmlHashFunc() {
    }
private:
    LibXmlHashFunc(const LibXmlHashFunc& other);
    LibXmlHashFunc& operator=(const LibXmlHashFunc& rhs);
public:
    // modified to a large extent ...
    // see ftp://xmlsoft.org/libxml2 (libxml2-2.6.27.tar.gz/hash.c)
    unsigned long operator()(const char* str) {
        unsigned long value = 0L;
        char ch;
        if (str != 0) {
            value += 30 * (*str);
            while ((ch = *str++) != 0) {
                value ^= ((value << 5) + (value >> 3) + (unsigned long)ch);
            }
        }
        return value;
    }
};

/** STL hash */
class StlHashFunc : public HashFunc {
public:
    StlHashFunc() {
        name_ = "SGI STL hash func";
    }
    virtual ~StlHashFunc() {
    }
private:
    StlHashFunc(const StlHashFunc& other);
    StlHashFunc& operator=(const StlHashFunc& rhs);
public:
    // see http://www.sgi.com/tech/stl (stdlib_19991014.zip/stl_hash_fun.h)
    unsigned long operator()(const char* str) {
        unsigned long h = 0;
        for ( ; *str; ++str) {
            h = 5 * h + *str;
        }
        return h;
    }
};


////////////////////////////////////////////////////////////////////////////////
int
main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cerr << "filename is not given." << std::endl;
        return -1;
    }

    HashCheck hc(argv[1]);
    try {
        // aian's hash func
        MyHashFunc mhf;
        hc.check(mhf);
        hc.clear();
        // libxml2 hash func
        LibXmlHashFunc lhf;
        hc.check(lhf);
        hc.clear();
        // STL hash func
        StlHashFunc shf;
        hc.check(shf);
        hc.clear();
    } catch (std::logic_error& e) {
        std::cerr << e.what() << std::endl;
    } catch (std::runtime_error& e) {
        std::cerr << e.what() << std::endl;
    } catch (...) {
        std::cerr << "unknown error." << std::endl;
    }

    return 0;
}

ファンクタクラス(HashFunc)を作ったので,ソース中ほどでやってるように,operator() を適当にオーバーライドすれば,任意のアルゴリズムを使うことができます。で,main() 関数内でやってるように呼び出す。また,LibXML2 のアルゴリズムは,本当は3つの文字列から1つのハッシュを作っているんですけれど,ここでは,引数の条件を同じにするために,1つの文字列だけについてハッシュを取りました。

仕組みは単純で,STL の std::map にハッシュをキーにして追加する時に衝突するかを見ています。あたしは Cygwin gcc 3.4.4 + Cygwin で動作確認しました。std::map はそれなりに早いんですけれど,400万語近い辞書を扱うとなる,実行時間もそれなりにかかります。やれやれ。

他の関数も試そうと思ったんですけれど,あまり時間をかけたくなかったので,1時間くらいでできる範囲で作っちゃいました。前回紹介した他の関数は,もう少し内部のソースを追いかけないといけないので,今回は断念。気が向いたら,またオイオイで。

衝動的にハッシュ関数の衝突頻度を測るツールを作ったわけですけれど,これ,案外便利に使えるかも。もちっと使いやすくしてみようかな。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN