2009-07-03

google::dense_hash_mapのset_deleted_keyメソッド

Programming

google::dense_hash_mapを使うときは、データのinsertを行う前にset_empty_keyメソッドで空のとき用のキーを指定しておく必要がある。同様にキーの削除を行う前には、set_deleted_keyメソッドで削除されたとき用のキーを指定しておかなければならない。

で、このset_deleted_keyをあらかじめ指定しておくようにしてたんだけど、そうしたら何か遅くなった？と思って、ちょっと動作速度を調べてみた。

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <google/dense_hash_map>

int main() {
  clock_t start, end;
  const int max = 20000000;

  srand(time(NULL));

  // not set_deleted_key
  google::dense_hash_map<int, int> h1;
  h1.set_empty_key(-1);
  start = clock();
  for (int i = 0; i < max; i++) { // write
    h1[i] = i;
  }
  for (int i = 0; i < max; i++) { // read
    int r = rand() % max;
    int val = h1[r];
  }
  end = clock();
  std::cout << "not_set_deleted_key: "
            << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

  // set_deleted_key
  google::dense_hash_map<int, int> h2;
  h2.set_empty_key(-1);
  h2.set_deleted_key(-2);
  start = clock();
  for (int i = 0; i < max; i++) { // write
    h2[i] = i;
  }
  for (int i = 0; i < max; i++) { // read
    int r = rand() % max;
    int val = h2[r];
  }
  end = clock();
  std::cout << "set_deleted_key: "
            << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

  return 0;
}

set_deleted_keyをあらかじめ指定した場合と、指定しなかった場合それぞれで、データのinsertとgetを繰り返し実行したときの処理時間を調べてみた。

% g++ dense_hash_bench.cc 
% ./a.out
not_set_deleted_key: 17.2
set_deleted_key: 17.65

びみょーな差だけど、set_deleted_keyを指定しておくと遅くなった。

ドキュメントを見てみると、set_empty_keyは初めから指定しておかないとダメだけど、set_deleted_keyはeraseが呼ばれるまでは実行しておく必要はないらしい。
http://goog-sparsehash.sourceforge.net/doc/dense_hash_map.html#6

なのでdense_hash_mapを使うときは、eraseが呼ばれる直前まではset_deleted_keyは使用しない方がよさそう。それとclear_deleted_keyを呼べばdeleted_keyもクリアされて、遅くなっていたのもの元に戻ってたので、set_deleted_keyを使用した後はclear_deleted_keyも忘れずに。

そもそもempty_keyやdeleted_keyを指定しておかないといけないかが分かっていないんだけど…。やはりアルゴリズムの中身をちゃんと勉強してないとダメだな。

2009-06-28

Wikipediaのリダイレクトを使って同義語とれるかな

Programming

wikipediaは同義語の単語(「ASIA」と「アジア」とか)は、代表的な単語にリダイレクトするようになっています。つまりリダイレクト関係にある単語は、大抵は同じ意味であることが期待されます。そこでこのリダイレクト関係を使って、同義語を抽出してみようと思います。

実際に作成したスクリプトは以下の通りです。

#!/usr/bin/perl
#
# wikipediaのリダイレクトを使って同義語を抽出
#
# Usage:
# % bzcat jawiki-latest-pages-articles.xml.bz2 | ./redirect_words.pl > result.tsv
#
# 参考ページ: 
# [を] Wikipediaのキーワードリンクを使って関連語データを作ってみた
# http://chalow.net/2007-06-09-3.html
#

use strict;
use warnings;
use Encode qw(encode decode);

