2010-04-12

gihyo.jpの計算幾何学の連載が終了しました

Algorithm Writing

gihyo.jpでの連載が、全12回で終了しました。当初の予定通り、線分交差、面分交差、ボロノイ図の3テーマを取り上げることができました。

最終回記事のページから、GUIのデモを含めて、全プログラムのソースコードがダウンロードできます。複数の点が重なる場合などの特殊ケースを全然考慮していないので、このままでは実用に向かないですが、何かの土台としては使えるのではないかと思います。

執筆にあたっては、以下の書籍が非常に参考になりました。アルゴリズムが1つ1つ丁寧に説明されていて、おすすめです。

Computational Geometry: Algorithms and Applications

作者: Mark de Berg,Otfried Cheong,Marc van Kreveld,Mark Overmars
出版社/メーカー: Springer
発売日: 2008/03/07
メディア: ハードカバー
購入: 1人クリック: 2回
この商品を含むブログ (2件) を見る

2010-02-09

『実用Git』を共訳しました

Book

id:hirataraさんとkentaro714さんの3人で、"Version Control with Git"を共訳しました。邦題は『実用Git』で、Amazonで予約受付開始されています。

実用Git

作者: Jon Loeliger,吉藤英明(監訳),本間雅洋,渡邉健太郎,浜本階生
出版社/メーカー: オライリージャパン
発売日: 2010/02/19
メディア: 大型本
購入: 7人クリック: 287回
この商品を含むブログ (45件) を見る

hirataraさんも言っていますが、濱野さんが書かれた『入門Git』に比べると、よりチュートリアル的な内容で、初心者にも分かりやすいのではないかと思います。

日本語版だけの付録として、hirataraさん自身が書かれた「Gitにおける日本語の利用」と、瀧内元気さん著の「GitHub入門」も追加されているので、これ1冊でかなりGitの理解が深まるのではないでしょうか。

『実用Git』、ぜひ読んでみてください。

2010-01-23

『詳解 ActionScript 3.0 アニメーション』

Book

オライリーさんから、『詳解 ActionScript 3.0 アニメーション』を献本いただきました。

詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック

作者: Keith Peters,相川愛三
出版社/メーカー: オライリージャパン
発売日: 2010/01/25
メディア: 大型本
購入: 12人クリック: 267回
この商品を含むブログ (13件) を見る

タイトルから想像して、狭い領域に話題を絞っているのかと思っていましたが、実際に読んでみるとテーマが多岐にわたっており、アルゴリズム自体の解説にもかなり重点がおかれていました。

まずFlashに特化した内容でいうと、後半の章でFlash 10の新機能である3D APIやPixel Benderが詳細に解説されていますが、この部分だけでも読む価値が十分にあると思います。

前半の章では、グラフィカルなプログラムを作る上で役立つ面白いアルゴリズムが多数紹介されています。鳥の群れの動きをシミュレートするBoidsのように、オブジェクトに人工生命のような動きをさせる「操舵行動」の解説、経路探索アルゴリズムとして有名なA*の解説、等角投影（いわゆるクォータービュー）の実現方法などが出てきます。個人的に一番面白かったのは等角投影の章で、これはアルゴリズムというよりもノウハウに近いものだけに、まとまった形での解説を読んだのは今回が初めてで、非常に参考になりました。

AS3はもちろん、あらゆるGUIプログラミングに活かすことのできる良書だと思いました。

2010-01-10

Solr 1.3と1.4の検索パフォーマンス比較

Java

TopHatenarとBlogopolisでは現在、全文検索用途にApache Solr 1.3を使っていますが、去年11月にSolr 1.4がリリースされたので、近いうちに1.4に移行したいと思っています。

そこで、1.3と1.4の検索パフォーマンスにどのくらい差があるのか、TopHatenarで収集しているブログの本文データを使って、以下の条件で計測してみました。

計測は、事前にSolrをウォームアップし、キャッシュが十分に効いた状態で行いました。

Solrサーバ環境
- OS: CentOS 5.4 (x86_64)
- CPU: Phenom II X4 905e
- RAM: DDR2-800 9GB
- HDD: Seagate ST3160815AS (160GB, 7200rpm)
- JRE: 1.6.0_17-b04 (64bit)
- Tomcat: 6.0.20
- Solrのキャッシュ設定
  - filterCache size: 512
  - queryResultCache size: 512
  - documentCache size: 512
  - queryResultMaxDocsCached: 200

インデックス
- ドキュメントの内容: ブログ記事（URL, タイトル, 本文）
- ドキュメント数: 約30万
- インデックスサイズ: 2.1GB

クライアント環境
- OS: Mac OS X 10.6.2
- CPU: Intel Core i5
- RAM: DDR3-1066 8GB
- JRE: 1.6.0_17-b04 (64bit)

検索方法
- Solrサーバへの接続手段: Javaプログラム (CommonsHttpSolrServerを使用)
- 使用クエリ: はてなブックマークの最頻出タグ1000個
- 検索対象フィールド: 本文
- 取得フィールド: URL, タイトル
- 検索結果の最大取得行数: 10, 100, 1000
- 同時接続数（スレッド数）: 1, 2, 4, 8, 16, 32, 64

計測結果

スループット（QPS, 1秒あたりのクエリ処理数）は、以下のグラフのようになりました。

レイテンシ（クエリの応答時間）の平均値は、以下のグラフのようになりました。

今回の条件下でSolr 1.3と1.4を比較すると、接続数が少ないうちはほとんど同等の検索パフォーマンスを示していますが、並列性が高くなると、圧倒的に1.4の方が速くなりました。64スレッドの場合、10行取得（最初の10件まで検索）時のスループットは3倍、レイテンシは10倍も優秀です。1000件取得になると、レイテンシは1.3に少し劣るものの、スループットはやはり3倍以上優秀です。

この大幅なパフォーマンス向上がSolr自身によるものか、Solrで内部使用しているLuceneが2.4-devから2.9に上がったことによるものか自分には分かりませんが（多分両方）、高負荷な環境でSolr 1.3を運用している場合、1.4への移行を検討した方が良さそうです。

2010-01-07

YAMAHA RTX1200を購入

Misc

TopHatenarなどを運用している自宅サーバで、今まではTime Capsuleをルータとして使ってきたんですが、時々タイムアウトしたりハングアップしたりしていて、負荷にはあまり耐えられない印象がありました。最近、そのTime Capsuleが完全に壊れてしまい、BUFFALOのブロードバンドルータに替えてみたら、今度はまったく負荷に耐えられず、タイムアウトが頻発してしまいました。

もっと高性能のルータを買わないと駄目だと思い、どのくらいのものにすれば良いのか感覚が掴めませんでしたが、とりあえずYAMAHAのRTX1200を買ってみました。