server-completion の実装

SKK-ML で server-completion の話題が出ていました。L 辞書はソート済なので対数時間で処理できるはずです。むずむずしたので実験してみました。

補完動作の確認

まずは補完動作がきちんとできることを確認するために、小さなプログラムを書きます。main 関数からです。

int main() {
    std::vector<std::string> data;

    data.push_back("abc");
    data.push_back("bcd");
    data.push_back("bcdef");
    data.push_back("bcdefg");
    data.push_back("c");

    complete<compare1>("bcd", data);
}

テストデータを用意して、complete 関数を呼び出しています。complete 関数は以下の通りです。

template <typename CompareFunctor>
void complete(const std::string& key, std::vector<std::string>& data) {
    typedef std::vector<std::string>::iterator vecstr_iterator;
    typedef std::pair<vecstr_iterator, vecstr_iterator> range;

    range result = std::equal_range(data.begin(), data.end(), key, CompareFunctor(key.size()));
    std::for_each(result.first, result.second, dump());
}

テンプレート引数は equal_range に渡す比較用ファンクタです。range は equal_range の戻り値を格納する型で、一致した範囲の先頭と末尾を示すイテレータのペアになります。最後に一致した内容をダンプしてます。ダンプするファンクタは単純そのもの。

struct dump {
    void operator()(const std::string& str) const {
	std::cerr << str << std::endl;
    }
};

比較用ファンクタは、キーの長さで大小比較しているだけです。

class compare1 {
    int length_;

public:
    compare1(int length) : length_(length) {}
    bool operator()(const std::string& lhs, const std::string& rhs) const {
	return lhs.substr(0, length_) < rhs.substr(0, length_);
    }
};

では、実行してみます。

% ./a.out
bcd
bcdef
bcdefg

うまくいっているようです。しかし、substr は string のインスタンスを毎回生成するので非効率です。調べてみると、compare というメソッドが用意されていたので、これを使うようにしてみます。

class compare2 {
    int length_;

public:
    compare2(int length) : length_(length) {}
    bool operator()(const std::string& lhs, const std::string& rhs) const {
	return 0 < rhs.compare(0, length_, lhs, 0, length_);
    }
};

complete 関数のテンプレート引数を compare2 にして確認したところ、結果は同じでした。これでひとまず OK ですね。

L 辞書で試してみる

では続けて、L 辞書でやってみるとどうなるのか確認してみます。main() を以下のように書き換えます。文字コードは当然 EUC です。

int main() {
    std::vector<std::string> data;
    std::fstream ifs("SKK-JISYO.L");
    std::string word;

    // 送りなしまで読み飛ばす
    while(getline(ifs, word)) {
        if(word == ";; okuri-nasi entries.") break;
    }

    // 見出し語の vector を構築する
    while(ifs >> word) {
	data.push_back(word);
	std::getline(ifs, word);
    }

    // 補完
    complete<compare2>("かたかな", data);
}

実行してみます。

% ./a.out
かたかな
かたかなご
かたかなひょうき

うまくいっているようです。

substr と compare の違いを計測する

せっかくなので、compare1 と compare2 でどれぐらい違いが出るのか計測してみました。まず計測用の perf 関数を用意します。

template <typename CompareFunctor>
void perf(const std::string& key, std::vector<std::string>& data) {
    stopwatch t(typeid(CompareFunctor).name());

    for(int i = 0; i < 100000; ++ i) {
	std::equal_range(data.begin(), data.end(), key, CompareFunctor(key.size()));
    }
}

equal_range を 10 万回繰り返します。stopwatch は以下のような単純なクラスです。

class stopwatch {
    clock_t begin_;
    const char* msg_;

public:
    stopwatch(const char* msg) : msg_(msg), begin_(clock()) {}
    ~stopwatch() {
	std::cerr << msg_ << ": " << (clock() - begin_) / (double)CLOCKS_PER_SEC << " seconds" << std::endl;
    }
};

main を書き換えて、

int main() {
    std::vector<std::string> data;
    std::fstream ifs("SKK-JISYO.L");
    std::string word;

    // 送りなしまで読み飛ばす
    while(getline(ifs, word)) {
	if(word == ";; okuri-nasi entries.") break;
    }

    // 見出し語の vector を構築する
    while(ifs >> word) {
	data.push_back(word);
	std::getline(ifs, word);
    }

    // 補完時間計測
    perf<compare1>("かたかな", data);
    perf<compare2>("かたかな", data);
}

実行してみます。

% g++ -O2 completion.cpp
% ./a.out
8compare1: 2.65 seconds
8compare2: 0.31 seconds

その差は歴然と言いたいところですが、現実問題として 10 万回も検索することはないので、たとえ substr を使ったとしても体感速度的には全く問題ないと思います。線形検索ならもっと劇的な差が出たことでしょう。

いずれにしても、思った通りの結果が出ると気持ちがいいですね ;-) server-completion への対応は前向きに検討したいと思います。