sub word_ok {
    my $word = shift;
    return unless $word;
    return if $word =~ m{[:\|\n\t\[\]]};;
    return if $word =~ m{^[\#\s]};;
    $word =~ s/\s*\(.+?\)$//;
    return if $word =~ /一覧$/;
    return if $word =~ /\d+月\d+日$/;
    return if $word =~ /^\d{4}年$/;
    return if $word =~ /Wikipedia:/;
    return if $word =~ /Portal:/;
    return if $word =~ /その他/;
    return if $word =~ /の比較/;
    return if $word =~ /（曖昧さ回避）/;
    return if $word =~ /#/;
    return $word;
}

my $flag = 0;
my $content;
while (my $line = <STDIN>) {
    chomp $line;
    if (!$flag && $line =~ m{<page>}) {
        $flag = 1
    }
    if ($flag) {
        $content .= $line;
    }
    if ($flag && $line =~ m{</page>}) {
        my ($title) = $content =~ m{<title>([^<]+)<};
        $title = word_ok($title);
        if ($title) {
            my @words;
            push @words, $title;

            my ($redirect_large) = $content =~ m/#REDIRECT \[\[(.+?)\]\]/;
            $redirect_large = word_ok($redirect_large);
            push @words, $redirect_large if $redirect_large;

            my ($redirect_small) = $content =~ m/{{[Rr]edirect\|(.+?)}}/;
            if ($redirect_small) {
                my @redirects;
                foreach my $word (split /\|/, decode 'utf-8', $redirect_small) {
                    $word = word_ok(encode 'utf-8', $word);
                    push @words, $word if $word;
                }
            }
            if (scalar(@words) > 1) {
                print join "\t", @words;
                print "\n";
            }
        }
        $flag = 0;
        $content = '';
    }
}

抽出結果はこちら。(ファイルサイズが9M近くあるので注意)

AFTA	ASEAN自由貿易地域
AFTC	自動車公正取引協議会
AFU	アフリナット国際航空

こんなのとか、

明石焼き    玉子焼
明石西公園  兵庫県立明石西公園
明石西高等学校  兵庫県立明石西高等学校
明石中宮    明石の姫君

こんなのが取れてます。まあ大抵は1文字違いの単語とかで、編集距離で判定した方が良さそうなものばかりですが。

使い道はなさそうですが、メモとして置いておきます。

2009-06-28

むこうぶち6 高レート裏麻雀列伝

DVD

むこうぶち6 ~高レート裏麻雀列伝~ [DVD]

出版社/メーカー: GP~[WA
発売日: 2009/06/25
メディア: DVD
クリック: 40回
この商品を含むブログ (2件) を見る

原作で好きだったので、DVD借りてきて見てみた。今回はホステスのスカウトが相手。原作でも読んでるので内容は分かってるけど、なかなか面白い。どうしても牌捌きの部分は俳優さんはあまりうまくないけど、それでも麻雀の内容はなかなか楽しめる。

2009-06-28

うめ『大東京トイボックス4』

本

大東京トイボックス(4) (バーズコミックス)

作者: うめ
出版社/メーカー: 幻冬舎
発売日: 2009/06/24
メディア: コミック
購入: 4人クリック: 26回
この商品を含むブログ (44件) を見る

ゲーム開発会社のお話第4巻。今回は前回ほど大きな動きもなくて、開発中のドタバタが書かれている。それにしても仕様変更多すぎ。仕様変更で追加した機能が、やっぱりいらないって言われて、先祖返りしちゃったソースコードが全体の2割以上ってちょっとひどい気が…。プロデューサーの思うがままに作らされてるって、ちょっと怖いね。

2009-06-23

ハゲタカ

DVD

ハゲタカ DVD-BOX

出版社/メーカー: ポニーキャニオン
発売日: 2007/07/18
メディア: DVD
購入: 10人クリック: 161回
この商品を含むブログ (214件) を見る

テレビ版のハゲタカのDVDを全部借りて見てみた。これかなり面白い。どれだけリアリティのある話なのかは分からないけど、話の展開がよくできていて、見ていて先が気になってしょうがない。役者もいい面子を揃えていて登場人物がみんなかっこいい。特に主役の大森南朋とライバル役の柴田恭兵が非常にいい。

DVDがかなり面白かったので、今は小説を読み中。ドラマは小説からかなりストーリーを変えてきたんだなぁ。ドラマでは主役の鷲津は人間味が結構ある感じだけど、小説ではまだそういうところは見えてこない。どっちがいいかと言われると、ドラマは展開の面白さとかっこよさ、小説はもう少し細かいところまで突っ込んだ面白さがあって、どちらも面白い。

積ん読がたまりまくってるけど、しばらくは原作者の真山仁の本を読み漁ろうかなと。amazonでの評判もみんないいようなので、今から楽しみ。