『プログラミングScala』は腰を据えたScalaの学習に最適

1/20発売予定のオライリージャパンの新刊、『プログラミングScala』を献本いただきました。

プログラミングScala

プログラミングScala

この本の敷居ははっきり言って高く、『Scalaスケーラブルプログラミング』に近いレベルだと思います。その難しさは、Scalaの型システムと関数型プログラミングを正面から解説しているところから来ています。重いテーマなので後回しにしたくなりますが、この部分の理解が曖昧なままでは、結局、いつまで経ってもScalaを理解したことにならないので、本書や『Scalaスケーラブルプログラミング』のような正面突破のアプローチは正解だと思います。

Scalaスケーラブルプログラミング』と『プログラミングScala』の比較としては、前者はScalaを設計した本人が原著者なこともあって、言語機能ごとに章がかっちり分割されているのに対し、後者は「ScalaOOPするには?」「Scalaにおけるデザインパターンは?」のような、ユーザ視点の緩やかな章立てになっている印象を受けました(追記: 本書の原共著者のAlex Payneさんは、TwitterのバックエンドをRubyからScalaに移植したチームメンバーだそうです)。

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

内容的にももちろん素晴らしく、『Scalaスケーラブルプログラミング』と併読をおすすめしたいです。この2冊を横に置いて、プログラムを実際に打ち込みながら、じっくり学習するのが良いと思います。

追記: 原著はScala 2.7をベースにしていますが、この翻訳版は、紙面の内容が2.8と互換性の問題を持つ場合の全箇所に脚注が入っていることと、2.8の新機能を紹介する付録もあるので、2.8の環境で全く問題なく使える本だと思います。

fastutilの注意点

WEB+DB PRESS Vol.60で、「fastutilとsuxによる大規模データ処理」と題して、プリミティブコレクションライブラリのfastutilと、簡潔データ構造ライブラリのsuxを紹介する記事を書きました。

WEB+DB PRESS Vol.60

WEB+DB PRESS Vol.60

fastutil: http://fastutil.dsi.unimi.it/
sux: http://sux.dsi.unimi.it/

fastutilは特に汎用性が高く、いろいろな場面で使えるライブラリだと思うのですが、記事に挙げていない注意点も若干あるので、以下に書きたいと思います。

メソッド名の取り違えによる思わぬautoboxingの発生

fastutilでは、プリミティブリストはjava.util.Listと、プリミティブマップはjava.util.Mapと互換性を持っていて便利なのですが、その反面、get()メソッドがjava.util.List#get()やjava.util.Map#get()を実装しているため、何気なくget()メソッドを使うとautoboxingが発生してしまいます。

例えばIntArrayListには以下の2種類のgetメソッドがあり、プリミティブ値を直接取得するには後者のgetInt()メソッドを呼ぶ必要があります。

  • Integer get(int index);
  • int getInt(int index);

Mapのイテレーションが遅い

fastutilのパフォーマンスは、全体的にMahout CollectionsやTroveよりも優秀なのですが、Mapのイテレーションに関しては劣っています。

Mahout CollectionsやTroveのMap実装では、以下のように内部イテレータを使って高速なイテレーションができるのですが、fastutilにはそれがありません。

// Mahout Collectionsの場合
OpenIntIntHashMap map = new OpenIntIntHashMap();
...
map.forEachPair(new IntIntProcedure() {
    @Override
    public boolean apply(int key, int value) {
        // 何らかの処理
        return true;
    }
});

fastutilのマップで高速なイテレーションをしたい場合は、各マップクラスを継承して、内部イテレータを実装した方が良いと思います。

そこまでしたくないという場合、fastutilでは以下のようにfastIteratorという外部イテレータが使えます。記述が少し冗長になりますが、通常のイテレータよりは高速です。

Int2IntMap map = new Int2IntOpenHashMap();
...
Int2IntMap.FastEntrySet entrySet = (Int2IntMap.FastEntrySet) map.int2IntEntrySet();
ObjectIterator<Int2IntMap.Entry> it = entrySet.fastIterator();
while (it.hasNext()) {
    Int2IntMap.Entry e = it.next();
    int key = e.getIntKey();
    int value = e.getIntValue();
    // 何らかの処理
}

29ビット以上のint値にも対応できるようにSimple9を調整

