Hatena::ブログ(Diary)

ny23の日記 このページをアンテナに追加 RSSフィード

2010-06-11 流行りにのってみる

動的ダブル配列を使って Wikipedia のテキスト処理を高速化

| 動的ダブル配列を使って Wikipedia のテキスト処理を高速化を含むブックマーク 動的ダブル配列を使って Wikipedia のテキスト処理を高速化のブックマークコメント

Wikipediaによるテキストマイニング入門など,Wikipedia 中の単語頻度を測るのが流行っているようだ.例えば,Hadoop を使ったり(Hadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記),ハッシュを使ったり(tsubosakaの日記)とか.情報系の人間なら普通はハッシュで十分と思うところ,折角なので動的ダブル配列を使って測ってみた.動的ダブル配列から保存された文字列を効率的に取り出すには,ノードリンクを実装して traverse () を再帰的に呼び出せば良い.今回は MSD radix sort 用に sibling のリンクを昇順にしたバージョン(僅かに追加速度が低下)を利用. Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記のハッシュ (unordered_map) を利用したカウンタと比較してみる (gcc 4.6; -O2 -march=core2 -m64).

データは Wikipedia-ja の2010-03-06 版 (テキストで 10M x 128).ハッシュを利用したカウンタ (遅い順にhash_counter1, hash_counter2, hash_counter3) と,動的ダブル配列を使ったカウンタ (dda_counter) の実行結果 (on a server with Intel Xeon E5462 (3.2 Ghz)) は以下.

> ls -l unigram_raw.txt 
-rw-r--r--   1 xxxxx xxxxx 1645539124 2010-06-12 12:50 unigram_raw.txt

> time cat unigram_raw.txt | hash_counter1 > tmp.hash1
cat unigram_raw.txt  0.09s user 2.04s system 2% cpu 1:35.57 total
hash_counter1 > tmp.hash1  96.76s user 3.41s system 99% cpu 1:40.62 total

> time hash_counter2 > tmp.hash2
hash_counter2 > tmp.hash2  61.90s user 5.12s system 99% cpu 1:07.06 total

> time hash_counter3 > tmp.hash3
hash_counter3 > tmp.hash3  33.98s user 5.41s system 99% cpu 39.432 total

> time dda_counter unigram_raw.txt > tmp.dda
dda_counter unigram_raw.txt > tmp.dda  27.35s user 2.04s system 99% cpu 29.426 total

dda_counter では std::map と同様に,キーは辞書順で出力される.処理時間,消費メモリは hash_counter1 (101s, 177MB), hash_counter2 (67s, 1717MB), hash_coutner3 (39s, 1633MB), dda_counter (29s, 161MB).

というわけで,Hadoop やハッシュを使わなくても,動的ダブル配列を実装すれば,単語頻度のカウントは1750倍高速化される上,キーをソートして出力できます!動的ダブル配列ハヤーイと言いたいところだが,ランダム追加・検索だとハッシュとダブル配列は大差ないような気がしたので,ダブル配列のところをハッシュに変えた版を自作.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tr1/unordered_map>

struct equal_charp {
  bool operator () (const char* a, const char* b) const {
    int i = 0;
    for (; a[i] && b[i]; ++i)
      if (a[i] != b[i]) return false; // reject immediately
    return a[i] == b[i];
  }
};

struct hashfun_charp { // FNV-1a
  unsigned int operator () (const char* const &p) const {
    unsigned int h = 0x811c9dc5;
    for (char const *q = p; *q != '\0'; ++q)
      { h ^= *q; h *= 0x01000193; }
    return h;
  }
};

int main (int argc, char** argv) {

  typedef std::tr1::unordered_map <char*, int, hashfun_charp, equal_charp> hash;

  if (argc < 2)
    { std::fprintf (stderr, "Usage: %s file\n", argv[0]); std::exit (1); }
 
  FILE * reader = std::fopen (argv[1], "r");
  if (! reader)
    { std::fprintf (stderr, "no such file: %s\n", argv[1]); std::exit (1); } 

  // push
  hash keys;
  char * line = 0;
#ifdef __APPLE__
  size_t read = 0;
  while ((line = fgetln (reader, &read)) != NULL) {
#else
  ssize_t read = 0; 
  size_t  size = 0;
  while ((read = getline (&line, &size, reader)) != -1) {
#endif
    * (line + read - 1) = '\0';
    hash::iterator it = keys.find (line);
    if (it == keys.end ()) {
      char * copy = new char[read];
      std::strcpy (copy, line);
      it = keys.insert (hash::value_type (copy, 0)).first;
    }
    ++it->second;
  }
  std::fclose (reader);

  // print
  for (hash::iterator it = keys.begin (); it != keys.end (); ++it) {
    std::fprintf (stdout, "%s %d\n", it->first, it->second);
    delete [] it->first;
  }
 
  return 0;
}

実行してみる.

> time hash_counter4 unigram_raw.txt > tmp.hash4
hash_counter4 unigram_raw.txt > tmp.hash4  28.21s user 1.91s system 99% cpu 30.170 total

処理時間,消費メモリは,30s, 106M.動的ダブル配列を使ったカウンタとほとんど同じ速度(で,メモリ的には当然有利).釣りっぽいタイトルでしたが,char * をキーにしたハッシュと比較する限り,キーを整列する必要がなければダブル配列を持ち出すメリットは無いということでした.

また,ちゃんとメモリを適宜確保すれば,ファイル全体をメモリに載せる必要は無いです(頻度が2回以上の単語について無駄にメモリを割り当てる分遅い).コンテナの要素にはコピーコストの大きい要素を入れずに(コンテナのサイズを拡大する度に全要素をコピーし直す),ポインタを入れましょう.

先日の日記に書いたことにも関係するけど,Hadoop みたいな技術は,「処理にかかる時間を1/1000に短縮する」ための技術と認識している人と,「処理するデータを1000倍に増やす」ための技術と認識している人とで,実際に扱うデータのサイズに大きな差が出ると思う.

nokunonokuno 2010/06/12 18:29 ありがとうございます! どうもsortコマンドが遅すぎると思ってたところです。
ソートがO(n log(n))といったってlog(n)で400倍も遅くなるわけないし、と…

ny23ny23 2010/06/12 19:25 単語頻度のカウントに使う場合,100倍とまで行かなくても,手元で試した限り,10倍程度は変わりそうな感じでした.
これで解決されると良いですね.