2008-09-06

Array::Gap

明日は一ヶ月ぶりのIIR輪読会です。主催のたつをさんから「教科書の話題から何か適当に実装せよ」という課題が出ていたので、5章のインデックスの圧縮の所で見た Variable byte codes (以下 VB code) を使った圧縮の実装を作ってみました。

整列済みの整数を圧縮する手法

ここでの圧縮のポイントは二つ。

昇順に並べられた整数を、整数そのままの数で扱うのではなく、一つ前の要素との差で扱う。差で扱うと 21,314,156 → 21,314,157 という数は "1" というより小さい数で表現することができる。(整列済みなので、差が分かれば逆の操作で復元が可能)
32 ビット int の整数を固定長 32 ビットで表現するのではなく可変長バイトで表現する。(これが VB code) VB code なら小さな数字は 32ビット = 4バイトよりも小さなビット数で表現できる

この二つの手法を組み合わせると、大きな整数を差分で小さい数字として表現し、その小さい数字を可変長整数で小さなビット数で表現することができるので、圧縮効果が得られます。

整数を可変長なエンコーディングで圧縮するアルゴリズムは、より圧縮率の高いγコードやδコードなども有名です。VB code は実装が簡単なのが利点です。VB code はバイトレベルでの圧縮、γコード/δコードはビットレベルでの圧縮になります。

ASN.1 Basic Encoding Rules / perl の pack('w', ...)

IIR で解説されている VB code は、ほぼ同じ変換規則で ASN.1 BER (Basic Encoding Rules) という仕様で標準化されているようです。(IIR での VB code と ASN.1 BER は先頭ビットの解釈が異なる。)

Perl の場合、pack() が整数を BER でエンコーディングする機能を提供しています。数値の 5 を 00000101 に変換するには

pack('w', 5) # 00000101

で ok です。

Array::Gap

整列済みの整数リストを、pack() を利用した圧縮済みの配列として BER で保持しつつ、普通のリスト同様に扱えるよう操作を加えたクラスが今回作った Array::Gap です。

#!/usr/bin/env perl
use strict;
use warnings;

use FindBin::libs;
use Perl6::Say;
use Array::Gap;

my $array = Array::Gap->new;
$array->push(824);
$array->push(829);
$array->push(830);
$array->push(1024);
$array->push(215406);

my $it = $array->iterator;
while ($it->has_next) {
    say $it->next;
}

というコードの出力は

となります。一見すると Array::Gap 内部で配列を持っているだけのように見えますが、実際には内部で整数の配列は保持しておらず、隣り合う整数の差分をBER によるバイナリ表現、つまりスカラーで保持するようになっています。

ソースコードを以下に置いておきます。

http://github.com/naoya/perl-array-gap/tree/master

以上、夏休みの宿題でした。

追記

say $array

で、二進数の文字列表現を表示することができます。

my $array = Array::Gap->new;
$array->push(824);
$array->push(829);
$array->push(830);
$array->push(1024);
$array->push(215406);

say $array

ですと

100001100011100000000101000000011000000101000010100011011000101001101110

となります。72ビットです。工夫せずに実装すると、32ビット x 5 = 160 ビット*1になるところ、72 ビットで済んでいます。

*1:実際には 32ビット x 5 ではなく「Perl のスカラーのサイズ」 x 5 です。

2008-09-04

第2回インターンシップ

8月の第1回が終わり、続けて9月の第2回目のインターンが始まっています。今日はもう4日目、MVC フレームワークの講義です。

8月のインターンでは、後半二週間の開発ではてなダイアリーの AtomPub や下書き機能、はてなハイクの API、新しいはてなキーワードのランキング機能、フォトライフのアニメーションGIF対応、(これはまだ未公開ですが) 新はてなブックマークのある重要なバックエンドシステムの実装など、様々なものが生まれました。素晴らしい成果でした。

9月のインターンでは果たして何が生まれるでしょうか。今からとても楽しみです。

2008-08-18

インターン後半 / 第2回募集

今日からインターンも折り返し、後半2週間が始まりました。2週間のトレーニングを終えて、いよいよ実地でアプリケーション開発が始まっています。各プロジェクトチームに配属になり、はてなスタッフの指導のもと新機能などの開発を行います。

社内の方々で仕様の検討などディスカッションが行われていて、活気に溢れています。再来週の成果発表が楽しみです。チームよっては、もっと早い段階でリリースできそうな話題もちらほら。

インターン第二回の参加者を募集しています

この夏のインターンですが、来月9月にも実施します。既に募集を開始していて、締めきりは 8/20 (水) でもうすぐです。詳しくは http://www.hatena.ne.jp/company/staff/intern をご覧ください。

第一回の前半のトレーニングがどのようなものだったか、実際の参加者がブログに感想などを書いていますのでこちらをご覧いただくと良いでしょう。

実際のプロダクションに載せるコードを書いてもらうことになるので、そこの品質はしっかり確保しておきたい...ということでの二週間のトレーニングでした。ここまで教育に力を入れるインターンは珍しいのかもしれませんが、得るものはしっかり得てもらって、出すものはしっかり出してもらうというのが弊社の方針です。続く 9月、また来年も同様のカリキュラムで進行していきたいと思っています。

