Hadoopを使わずにWikipediaのテキスト処理を400倍高速化

タイトルは釣りです。id:mamorukさんの書いたHadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記を読んで、そもそも1G程度のデータの単語頻度を数えるのに858分もかかるんだっけと思い、id:nokunoさんの資料を読んでみると単語頻度を求める際に

a
b
a
a

みたいなデータを

a 3
b 1

に変形するのにsortしたファイルをuniq -cで処理するということをやっていた。これはあまり効率のよい方法ではなくて行数をNとしたときにO(N log N)の計算時間となる(文字列比較はO(1)でやれることにする)。
これに対して、単語の頻度をハッシュ表で保存すると理想的な条件の元ではO(N)の計算時間で頻度を求めることが出来、より高速に計算することが可能となることが期待される。
また、単語数をWとしたとき、C++のmapのような二分探索木を使ってもO(N log W)とsortしてuniqするのに比べ、より低い計算量を達成できる。

単語の頻度表を求めるコードをC++のunordered_map(gccのバージョンによっては使えない場合があります、その場合は適宜boost/unordered_mapなどに置き換えてください)を使って書くと以下のようになる

#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
int main(){
  unordered_map<string , int> m;
  string line;
  while(getline(cin , line))
    m[line]++;
  unordered_map<string , int>::iterator it;
  for(it = m.begin(); it != m.end(); ++it)
    cout << it->first << " " << it->second << endl;
  return 0;
}

これを利用して日本語Wikideiaの生のunigramデータから単語頻度を求めると1分50秒で終了。コア数は1(CPUはCore i7 920, 2.67GHzでメモリが3G)でやってるので大体400倍ぐらい高速になっている計算になる。ちなみにunordered_mapをstd::mapに置き換えた場合4分49秒となった。

計算機を大量に並べてHadoopで分散処理というのも非常に価値のあることとは思いますが、会社によってはサーバを1台買うのにも非常に煩雑な手続きが必要で、しかも注文してから半年ぐらい来なかったり、開発環境のサーバが1台しかなかったりするので、こういった1台のサーバで処理を高速化するテクニックもまだまだ重要なのではないかと思いました。

あと、結局サーバを並べるといってもデータが2倍に増えたときにサーバが4倍必要になるとか言う状況だと、いつかは破綻するので計算量の見積りは大変重要です。

追記

id:n_shuyoさんに900倍を越えてほしかったといわれたので多少の高速化を試みてみた。データが1G程度しかないのでファイルの中身を全部メモリに読み込む+getlineを使わずに自力で改行をパースするという方針で書いた

#include <unordered_map>
#include <map>
#include <string>
#include <iostream>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
using namespace std;
int main(){
  struct stat st;
  char * fileName = "unigram_raw.txt";
  if(stat(fileName , &st)){
    perror("stat");
    return 1;
  }
  int fd = open(fileName  , O_RDONLY);
  char * buffer = new char[st.st_size];
  if(read(fd , buffer , st.st_size) != st.st_size){
    return 1;
  }
  int prev = 0;
  unordered_map<string , int> m;
  for(size_t i = 0 ; i < st.st_size ; ++i){
    if(buffer[i] == '\n'){
      string s(buffer + prev , buffer + i);
      m[s]++;
      prev = i + 1;
    }
  }
  unordered_map<string , int>::iterator it;
  for(it = m.begin(); it != m.end(); ++it)
    cout << it->first << " " << it->second << endl;
  return 0;
}

これだと手元の環境では62秒で終わり、800倍以上(900は行かなかったorz)の高速化になっている。

追追記

bufferを全部持っている以上、string => intのテーブルを持つのではなく、(文字列の開始位置,文字列の終了位置)をキーにしたほうが効率が良さそうと思い実装。

struct myeq : std::binary_function<pair<int , int> , pair<int , int> , bool>{
  char * buf;
  myeq(char * b) : buf(b) {}
  bool operator() (const pair<int , int> & x , const pair<int , int> & y) const{
    char * s = buf + x.first;
    char * t = buf + y.first;
    char * se = buf + x.second; // *se == '\n'
    for( ; *s == *t && s != se ; ++s , ++t)
      ;
    // *s != *t or (*s == '\n' => *t == '\n')
    return *s == *t;
  }
};

struct myhash : std::unary_function<pair<int , int> , size_t>{
  char * buf;
  myhash(char * b) : buf(b) {}
  size_t operator()(const pair<int , int> & p) const{
    size_t h = 0;
    for(int i = p.first ; i < p.second ; ++i){
      h = h * 31 + buf[i];
    }
    return h;
  }
};

int main(){
  struct stat st;
  char * fileName = "jawiki_unigram_raw.txt";
  if(stat(fileName , &st)){
    perror("stat");
    return 1;
  }
  int fd = open(fileName  , O_RDONLY);
  char * buffer = new char[st.st_size];
  if(read(fd , buffer , st.st_size) != st.st_size){
    return 1;
  }
  int prev = 0;
  myhash h(buffer);
  myeq   e(buffer);
  unordered_map<pair<int , int> , int  , myhash , myeq> m(3 , h , e);
  for(size_t i = 0 ; i < st.st_size ; ++i){
    if(buffer[i] == '\n'){
      pair<int , int> p(prev , i);
      unordered_map< pair<int , int> , int  , myhash , myeq>::iterator it = m.find(p); 
      if(it != m.end()){
        it->second++;
      }else{
        m.insert(pair<pair<int,int> , int>(p , 1));
      }
      prev = i + 1;
    }
  }
  unordered_map<pair<int , int> , int>::iterator it;
  for(it = m.begin(); it != m.end(); ++it){
    string s(buffer + it->first.first , buffer + it->first.second);
    cout << s << " " << it->second << endl;
  }
  return 0;
}

これだと手元の環境では49秒で終わり、無事900倍達成できたのであった。めでたし。