『プログラミングScala』は腰を据えたScalaの学習に最適
1/20発売予定のオライリージャパンの新刊、『プログラミングScala』を献本いただきました。
- 作者: Dean Wampler,Alex Payne,株式会社オージス総研オブジェクトの広場編集部
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/01/20
- メディア: 大型本
- 購入: 3人 クリック: 320回
- この商品を含むブログ (38件) を見る
この本の敷居ははっきり言って高く、『Scalaスケーラブルプログラミング』に近いレベルだと思います。その難しさは、Scalaの型システムと関数型プログラミングを正面から解説しているところから来ています。重いテーマなので後回しにしたくなりますが、この部分の理解が曖昧なままでは、結局、いつまで経ってもScalaを理解したことにならないので、本書や『Scalaスケーラブルプログラミング』のような正面突破のアプローチは正解だと思います。
『Scalaスケーラブルプログラミング』と『プログラミングScala』の比較としては、前者はScalaを設計した本人が原著者なこともあって、言語機能ごとに章がかっちり分割されているのに対し、後者は「ScalaでOOPするには?」「Scalaにおけるデザインパターンは?」のような、ユーザ視点の緩やかな章立てになっている印象を受けました(追記: 本書の原共著者のAlex Payneさんは、TwitterのバックエンドをRubyからScalaに移植したチームメンバーだそうです)。
Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)
- 作者: Martin Odersky,Lex Spoon、Bill Venners,羽生田栄一,長尾高弘
- 出版社/メーカー: インプレス
- 発売日: 2009/08/21
- メディア: 単行本
- 購入: 18人 クリック: 687回
- この商品を含むブログ (121件) を見る
内容的にももちろん素晴らしく、『Scalaスケーラブルプログラミング』と併読をおすすめしたいです。この2冊を横に置いて、プログラムを実際に打ち込みながら、じっくり学習するのが良いと思います。
追記: 原著はScala 2.7をベースにしていますが、この翻訳版は、紙面の内容が2.8と互換性の問題を持つ場合の全箇所に脚注が入っていることと、2.8の新機能を紹介する付録もあるので、2.8の環境で全く問題なく使える本だと思います。
fastutilの注意点
WEB+DB PRESS Vol.60で、「fastutilとsuxによる大規模データ処理」と題して、プリミティブコレクションライブラリのfastutilと、簡潔データ構造ライブラリのsuxを紹介する記事を書きました。
- 作者: まつもとゆきひろ,西尾泰和,山田憲晋,城戸忠之,増井俊之,羽生章洋,uupaa,ミック,塙与志夫,原悠,奥一穂,はまちや2,大沢和宏,吾郷協,浜本階生,中島拓,中島聡,矢野りん,角田直行,能登信晴,田村哲也,吉村譲,結城亜砂子,角谷信太郎,石橋秀仁,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2010/12/22
- メディア: 大型本
- 購入: 12人 クリック: 185回
- この商品を含むブログ (24件) を見る
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』の連載を始めました
- 作者: 今村謙之,遠藤正仁,浜本階生,uupaa,増井俊之,大沢和宏,伊藤直也,村瀬大輔,塙与志夫,中島拓,中島聡,角田直行,cho45,はまちや2,新里祐教,塚田翔也,ミック,関治之,れさく,加藤幹生,原悠,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2010/06/24
- メディア: 大型本
- 購入: 4人 クリック: 206回
- この商品を含むブログ (32件) を見る
先週発売のWEB+DB PRESSから、『つながるJava』というタイトルで連載を始めました。毎回、注目のフレームワークやライブラリを紹介していこうと思います。初回はJavaとAjaxをつなげるという趣旨で、先日のカンファレンスでも話した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を連発という失態を演じてしまいました。ネットワークを使うデモは会場でのリハーサルが必須ですね...。
以下、発表資料です。