Simple-9について解説 - tsubosakaの日記
http://ameblo.jp/th0083/entry-10483740192.html

Simple9は、整数列を高速に圧縮するアルゴリズムです。32bitのint値を上位4bitと下位28bitに分けて、下位28bitにデータをできるだけ多く詰め込み、上位4bitで詰め込みのパターンを表現します。パターンは全部で9種類あります。

上位4bit パターン
0000 1bit x 28
0001 2bit x 14
0010 3bit x 9
0011 4bit x 7
0100 5bit x 5
0101 7bit x 4
0110 9bit x 3
0111 14bit x 2
1000 28bit x 1

ただしこのレイアウトでは、圧縮対象の整数列の中に29bit以上の数値が入っている場合に対応できません。そこで、詰め込み方を少し変更してみました。

上位4bit パターン
0000 1bit x 28
0001 2bit x 14
0010 3bit x 9
0011 4bit x 7
0100 5bit x 5
0101 7bit x 4
0110 9bit x 3
0111 14bit x 2
10XX 30bit x 1(XXのビットも使って30bitを表現する)
1100 ここでの残りビットは捨て、次の位置に32bit x 1を置く

この表のように、上位4bitのうち2bitを使うことで30bitまでは詰め込めるようにしてみました。

以下、プログラムです。パフォーマンス重視のためTroveを使い、全部のパターンをハードコーディングしました。

import gnu.trove.TIntArrayList;

public class SafeSimple9Codec {
    public int[] encode(int[] array) {
        // 再割り当てを避けるため初期サイズを大きめに取る
        TIntArrayList result = new TIntArrayList(array.length);

        int len = array.length;
        int i = 0, n = 0, code = 0, v = 0;
        while (i < len) {
            // 1bit x 28
            for (n = 0, code = 0; n < 28 && i + n < len && ((v = array[i + n]) & ~0x1) == 0; n++) {
                code = (code << 1) | v;
            }
            if (n == 28) { result.add(0x00000000 | code); i += n; continue; }
            // 2bit x 14
            for (n = 0, code = 0; n < 14 && i + n < len && ((v = array[i + n]) & ~0x3) == 0; n++) {
                code = (code << 2) | v;
            }
            if (n == 14) { result.add(0x10000000 | code); i += n; continue; }
            // 3bit x 9
            for (n = 0, code = 0; n < 9 && i + n < len && ((v = array[i + n]) & ~0x7) == 0; n++) {
                code = (code << 3) | v;
            }
            if (n == 9) { result.add(0x20000000 | code); i += n; continue; }
            // 4bit x 7
            for (n = 0, code = 0; n < 7 && i + n < len && ((v = array[i + n]) & ~0xf) == 0; n++) {
                code = (code << 4) | v;
            }
            if (n == 7) { result.add(0x30000000 | code); i += n; continue; }
            // 5bit x 5
            for (n = 0, code = 0; n < 5 && i + n < len && ((v = array[i + n]) & ~0x1f) == 0; n++) {
                code = (code << 5) | v;
            }
            if (n == 5) { result.add(0x40000000 | code); i += n; continue; }
            // 7bit x 4
            for (n = 0, code = 0; n < 4 && i + n < len && ((v = array[i + n]) & ~0x7f) == 0; n++) {
                code = (code << 7) | v;
            }
            if (n == 4) { result.add(0x50000000 | code); i += n; continue; }
            // 9bit x 3
            for (n = 0, code = 0; n < 3 && i + n < len && ((v = array[i + n]) & ~0x1ff) == 0; n++) {
                code = (code << 9) | v;
            }
            if (n == 3) { result.add(0x60000000 | code); i += n; continue; }
            // 14bit x 2
            for (n = 0, code = 0; n < 2 && i + n < len && ((v = array[i + n]) & ~0x3fff) == 0; n++) {
                code = (code << 14) | v;
            }
            if (n == 2) { result.add(0x70000000 | code); i += n; continue; }
            // 30bit x 1
            if (((v = array[i]) & ~0x3fffffff) == 0) {
                result.add(0x80000000 | v); i++; continue;
            }
            // (over 30 bit)
            result.add(0xc0000000);
            result.add(v);
            i++;
        }

        return result.toNativeArray();
    }