2008-08-13

アルゴリズムイントロダクション輪講@京都

社内エンジニアの間に、計算機科学をマジメにやろうという機運が高まっています。それを受けはてな社内で計算機科学に関する教科書の輪講をやろうという話になりました。という訳でまずはアルゴリズムの教科書「アルゴリズムイントロダクション第1巻改訂2版 (1)」を輪講してみることにします。はてなスタッフだけでなく社外からの参加も募集しているので、京都オフィスに近い方はぜひご参加下さい。

id:motemen がコンピュータサイエンス関連書籍の輪講を開催するとのこと。もちろん自分も参加します。教科書は何が良いか色々考えたようですが、まずはアルゴリズムイントロダクションに決まったようです。アルゴリズムイントロダクション、ちょうど今日届いたのでざっと見てみた所、数学的な観点からアルゴリズム/データ構造についての基礎を論じている良い書籍だと思いました。

アルゴリズムとデータ構造は最も重要な基礎ですが、これまで理解が曖昧なのをごまかしてきた感があるので、ここらで是非梃子入れしたいと思っていました。楽しみです。

この輪講は弊社の京都オフィス(烏丸御池です)が会場ですが、社外の方の参加も募集してます。学生さんも大歓迎です。8/25 (月) 開始で隔週ぐらいで開催です。応募方法など詳しくは id:motemen:20080813:1218634304 を参照してください。

2008-08-10

Kansai.pm#10 での発表資料 (Thrift について)

今日は第10回 Kansai.pm でした。自分も 10 分だけ、Thrift について発表を行いました。資料を以下にアップロードしました。

http://bloghackers.net/~naoya/ppt/080810kansaipm.ppt (ppt)
http://www.slideshare.net/naoya1977/about-thrift/ (Slide Share)

Thrift については今月末発売の WEB+DB PRESS Vol.46 の連載記事でも解説を行っていますので、興味のある方はご一読いただければ幸いです。

今回の Kansai.pm、場所は弊社オフィスで開催でした。閉会後そのままピザを取って懇親会に。なぜか id:azurestone さんらと Linux セキュアOS についての話題で盛り上がっておもむろにカーネルのコードリーディングが始まったり、こちらも楽しかったです。みなさまお疲れさまでした。

2008-08-10

サーバ/インフラ Tech Meeting の資料など

金曜日はサーバー/インフラを支える技術出版記念イベントサーバ/インフラ Tech Meeting の日でした。自分は「Linux カーネルの読み方」と題して、自分なりにまとめたカーネルのソースコードを読むコツについてお話させていただきました。

発表資料を以下にアップロードしました。

http://bloghackers.net/~naoya/ppt/08080924svr_techmeeting.ppt (ppt)
http://www.slideshare.net/naoya1977/how-to-read-linux-kernel/ (Slide Share)

同じく著者のひろせさんからはなぜこの本を書いたか、どういう本なのかという概論 (One more thing もありました)。Klab の安井さんは DSAS について、特に「ダイナミック」をキーワードにした幾つかのインフラ構築の方法論、弊社田中 (id:stanaka) からは「はてなのインフラいまむかし」ということで、これまでのはてなのインフラの変遷についての発表がありました。みなさんとても面白い発表で、聞く側としても有意義でした。

発表の動画は id:coji さんに撮影いただき、すでに http://techtalk.jp/2008/08/-tech-meeting.html にすべてアップロードされています。ありがとうございます。

イベント終了後は、書籍のサイン会がありました。顔見知りも多く、サインをするのは恥ずかしかったです (実弟にサインすることになるとは思わなかった...) こればかりは慣れませんね。

さて、本日 8/10 ははてなのオフィスで Kansai.pm#10 です。忙しい忙しい。

2008-08-08

インターン 4日目、5日目

インターンシップも5日目です。4日目の昨日は id:motemen から MVC フレームワークの話。

はてなの MVC フレームワークである Ridge についての講義でした。一昨日に作成した CLI のデータベースアプリケーションを、MVC フレームワークに載せてウェブアプリケーション化するというもの。CLI での MVC とウェブアプリケーションでの MVC を比較しての解説でした。この順番で学ぶと、何がモデルで何がコントローラなのかという、コンポーネントの区別が付きやすくて良いでしょう。

毎日の午後には、前日の講師からフィードバックがあります。課題の提出状況や、点数について。ここで課題の中で面白かった実装を紹介します。「○○さんの CLI の実装はこんな風に、無名関数によるディスパッチテーブルを使っていて綺麗に書けていました...」など。

今日は id:secondlife から JavaScript や Flash によるユーザーインタフェースプログラミングの話。自分は東京出張なので、一回休みです。

前半は今日で折り返し、ウェブアプリケーション開発については一区切り。来週は大規模データを前提にしたデータベース設計、計算の仕方、Thrift や Hadoop を使った分散プログラミングなどの話に入っていきます。

なお、インターンシップは同じ内容を9月にも予定しています。今日中には応募を開始できるのではないかと思います。