    public int[] decode(int[] array) {
        // 再割り当てを避けるため初期サイズを大きめに取る
        TIntArrayList result = new TIntArrayList(array.length);

        int len = array.length;
        for (int i = 0; i < len; i++) {
            int v = array[i];
            int selector = (v >> 28) & 0xf;
            switch (selector) {
            case 0x0: // 1bit x 28
                result.add((v >> 27) & 0x1);
                result.add((v >> 26) & 0x1);
                result.add((v >> 25) & 0x1);
                result.add((v >> 24) & 0x1);
                result.add((v >> 23) & 0x1);
                result.add((v >> 22) & 0x1);
                result.add((v >> 21) & 0x1);
                result.add((v >> 20) & 0x1);
                result.add((v >> 19) & 0x1);
                result.add((v >> 18) & 0x1);
                result.add((v >> 17) & 0x1);
                result.add((v >> 16) & 0x1);
                result.add((v >> 15) & 0x1);
                result.add((v >> 14) & 0x1);
                result.add((v >> 13) & 0x1);
                result.add((v >> 12) & 0x1);
                result.add((v >> 11) & 0x1);
                result.add((v >> 10) & 0x1);
                result.add((v >> 9) & 0x1);
                result.add((v >> 8) & 0x1);
                result.add((v >> 7) & 0x1);
                result.add((v >> 6) & 0x1);
                result.add((v >> 5) & 0x1);
                result.add((v >> 4) & 0x1);
                result.add((v >> 3) & 0x1);
                result.add((v >> 2) & 0x1);
                result.add((v >> 1) & 0x1);
                result.add(v & 0x1);
                break;
            case 0x1: // 2bit x 14
                result.add((v >> 26) & 0x3);
                result.add((v >> 24) & 0x3);
                result.add((v >> 22) & 0x3);
                result.add((v >> 20) & 0x3);
                result.add((v >> 18) & 0x3);
                result.add((v >> 16) & 0x3);
                result.add((v >> 14) & 0x3);
                result.add((v >> 12) & 0x3);
                result.add((v >> 10) & 0x3);
                result.add((v >> 8) & 0x3);
                result.add((v >> 6) & 0x3);
                result.add((v >> 4) & 0x3);
                result.add((v >> 2) & 0x3);
                result.add(v & 0x3);
                break;
            case 0x2: // 3bit x 9
                result.add((v >> 24) & 0x7);
                result.add((v >> 21) & 0x7);
                result.add((v >> 18) & 0x7);
                result.add((v >> 15) & 0x7);
                result.add((v >> 12) & 0x7);
                result.add((v >> 9) & 0x7);
                result.add((v >> 6) & 0x7);
                result.add((v >> 3) & 0x7);
                result.add(v & 0x7);
                break;
            case 0x3: // 4bit x 7
                result.add((v >> 24) & 0xf);
                result.add((v >> 20) & 0xf);
                result.add((v >> 16) & 0xf);
                result.add((v >> 12) & 0xf);
                result.add((v >> 8) & 0xf);
                result.add((v >> 4) & 0xf);
                result.add(v & 0xf);
                break;
            case 0x4: // 5bit x 5
                result.add((v >> 20) & 0x1f);
                result.add((v >> 15) & 0x1f);
                result.add((v >> 10) & 0x1f);
                result.add((v >> 5) & 0x1f);
                result.add(v & 0x1f);
                break;
            case 0x5: // 7bit x 4
                result.add((v >> 21) & 0x7f);
                result.add((v >> 14) & 0x7f);
                result.add((v >> 7) & 0x7f);
                result.add(v & 0x7f);
                break;
            case 0x6: // 9bit x 3
                result.add((v >> 18) & 0x1ff);
                result.add((v >> 9) & 0x1ff);
                result.add(v & 0x1ff);
                break;
            case 0x7: // 14bit x 2
                result.add((v >> 14) & 0x3fff);
                result.add(v & 0x3fff);
                break;
            case 0xc: // (over 30bit)
                result.add(array[i + 1]);
                i++;
                break;
            default: // 30bit x 1
                result.add(v & 0x3fffffff);
                break;
            }
        }

        return result.toNativeArray();
    }
}

Twitter本文と言及URLの圧縮

最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつgzip等で圧縮してもほとんど意味がないか、オーバーヘッドが出て逆効果になってしまいます。

そこで、収集済みのサンプルデータを元にハフマン木を作っておき、それを共通利用してtweetを圧縮してみました。

用意したのは、英語ユーザ/日本語ユーザ/韓国語ユーザ各1000人のtweetサンプルをベースにしたハフマン符号と、tweet本文から抽出したURL文字列をベースにしたハフマン符号の4種類です。

頻度表は次のようになりました。

char
(en)
freq
(en)
char
(ja)
freq
(ja)
char
(ko)
freq
(ko)
char
(url)
freq
(url)
(space) 1348393 (space) 272693 (space) 1153658 . 117835
e 699224 t 190132 . 223743 / 117587
t 608528 142493 t 133262 t 104686
o 533925 / 140918 109998 l 96779
a 501332 125271 o 106729 i 92201
i 448181 i 124956 e 100288 b 76967
n 421090 o 124626 / 97184 o 72043
s 379668 a 123180 i 90800 m 67298
r 368706 113045 a 83993 e 66610
h 296416 e 107796 @ 79703 y 65559
l 284100 104583 76449 c 56271
d 212750 92110 n 75734 a 53425
u 196833 90285 71036 r 49960
c 185527 h 90026 h 66954 w 40989
m 182875 88902 p 61647 n 40891
p 170037 83075 r 58089 s 39480
... ... ... ... ... ... ... ...

(追記: URLから"http://"は除去済み)

現在、Twitterではbit.lyが良く使われるので、'b','i','t','l','y'のURL使用文字としての出現頻度が高くなっていることが表から分かります。この偏りは今後変わるかもしれません。

これらの固定ハフマン符号を使って、実際にtweet本文や言及URLを圧縮してみたところ、次のような結果になりました。

符号ベース 圧縮対象 圧縮率
英語tweet 英語tweet 61.56%
英語tweet スペイン語tweet 62.71%
英語tweet ポルトガル語tweet 65.32%
英語tweet インドネシア語tweet 66.93%
日本語tweet 日本語tweet 47.64%
韓国語tweet 韓国語tweet 48.12%
URL URL 68.93%

英語tweetをベースにしたハフマン符号は、西欧言語に対しては大体共通して有効でした。日本語と韓国語が50%を切る優秀な圧縮率なのは、圧縮前の文字列がUTF-8なので、1文字あたり3バイト使われている確率が高くて非効率だったからだと思います。

このように、サンプルデータを元にした固定ハフマン符号を使う方法は、1件あたりの文字数が少ないtweet本文やURLの圧縮において有効だと分かりました。さらに、毎回ハフマン木を作らなくて良いので、パフォーマンス的にも非常に有利だと思います。

S2GWT的なもの

GWTのRPCでは、com.google.gwt.user.client.rpc.RemoteServiceを継承したサービスインタフェースとその対になる非同期インタフェース、そしてcom.google.gwt.user.server.rpc.RemoteServiceServletを継承したサービス実装の3点セットが必要になります。

GWTアプリケーションでSeasar2を使っている場合、DI機能でサービス実装をインジェクションしたいところですが、GWTのサービス実装クラスは個別にサーブレットとしてweb.xmlに登録する必要があり、そのままではDIすることができません。

そこで、GWTからS2へのゲートウェイとなる単一のサーブレットを用意することを考えます。GWT側では全てのRPCをこのゲートウェイマッピングします。ゲートウェイ内部ではS2Containerをルックアップして適切なサービス実装を探し、処理を委譲するわけです。

こういう方式を実践している方は他にもおられるようです。僕はこちらを参考にして、以下のようにゲートウェイを作成しました。

import org.seasar.framework.container.SingletonS2Container;
import org.seasar.framework.util.StringUtil;

import com.google.gwt.user.client.rpc.IncompatibleRemoteServiceException;
import com.google.gwt.user.client.rpc.RemoteService;
import com.google.gwt.user.client.rpc.SerializationException;
import com.google.gwt.user.server.rpc.RPC;
import com.google.gwt.user.server.rpc.RPCRequest;
import com.google.gwt.user.server.rpc.RemoteServiceServlet;
import com.google.gwt.user.server.rpc.impl.ServerSerializationStreamReader;


public class S2RemoteServiceServlet extends RemoteServiceServlet {
    private static final long serialVersionUID = -7247717864097930745L;

    @Override
    public String processCall(String payload) throws SerializationException {
        String componentName = getRemoteServiceComponentName(payload);
        Object service = SingletonS2Container.getComponent(componentName);
        try {
            RPCRequest rpcRequest = RPC.decodeRequest(payload, null, this);
            onAfterRequestDeserialized(rpcRequest);
            return RPC.invokeAndEncodeResponse(service, rpcRequest.getMethod(),
                    rpcRequest.getParameters(), rpcRequest
                            .getSerializationPolicy(), rpcRequest.getFlags());
        } catch (IncompatibleRemoteServiceException e) {
            log(
                    "An IncompatibleRemoteServiceException was thrown while processing this call.",
                    e);
            return RPC.encodeResponseForFailure(null, e);
        }
    }

    private String getRemoteServiceComponentName(String encodedRequest) {
        ClassLoader classLoader = Thread.currentThread()
                .getContextClassLoader();

        String serviceName;
        try {
            ServerSerializationStreamReader streamReader = new ServerSerializationStreamReader(
                    classLoader, this);
            streamReader.prepareToRead(encodedRequest);
            serviceName = streamReader.readString();
        } catch (SerializationException e) {
            throw new IncompatibleRemoteServiceException(e.getMessage(), e);
        }

        Class<?> serviceClass;
        try {
            serviceClass = Class.forName(serviceName, false, classLoader);
        } catch (ClassNotFoundException e) {
            throw new IncompatibleRemoteServiceException(
                    "Could not locate requested interface '" + serviceName
                            + "' in default classloader.", e);
        }

        if (!RemoteService.class.isAssignableFrom(serviceClass)) {
            throw new IncompatibleRemoteServiceException(
                    "Blocked attempt to access interface '"
                            + serviceClass.getName().replace('$', '.')
                            + "', which doesn't extend RemoteService;"
                            + " this is either misconfiguration or a hack attempt.");
        }

        // 例えばFooServiceというクラスであれば"fooService"
        // というコンポーネント名にマッピングされ、この名前を
        // 使ってS2Containerからサービス実装がルックアップされる
        return StringUtil.decapitalize(serviceClass.getSimpleName());
    }
}

このクラスを以下のようにweb.xmlに登録しておきます。

<servlet>
    <servlet-name>s2RemoteService</servlet-name>
    <servlet-class>com.kaiseh.gwt.servlet.S2RemoteServiceServlet</servlet-class>
</servlet>
<servlet-mapping>
    <servlet-name>s2RemoteService</servlet-name>
    <url-pattern>/hellogwt/s2RemoteService</url-pattern>
</servlet-mapping>

GWTアプリのクライアント側では、全てのRPCインタフェースで、URLとして"s2RemoteService"を使うように設定します。これは@RemoteServiceRelativePathアノテーションで指定可能です。

@RemoteServiceRelativePath("s2RemoteService")
public interface CalculatorService extends RemoteService {
    int add(int a, int b);
}

上記のCalculatorServiceの例の場合、このインタフェースを実装したCalculatorServiceImplクラスを"calculatorService"というコンポーネント名でapp.diconから探せるようにしておけば、後はS2がマッピングを行ってくれます。

このようにS2とGWT RPCを連携すると、RPCインタフェースを追加するたびにweb.xmlを書き換える必要がなくなるので、開発効率が向上すると思います。

WEB+DB PRESSで『つながるJava』の連載を始めました

WEB+DB PRESS Vol.57

WEB+DB PRESS Vol.57

先週発売のWEB+DB PRESSから、『つながるJava』というタイトルで連載を始めました。毎回、注目のフレームワークやライブラリを紹介していこうと思います。初回はJavaAjaxをつなげるという趣旨で、先日のカンファレンスでも話したGWTを取り上げています。

Java Cloud Meeting Tokyo 2010: 『Google Web Toolkitのすすめ』発表資料

Java Cloud Meeting Tokyo 2010で、『Google Web Toolkitのすすめ』と題して発表を行いました。スタッフの皆さま、お疲れ様でした。

発表中に、Google PluginでGWTアプリをGAEにデプロイする予定だったのですが、Eclipseで謎のエラーが出てしまいました。そこであらかじめデプロイしておいたアプリを表示しようと思ったのですが、動揺でApp IDをど忘れしてしており、URLを間違えて404を連発という失態を演じてしまいました。ネットワークを使うデモは会場でのリハーサルが必須ですね...。

以下、発表資料です。