2015/03/06

JJUG ナイトセミナ 「至極の Java Quiz 傑作選」 続き

このエントリーをはてなブックマークに追加

ナイトセミナの後、寺田さんにパズルの解説を blog で書かないのと聞いたら、Java Day Tokyo の準備でそれどころではないというので、代わりに寺田さんのパズルの解説をしようと思います。

資料はこちら。

 

寺田さんの問題は 2, 5, 8 問目です。

 

#2 TriTrial

問題はこちら。

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class TriTrial {
    public static void main(String... args) {
        List<Integer> fifthElement = Stream.of(1, 2, 3, 4, 5)
                                           .collect(Collectors.toList());
        
        IntStream.rangeClosed(1, 5)
                 .filter(n -> n % 3 == 0)
                 .forEach(n -> fifthElement.remove(n));
        
        fifthElement.forEach(System.out::print);
    }
}

選択肢は

  1. 1235
  2. 1345
  3. 1245
  4. それ以外

この問題では、[1, 2, 3, 4, 5] を要素に持つリストがあります。それに対し、3 で割り切れる要素を削除しようというものです。順当に考えれば、3 の 1245 になると思うわけですが、答えは 1 の 1235 です。

どうして、そうなってしまったのでしょう。

Stream API が散りばめられているので、なんとなくそこら辺がもんだいなのかと思われるかもしれませんが、違います。

とりあえず、はじめからコードをおってみましょう。

main メソッドのはじめの Stream.of メソッドは可変長引数のメソッドで、引数を要素に持つ Stream オブジェクトを生成するメソッドです。of メソッドの引数の型はジェネリクスの型パラメータで指定されるので、オートボクシングが働いて Stream<Intger> オブジェクトが生成されます。

次の collect メソッドはストリームに対する集約処理を行うメソッドですが、実際に行う集約処理は引数に指定する Collectors クラスのメソッドに依存します。ここでは toList メソッドを使用しているので、ストリームをリストに変換する処理を行います。

さて、次の IntStream クラスの rangeClosed メソッドは、引数で開始から終わりまでを指定して IntStream オブジェクトを生成するファクトリメソッドになります。同じようなメソッドに range メソッドがありますが、こちらは第 2 引数は含まないストリームを生成し、rangeClosed メソッドは第 2 引数を含むという違いがあります。

このため、生成した IntStream オブジェクトは、要素として [1, 2, 3, 4, 5] を保持します。

次の filter メソッドは引数のラムダ式の返り値が true の要素だけを残すフィルタリングのメソッドです。ここでは、3 で割ったあまりが 0 のものだけ取り出すということなので、結果として [3] だけを要素に持つ IntStream オブジェクトとなります。

問題は次の forEach メソッドに指定したラムダ式です。ここでは、fifithElement オブジェクトの remove メソッドをコールしています。

remove メソッドの引数は 3 なので、fifthElement オブジェクトの 3 が削除されてと考えるかもしれません。ところが、ここに落とし穴があるのです。

List インタフェースの remove メソッドは、2 つのオーバーロードがあります。

  • E remove(int index)
  • boolean remove(Object o)

なんとなく、オブジェクトを引数にとる remove がコールされるような気がしますが、実際には IntStream なのでラムダ式の引数の n は int 型であり、remove(int index) がコールされるのです。

インデックスだとすると、0 から始まるので要素の 4 が削除されます。

これを修正するには、明示的に n を int 型から Integer クラスに変換する必要があります。そのためには、n をキャストするか、IntStream オブジェクトを Stream<Integer> に変換する boxed メソッドを使用します。

boxed メソッドを使用すると、次のようになります。

        IntStream.rangeClosed(1, 5)
                 .filter(n -> n % 3 == 0)
                 .boxed()
                 .forEach(n -> fifthElement.remove(n));

この問題の教訓はメソッドのオーバーロードに気をつけることと、オートボクシングに気をつけるということがあります。

寺田さんの教訓は最もなのですが、櫻庭的にはもう 1 つ気をつけなくてはいけないところがあると思っています。

それはどこかというと、Stream API での副作用問題です。

Stream API を使用する時には、なるべく外部の変数にはアクセスしないようにすべきです。参照するだけであればまだしも、変数の状態を変更するようなことはなるべく避けるべきだと思います。

forEach メソッドは、Stream API の中では副作用を起こしてもしかたないメソッドの 1 つなのですが、それでもこのパズルのように、外部のリストの状態を変更するというのはちょっとやり過ぎのような気がします。

それだったら、次のように記述すればいいと思います。

public class TriTrial {
    public static void main(String... args) {
        List<Integer> fifthElement = Stream.of(1, 2, 3, 4, 5)
                                           .filter(n -> n % 3 != 0)
                                           .collect(Collectors.toList());
        
        fifthElement.forEach(System.out::print);
    }
}

この方が分かりやすいですよね。

 

さて、BGM です。

前回ちょっと書いたのですが、 Peter, Paul and Mary の All My Trial を使いました。問題では試行の意味の Trial なのですが、試練の意味の Trial をかけています。

櫻庭が PPM を聞き始めたのは、彼らのピークだった 60 年代とはかけ離れているわけです。

聞き始めたころは、60 年代でアコギ主体のアーティストと、どうしても Bob Dylan や Simon & Garfunkel などになってしまうわけです。PPM はちょっとまじめすぎて、なんとなく敬遠していた感もあります。

ほんとに PPM がいいなぁと感じられたのは、おとなになってからでしたね。コーラスはバツグンにキレイだし、3 人のテクニックがすごい。なんでこんなにコロコロとメインパートを入れ替わりながら歌えるのかほんと不思議です。ギターもむちゃくちゃうまいし。

PPM はキリスト教に関係する歌をよく歌っているのですが、この All My Trial もそのうちの一曲。この曲もほんとキレイな曲です。

 

#5 Kana Catalog

5 問目は Kana Catalog です。

問題はこちら。

import java.util.stream.IntStream;

public class KanaCatalog {
    public static void main(String... args) {
        IntStream.range('あ', 'わ')
                 .mapToObj(n -> (char)n)
                 .forEach(System.out::write);
    }
}

選択肢は

  1. あ ~ わ の表示
  2. あ ~ ゎ の表示
  3. 何も表示されない
  4. 文字化け発生

答えは 3. の 何も表示されない です。

これも Stream API の問題のように見えますが、違います。

ここでも、IntStream クラスの range メソッドを使用しています。'あ' から 'わ' までを作成しているわけですが、char 型のストリームはないので、int 型に暗黙の型変換が行われています。

次の mapToObj メソッドはプリミティブに対応した IntStream オブジェクトから Stream<T> に変換するメソッドです。ここではラムダ式の引数の int 型の変数を char 型にキャストしています。ここでは明示されていませんが、オートボクシングによって Character クラスに変換されます。

そして、最後の forEach メソッドで標準出力に出力されるわけです。

引っかかるとしたら、range メソッドが第 2 引数を含めないので、"わ" になるか "ゎ" になるかというところぐらいですね。

でも、そこではないのです。

どこかというと、write メソッドにあります。普通、こういうところでは write メソッドではなく、print メソッドか println メソッドを使いますよね。なぜ、print メソッドか println メソッドを使用するかご存じですか。

それは、print/println メソッドが最後にバッファをフラッシュするからです。ストリームやライタは通常バッファを持っており、バッファに対して書き込みを行い、ある程度まとまってから本来の出力先に対して出力します。この処理のことをフラッシュ (flush) と呼びます (トイレを流すことも flush ですね)。

write メソッドでも、条件が合致すれば flush するのですが、ここでコールされる write(int b) は改行文字、もしくはオートフラッシュモードにないかぎりフラッシュをしません。

これに対し、print/println メソッドでは毎回フラッシュを行うという違いがあります。

この問題の教訓は

  • 慣れ親しんだ API でも、必ず Javadoc をチェックしよう

ということです。

 

さて、BGM です。

とりあえず、 Catalog を扱った曲を探してみたのですが、手持ちの CD にはない ><

しかたないので、Catalog といえば Book だろうということで、Miles Davis Quintet の I Could Write a Book です。

この曲は Miles の Relaxin' に入っています。Relaxin' を含めた Streamin', Workin', Cookin' の 4 枚のアルバムはマラソンアルバムと呼ばれて、2 日間でアルバム 4 枚分を録音してしまったというアルバムなのです。レーベルを移籍に伴い、こういうことになったわけですが、この 4 枚のアルバムはほんとにカッコいい。Miles のベストといっても過言ではないと思います。

この頃の Miles バンドのメンバはサックスが John Coltrane、ピアノが Red Garland、ベースが Paul Chambers、ドラムが Philly Joe Jones です。ほんとすごいメンバなわけです。

コロコロと転がるような Garland のピアノで始まるこの曲も、Miles のミュートが冴え渡っています。Miles はどちらかというと暗いペットを吹くのですが、この曲のようにアップテンポで陽気な曲もいいものです。

 

#8 Superstar

8 問目は時間がなくて、セミナではできなかったのですが、Superstar という問題です。

import java.time.Year;

public class Superstar {
    public static final Superstar superstar = new Superstar();
    
    private static final int BIRTH_YEAR = Year.of(-4).getValue();
    private static final int THIS_YEAR = Year.now().getValue();
    
    private final int age;
    
    private Superstar(){
        age = THIS_YEAR - BIRTH_YEAR;
    }
    
    public int getAge() {
        return age;
    }
    
    public static void main(String... args) {
        int age = superstar.getAge();
        
        System.out.println("Superstar: " + age + " years old.");
    }
}

選択肢は次の通り。

  1. Superstar: 2019 years old.
  2. Superstar: 2015 years old.
  3. 例外発生
  4. それ以外

答えは 4 のそれ以外です。実際に出力されるのは "Superstar: 0 years old." になります。なんでだか全然分からないですよね。

この問題は、JVM が起動する時の、手順を知らないとちょっと難しいかもしれません。

JVM が起動して、main メソッドを実行するまでの手順は 4 つの段階に分かれます。

  1. JVM 起動
  2. クラスロード
  3. リンク
  4. 初期化

JVM の起動はその名の通り、JVM を起動するわけです。そして、必要とするクラスをロードするクラスロードを行います。

この時点ではロードしただけで、クラスを使えるところまではいきません。

その後、リンクを行います。リンクではベリフィケーション、準備、解決の 3 つの処理を行います。

ベリフィケーションはクラスファイルが正しいかどうかをチェックする処理です。

そして、準備で static フィールドの初期化を行います。ただし、クラス間の関係は次の解決で決められるので、クラスのメソッドをコールすることはできません。したがって、オブジェクトであれば null が代入されます。これは final な変数であったとしても同じです。

同様に数値を扱うプリミティブ型では 0 になります。

次の解決でクラス間の関係を構築したり、定数プールの解決を行います。

ここでやっと Java のコードを実行する準備が整います。

この時点で、superstar 変数は null、BIRTH_UYEAR と THIS_YEAR は 0 になっています。

そして、初期化で static フィールドの初期化と static イニシャライザが実行されます。これは記述順に行われるので、まず superstar の初期化が行われます。

superstar の右辺は new Superstar() なので、コンストラクタがコールされます。

コンストラクタでは THIS_YEAR と BIRTH_YEAR の引き算が行われるのですが、この時点でもまだ THIS_YEAR と BIRTH_YEAR の値は 0 なのです。

つまり、age は 0 になります。

superstar が初期化された後、BIRTH_YEAR、THIS_YEAR の順に初期化されます。

しかし、age が更新されることはなく、その値は 0 のままです。

このため、main メソッドで superstar.getAge() が返す値は 0 になってしまうわけです。

これを解消するには、static フィールドの記述順序を変更して、superstar を BIRHT_YEAR、THIS_YEAR の後に書けば OK。

でも、こんなことが起こるなんて、気がつかないですよね。だからこそ、気をつけて欲しいわけです。

 

さて、この問題の BGM ですが、ゴスペルの名曲、John The Revelator を使いました。

問題を見れば分かると思うのですが、Superstar といっているのはあの人のことです。

ほんとはミュージカルの Jesus Christ Superstar の曲を使いたかったのですが、さすがに CD を持ってなかったのでした。

キリスト教に関する曲だけはいっぱいあるので、その中のどれかにしようと思ったわけです。で、John The Revelator。

この曲はいろいろな人が歌っていますが、ここで使うつもりだったのは映画 Blues Brothers 2000 の Sam Moore のバージョン。Sam Moore といえば、Sam & Dave の Sam。

Sam Moore といえば高音でのシャウト。この曲でもそれが存分に発揮されてます。映画の中では、Blues Brothers の最後のメンバがこの曲で解脱 (?) してしまうわけです。


この Java Puzzlers の資料がとうとう 1 万 View に達してしまいました。こんな短い期間で 1 万に達したのは初めてです。

それだけ、注目されたということなのでしょう。

そうすると、やっぱり次回もということを考えてもいいかもしれません。まぁ、そんなにすぐにやるわけではないですが、頃合いを見て、考えようと思います。

2015/02/27

JJUG ナイトセミナ 「至極の Java Quiz 傑作選」

このエントリーをはてなブックマークに追加

2 月 25 日に JJUG ナイトセミナ に寺田さん、宮川さんと一緒に登壇しました。ナイトセミナに登壇するのは半年ぶりです。

ちょうど日経ソフトウエアで連載していた至極の Java クイズが終了したこともあり、傑作選を行いました。傑作選とはいいつつも、そのままをクイズに出したら連載を読んでいる方が有利になってしまうので、すべてアレンジしてあります。また、1/3 は新作です。

資料はこちら。

 

先におわびをしておきます。

最近、オラクルの会場のプロジェクタが変わったのです。前回、オラクルで話した時に資料を 1024×768 で作成したのですが、その時に横に黒帯が出力されていたので気がついたのですが。

そこで、プロジェクタの解像度を問い合わせたところ、機種は Panasonic PT-DZ770S で、解像度が 1920×1200 だということでした。いわゆる HD ということです。

それを盲目的に信じた私が行けなかったのですが、会場に着いてみたら、いわゆるアナログ RGB のケーブルしかありません。そういえば、以前から HDMI はなかったことに気がついていればよかったのですが....

結局、1920×1200 は出力できず、可能なのは 1360×768 まで!!

PowerPoint を使っている人には全然問題ないかもしれませんが、JavaFX で資料を作っているこちらには大問題。キクタローさんやいがぴょんさんが講演している間に、なんとか改造して出力できるようになりました。

でも、当初の 0.63 倍にスケールダウンしているため、当初思っていたよりもフォントが小さく表示されてしまいました。ほんと見づらくて、すみませんでした。

でも、Swing で作っていたら改造はムリだったろうなぁ... ほんと、JavaFX でよかった。

 

そんなこんなで、かなり焦った状況でセッションを始めてしまったので、始めはグダグダでしたね。本当は、Java Puzzlers って何なのか、なぜ寺田さんと私は青いつなぎを着ているのか、日経ソフトの Java クイズとは、などを説明する予定だったのですが...

寺田さんが、そこらへん補ってくれればよかったのですが、みんなで焦ってしまったので、まぁしかたありません。

ちなみに、Dukelele が 2 台というのは、本邦初だし、もうやらないだろうなと思います。

 

せかっくなので、セッションでははしょってしまったパズルの解説をここでやろうと思います。私が出題したのは、1, 4, 7 問目です。

 

#1 Vertigo

ちなみに Vertigo というのはめまいのことです。

問題はこちら。

import java.util.function.Supplier;

public class Vertigo {
    static class String {
        private Supplier direct;
        
        public String(java.lang.String director) {
            this.direct = () -> director;
        }
        
        public Supplier direct() {
            return direct;
        }
    }
    
    public static void main(String... args) {
        String alf = new String("Hitchcock");
        System.out.println(alf.direct().get());
    }
}

選択肢は

  1. Hitchcock
  2. 何も表示されない
  3. コンパイルエラー
  4. それ以外

答えは 4. のそれ以外です。

まず、気になると思うのが、String クラスを作れるのかどうかという点。

答えはできます。String クラスでも System クラスでもパッケージが異なれば作れます。

次に怪しいのが、main メソッドの String alf = new String("Hitchcock"); で使われている String クラスが、どの String クラスを指しているかという点。

これは、内部クラスの String クラスを指しています。

でも、それだけだと、1. の Hitchcock が出力されるのでは、と思いますよね。

もう 1 つ忘れてはいけない点が、main メソッドの引数の String クラスです。

この String クラスも内部クラスの String クラスを指しています。

でも、main メソッドの引数に使われるのは、java.lang.String クラスではないとダメですよね。なので、このプログラムを実行しようとすると、「メイン・メソッドが Vertigo で見つかりません」というエラーメッセージが表示されて、プログラムは動きません。

つまり、答えは 4. のそれ以外です。

さて、これをどうやれば修正できるかですが、一番単純なのは main メソッドを main(java.lang.String... args) のようにフルパッケージで指定することです。

しかし、これは本質的な答えではありません。

重要なのは内部クラスの String クラスは、その名前でいいのかどうかということです。

String クラスに direct メソッドなんて変な感じですよね。また、コンストラクタの引数名が director というのも。ここは String ではなくて、Movie というクラスにしてしまえば、しっくりきます。

つまり、クラス名はそのクラスの責務をちゃんと表す名前にする必要があるわけです。

ということで、この問題の教訓。

  • 標準ライブラリと同じ名前のクラス名は避ける
    • 特に java.lang パッケージのクラス名との重複は避ける
  • クラス名はとても重要
    • 責務に応じた名前にする

 

ところで、Vertigo ははじめに書いたように「めまい」のことなのですが、めまいと Hitchcock (アルフレッド ヒッチコック) といえば、映画の「めまい」ですよね。映画の「めまい」の中ではヒロインが 1 人 2 役をやっていて、主役の刑事を惑わせるというストーリーなんです。最後はそれがばれて、ヒロインの人は死んじゃうのですが...

ここでも、2 つの String クラスが出てきて、惑わせてくれるわけでした。

BGM もめまいのサントラを使いたかったのですが、さすがにそれは持っていないので、手持ちの CD を探したらありました。

U2 の Vertigo。

この曲、iPod の CM にも使われてましたね。

 

#4 Take Five

4 問目は Take Five です。

問題はこちら。

public class TakeFive {
    public static void main(String... args) {
        int beat = 0;
        long count = 0;
        
        for (; beat < Integer.MAX_VALUE; beat += 5) {
            count++;
        }
        
        if (beat == count * 5) {
            System.out.println("Break");
        } else {
            System.out.println("Keep Rhythm");
        }
        
        System.out.println(beat);
        System.out.println(count);
    }
}

選択肢は

  1. Break
  2. Keep Rhythm
  3. 例外発生
  4. それ以外

答えは 2. の Keep Rhythm です。

この問題はプリミティブ型の演算で避けることのできない、オーバーフローの問題です。

問題としては、for 文で beat を 5 ずつ増加させていき、それといっしょに count もインクリメントしています。for 文の終了条件は beat が Integer.MAX_VALUE 以上ということ。

beat は 0 から始まって、5、10 と値が増えていきます。普通に考えれば、beat == count * 5 は true ですよね。

難しいのは Integer.MAX_VALUE 付近の話。

Integer.MAX_VALUE の値は 2,147,483,647。16 進数で表すと、0x7FFF_FFFF です。ここにもっとも近い 5 の倍数は 2,147,483,645、16 進数だと 0x7FFF_FFFD です。

この値に 5 を足すと、2,147,483,650 にはなりません!

16 進数で考えると、5 を足した数は 0x8000_0002 になります。ここで思い出してほしいのはプリミティブ型を 2 進数で表した時の最上位ビットは符号を表していることです。

0x7FFF_FFFD の最上位ビットは 0 ですが、0x8000_0002 の最上位ビットは 1 になります。つまり、0x8000_0002 は負の数を表していることになります。10 進数であらわすと、-2,147,483,646 になってしまいます。

これが桁あふれ、つまりオーバーフロー、正確には整数オーバーフローです。

オーバーフローして負の数になってしまったのですから、Integer.MAX_VALUE より小さい値です。なので、まだ for 文は回り続けます。

次に、Integer.MAX_VALUE に再接近するのは beat が 2,147,483,644、そして 2,145,483 です。ここでまたオーバーフローして、ループを繰り返し、ちょうど beat が Integer.MAX_VALUE になるわけです。

この時の、count の値は 3,006,477,107。count は long 型なので、この値でも表すことができます。ちなみに、3,006,477,107 * 5 / Integer.MAX_VALUE は 7 になります。

Java は整数オーバーフローは検出できないので、こんなことになってしまうわけです。

では、どうやって直せばいいかというと、for 文の終了条件を beat < Integer.MAX_VALUE から beat < Integer.MAX_VALUE - 5 にすれば OK。これだと、5 を足しても MAX_VALUE を超えないので、オーバーフローにはなりません。

しかし、本質的に直すのであれば、変数の値の範囲を考えて beat 変数の型を long 型にする、もしくは BigInteger クラスにすることです。

この問題ではオーバーフローを扱いましたが、同様に小数点数におけるアンダーフローの問題もあります。どちらも Java では避けて通れないので、十分に気をつけましょう。

ということで、この問題の教訓。

  • オーバーフロー、アンダーフローに注意する
  • 変数の値の範囲から適切な型を選択する
  • 範囲が限定できないのであれば、BigDecimal/BigInteger の使用も検討する

 

ところで、この問題の Take Five ですが、英語の意味は 5 分休憩です。でも、やっぱり Dave Brubeck の Take Five なわけです。

この曲は 5 拍子。なので、5 で割り切れるところで Break、その他で Keep Rhythm としてます。

5 拍子とはいっても、実際には 3 拍子 + 2 拍子的なリズムですね。だから変拍子にも関わらず、聞いていると心地よいのかもしれません。

 

#7 Ants and Grasshopper

最後の問題は Ants and Grasshopper です。イソップのアリとキリギリスは Ant and Grasshopper ですが、ここでは Ant ではなくて Ants です。

この問題は普通のシーケンシャルなストリームとパラレルストリームのベンチマークです。

セッションでは説明したのですが、こういうベンチマークで 1 回だけの試行で性能を云々することはしません。通常は事前にウォーミングアップした後に、複数回の試行を行うようにします。

ということで、セッションで示したものを書き直したのが、次のプログラムです。

import java.util.Random;

public class AntsAndGrasshopper {

    static long grasshopperWork() {
        return new Random().longs(1_000_000L)
                           .sum();
    }

    static long antsWork() {
        return new Random().longs(1_000_000L)
                           .parallel()
                           .sum();
    }

    public static void main(String... args) {
        // ウォーミングアップ
        for (int i = 0; i < 50; i++) {
            grasshopperWork();
        }

        long s = System.nanoTime();
        for (int i = 0; i < 50; i++) {
            grasshopperWork();
        }
        long ghTime = System.nanoTime() - s;

        // ウォーミングアップ
        for (int i = 0; i < 50; i++) {
            antsWork();
        }

        s = System.nanoTime();
        for (int i = 0; i < 50; i++) {
            antsWork();
        }
        long atTime = System.nanoTime() - s;

        System.out.println("Ants work faster: " + ((ghTime - atTime) > 0));
    }
}

選択肢は

  1. Ants work faster: true
  2. Ants work faster: false
  3. 場合による
  4. それ以外

この問題はもちろん、マルチコアの CPU で実行することを想定しています。

grasshopperWork メソッドと ants メソッドで使用されている、Random クラスの longs メソッドですが、引数で与えた個数の long 型の乱数列の LongStream オブジェクトを生成するメソッドです。Random クラスには longs メソッド以外にも、ints メソッド、doubles メソッドが追加されています。

この乱数列の合計を計算するのが、grasshopperWork メソッドと antsWork メソッドのわけです。両者の違いは grasshopperWork メソッドがシーケンシャルなストリームを使用し、antsWork メソッドがパラレルストリームを使用しているところです。

ここでは、ウォーミングアップに 50 回それぞれのメソッドをコールし、その後、再び 50 回コールした合計の時間で比較しています。

普通だったら、当然パラレルストリームが速いわけですから、1. の Ants work faster: true になるはずです。

ところが、実際には違います。

パラレルストリームの方が遅くなるのです。実際にやってみると、ビックリするぐらいパラレルストリームの方が遅くなりますよ。

この理由を考えてみましょう。もちろん、怪しいのは Random クラスですね。

Random クラスの中で、乱数を生成しているのは next メソッドです。

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

乱数列を生成するには、種 (seed) が必要なのはご存じでしょうか。デフォルトコンストラクタで Random オブジェクトを生成すると、時間を基に seed が生成されます。

この seed の型は AtomicLong クラスです。つまり、Random クラスはスレッドセーフで複数のスレッドからアクセスすることが可能です。

そして、seed から新しい nextseed を生成しています。そして、青字部分の compareAndSet メソッドで、seed が変更されていないかどうかをチェックし、変更されていなければ新しい nextseed に更新しています。

つまり、他のスレッドがアクセスして、seed を変更してしまうと、この while ループがずっと回り続けるわけです。

そして、残念なことにこのループは非常に多くの回数ループしてしまいます。

実をいうと、AtomicLong クラスは複数のスレッドから頻繁に値が更新されることを想定していません。頻繁に値が更新するような場合は、Java SE 8 で導入された LongAccumulator クラスを使用します。

LongAccumulator クラスの Javadoc には以下のようなことが書いてあります。

きめ細かい同期制御のためではなく統計収集などの目的に使用される共通の値が、複数のスレッドによって更新される場合、通常は AtomicLong よりもこのクラスをお薦めします。更新の競合が少ないときは、2つのクラスの特徴は似ています。競合が多いときは、期待されるスループットはこのクラスの方がかなり高くなります。ただし、容量消費も多くなります。

日本語が分かりにくいですが、ようするに更新を多くする場合は LongAccumulator クラスを使えということです。ただし、LongAccumulator クラスはヒープも多く喰います。

つまり、パラレルストリームのように複数のストリームでアクセスすると、頻繁に競合が発生しパフォーマンスが劣化してしまうわけです。

このようにパラレルストリームの処理中に、外部の変数にアクセスすると、とたんにパフォーマンスが劣化します。イミュタブルのオブジェクトであればまだしも、状態を保持しているオブジェクトはダメです。

シンクロナイズしていないオブジェクトはもちろんダメですが、シンクロナイズしていても競合が頻繁に発生するので、パフォーマンスは劣化してしまいます。

Random クラスだけを見ていると気がつかないかもしれませんが、Random クラスは状態 (種のことです) を保持していることを考えれば、パラレルストリームではパフォーマンスが劣化することが予想できます。

このようにパラレルストリームにはやってはいけないことがいろいろあります。代表的なものを以下に列挙します。

  1. ストリームの要素数が少ないのはだめ。少なくとも 106 は要素がないと、効果が出ない
  2. 外部変数へのアクセス
  3. 順序に依存した処理
  4. 無限ストリーム
  5. 入出力

まず、1. の要素数です。

パラレルストリームはパラレル処理を行うため、シーケンシャルに実行することよりもオーバーヘッドがあります。このため、要素数が少ないと、オーバーヘッドの分だけパフォーマンスが上がりません。

私が試したケースからいうと、Java SE 8 の実装だと、要素が 106 以上ないと効果が出ませんでした。もっと、コア数が多いような場合には異なるかもしれませんし、今後はもっと少ない要素で効果が出るような実装になるかもしれません。

少なくとも、パラレルストリームのオーバーヘッドは少なくはないということは注意した方がいいと思います。

次の 2. が今回のケースですね。実際には、ストリームに処理させるラムダ式の中から、外部にアクセスしてしまうというケースが多いと思います。

3. は当然ですね。せっかくパラレルで処理しているのですから、順序に依存してしまうと意味がなくなってしまいます。

4. の無限ストリームは意外に思われるかもしれません。

無限ストリームはストリームの長さが明示的に決まらないストリームのことで、ストリームを iterate メソッドや generate メソッドで生成した場合に相当します。

なぜ、無限ストリームはパラレルだとパフォーマンスが落ちるのかは、パラレルストリームの処理手法を理解する必要があります。

パラレルストリームの処理は、Java SE 7 で導入された Fork/Join Framwork を使用して行われています。

Fork/Join Framework はタスクを細かくするために、分割統治法を使用します。分割統治法は、すべてのタスクをまず半分に分割します。そして、半分に分割したタスクをそれぞれ半分に分割します。このように半分に分割することを繰り返して、タスクを細かい粒度にしていきます。

ストリームの場合、タスクを分割するのではなく、タスクで処理する要素を分割していきます。つまり、ストリームの要素を半分に分割していくのです。この分割は要素が 1 つになるまで繰り返され、1 つになったらタスク処理します (この場合、ラムダ式で記述された処理)。そして、それを再び組み合わせていって、最終的な結果を得ています。

ところが、無限ストリームの場合、要素数が分からないので、要素の半分が分かりません。つまり、どこで分割していいのかが分からなくなってしまうのです。このため、分割が非効率になり、結果的にパフォーマンスが劣化してしまうわけです。

最後の入出力は Files クラスの lines メソッドや BufferedReader クラスの lines クラスに相当します。ファイルの読み込みや通信は CPU の処理スピードに比べると、遥かに遅いです。I/O 待ちで CPU が遊んでしまったら、何のためのパラレル処理なのか分からなくなってしまいますね。

この辺りの議論は、 ITpro の 詳説 Java SE 8 第 16 回 に解説したので、こちらもご参照ください。

さて、この問題ですが、どのように直せばいいでしょうか。

問題は競合を起こしている部分なのですから、その処理はパラレルで行わず、シーケンシャルに行えばいいのです。つまり事前に乱数列をシーケンシャルに生成しておきます。

    static long antsWork() {
        // 事前に乱数列を生成しておく
        long[] rands = new Random().longs(1_000_000).toArray();
 
        return Arrays.stream(rands).parallel().sum();
    }

とはいえ、この方法だと乱数列の rands を生成する方に時間がかかってしまうので、パラレルストリームの性能を測るという意味ではあまり適切ではありません。

乱数列は別に生成しておいて、それをメソッドの引数にしておく方が適切ですね。

    static long antsWork(long[] rands) {
        return Arrays.stream(rands).parallel().sum();
    }

もちろん、同じように grasshopperWork メソッドも変更します。これで実行すると、antsWork メソッドの方が処理時間が短くなるはずです。

ということで、この問題の教訓

  • パラレルストリームは落とし穴も多い
  • 動作原理を理解して、パフォーマンスを向上させる
  • 関数を使った考え方を理解する

 

さて、この問題の BGM ですが、Dave Matthews Band の Ants Marching です。

Dave Matthews は結構 CD を持っているつもりだったのですが、この曲が入った Under the Table and Dreaming は持ってませんでした ><

しかたないので、この曲だけライブ盤を使用しました。ライブの拍手が入っていると、そこで拍手強制しているみたいでイヤなのですが、しかたありません。まぁ、それに気づいた人はいなかったようでしたけど。


他の問題は、出題してくれた本人が解説してくれるでしょう。してなかったら、頃合いを見て、解説したいと思います。

なので、使用した BGM だけ。

2 問目は TriTrial。

問題では試行の意味の Trial なのですが、試練の意味の Trial をかけて、Peter, Paul and Mary の All My Trial を使いました。

3 問目は Answer to Everything。

この問題のタイトルは銀河ヒッチハイクガイドに引っかけてあります。問題の中にも 42 が出てきますし。ということで、映画の銀河ヒッチハイクガイドで使われていた、So Long and Thanks for All the Fish を使っています。この曲、映画では一番始めに使われるのですが、とても印象的でしたね。

5 問目は Kana Catalog。

この問題の BGM が一番困ったのでした。Catalog を扱った曲なんか持っていないし...

しかたないので、Catalog といえば Book だろうということで、Miles Davis の I Could Write a Book です。

この曲は Miles のマラソンアルバムの Relaxin' に入っているのですが、櫻庭はこの頃の Miles が一番好きなわけです。

6 問目は Odds and Sods。

この曲は外してしまいました ><

Odds and Sods の意味は「がらくた」です。だとしたら、グランジロックだろうということで、グランジの代表曲といってもいい、Nirvana の Smells Like Team Spirit にしたわけです。

ところが、当日判明したのが、このタイトル The Who のアルバムが由来だったのです。確かに宮川さんは 60 年代のブリティッシュロックが好きだったなぁ。

でも、さすがにこのアルバムは持ってませんでした ><

8 問目と 9 問目はセッションでは使わなかったのですが、使用する予定だったの曲を紹介しておきます。

8 問目は Superstar。

問題を見れば分かると思うのですが、Superstar といっているのはあの人のことです。ということで、ゴスペルの名曲、John The Revelator を使いました。

John The Revelator はいろいろな人が歌っていますが、ここで用意したのは、映画の Blues Brothers 2000 の Sam Moore のバージョン。Sam Moore といえば、Sam & Dave の Sam。パワフルです。

9 問目は Metamorphoses

最後は Metamorphose といえばやっぱり蝶でしょう、ということで Alicia Keys の Butterflyz です。これはとってもキレイな曲。Alicia のピアノがいいですね。


なぜか、よく分からないのですが、この Java Quiz とても反響が大きく、ビックリしています。

はてブのホットエントリ入りしていたり、Slideshare の view 数がかつてないほど急激に増えていたりで、ほんとビックリです。

問題を作るのはとっても大変なのですが、もし需要があれば、また寺田さんと一緒に企画してみようと思います。

2015/02/06

富山合同勉強会 .NET & Java

このエントリーをはてなブックマークに追加

1 月 30 日に富山で開催された .NET と Java の合同勉強会 に参加してきました。

毎冬、食べもの駆動で富山にいってますが、.NET の勉強会と合同なのは初めてです。同じ日に、同じ建物でやっているということはあったんですけどね。

しかも、今回は合宿形式で温泉!

でも、櫻庭はそれを気づかずに、富山市内のホテルを予約してしまったのでした ><

参加人数は .NET : Java = 3 : 1 ぐらい。もっと Java 勢にがんばってもらわないと! でも、このぐらいの人数だと、参加者との距離が近いのでツッコミもしやすいし、議論できたりもするのでいいですね。

さて、櫻庭は Project Valhalla と Project Panama の話をしてきました。資料はこちら。

 

 

Project Valhalla と Project Panama は Java SE 10 に入るかもしれない機能です。両方とも VM レベルのパフォーマンス向上などを目的にしたプロジェクトです。

でも、なんでそういう機能が必要なのかというところをまず話しました。

CPU のパフォーマンスが向上しない壁があって、電力 (熱)、ILP (Instruction level parallelism)、メモリアクセス、光速 (配線長) の 4 つです。

特に、メモリアクセスがネックになっていることが多くあります。CPU のパフォーマンス向上に比べると、メモリアクセスのスピードの伸びは低いので、スピードのギャップがどんどん広がっています。

かつて、Brian Goetz が JavaOne のセッションで Memory is the New Disk と言っていたのが、櫻庭にはとても衝撃的でした。

じゃあ、遅いメモリアクセスをしないようにするにはどうするのかというと、キャッシュメモリです。今の CPU はだいたい L1, L2, L3 の 3 段階のキャッシュメモリが備わっています。

L1 へのアクセスは 3 クロックぐらい、L2 が 15 クロックぐらいだそうです。それに対してメインメモリへのアクセスは 200 クロック程度。以下に遅いかが分かります。

つまり、メインメモリにアクセスする状況をなるべく減らすことがキモになります。具体的にはキャッシュミスを如何に減らすかということです。

では、Java ではどうなのという答えの 1 つが、Project Valhalla と Project Panama になるわけです。

Project Valhalla は主に以下の 3 つの仕様について議論されています。

  • ValueType
  • Specialization
  • VarHandle

まず、ValueType ですが、これはプリミティブ型以上、レファレンス型未満とでもいえばいいような型です。C の構造型のようなものとでもいえばいいかもしれません。しかも、イミュタブルに限定されます。

で、ValueType を使う利点は何かというと... たとえば ValueType の配列を考えてみましょう。リファレンス型だと配列にはリファレンスが保持され、そ参照先のオブジェクトはヒープのあちこちに散らばっています。

配列といえば、まとめて扱うことが多いわけですからなるべくまとめてキャッシュにおいておきたいわけですが、オブジェクトがヒープに散らばっているとまとめてキャッシュにおくということが難しくなります。

で、ValueType を使用すると、配列の中に ValueType のフィールドが展開されます。なので、キャッシュにのせやすいわけです。

ValueType の使用法としては、複素数であるとか、long より大きい数値を扱う場合、固定小数点数、タプルなどいろいろあると思います。特にタプルが実現できそうなのはいいですね。

このように ValueType を使用するとプリミティブと同じようにオブジェクトを扱うことができます。たとえば、OptionalInt クラスなんて ValueType で置き換えられますよね。

でも、OptionalInt クラスなんてほんとは使いたくなくて、Optional クラスで十分だと思いませんか。なんでこんなクラスがあるかというと、ジェネリクスの型パラメータとしてプリミティブ型を指定できないからです。

いろいろと過去の経緯や、互換性を重視して今のようにプリミティブ型を使えなくなっています。

これに対して、プリミティブ型を型パラメータとして使えるようにしようというのが、Specialization です。

今のジェネリクスの実装方法はイレージャ方式と呼ばれていますが、これとは違う方法でプリミティブ型を扱えるようにするということです。

これを使えば、IntStream だとか、IntFunction だとか、OptionalInt なんてインタフェース/クラス群は黒歴史として闇に葬り去られそうですw プリミティブ型のラッパークラスもほとんど必要なくなりますね。

まぁ、Specialization にはいろいろと問題も山積みなので、実現するのは大変だと思いますけど。

ちなみに、セッションではほとんど触れなかったのですが、VarHandle は volatile を拡張するためのものです。

 

さて、次の Project Panama です。Project Panama も 3 つの仕様が議論されています。

  • Array 2.0
  • JNR/FFI
  • Data Layout Control

Data Layout Control に関してはあまり公開されている資料がなくて、話せることがないのですが....

Array 2.0 はその名の通り配列をバージョンアップしましょうという仕様です。その中には多次元配列も含まれています。今の Java の 2 次元配列は正確には 2 次元配列ではなくて、単に配列の配列になっています。でも、これだとやっぱりキャッシュにのりにくいんですよね。

それに対して Panama が導入されれば、ちゃんとした 2 次元配列を使うことができるようになります。2 次元配列使いまくりの画像処理なんかはすごい恩恵があるはず。後は、行列計算とか。

JNR はネイティブコードを呼び出すための API です。ネイティブコードを呼び出すには JNI を使ってますけど、これがまた使いにくいし、パフォーマンスもよくない。JNA というのもありますけど、JNA は使いやすいけど、パフォーマンスはイマイチ。

ということで、JRuby の Charles Nutter が中心になって進めているのが JNR (Java Native Runtime) です。

JNR の基板となっているのが、JFFI です。FFI は Foreign Function Interface のことで、一般的な言葉。Java 版の FFI ということで JFFI です。

JNR は JNI と同じようにネイティブコードをコールするだけではなく、Posix 準拠の API を提供していたり、UNIX Socket をそのまま使えたりと、多機能。しかも、パフォーマンスもいいのです。

JNR はもう実装も結構進んでいるので、もしかしたら JNR だけ取り出して Java SE 9 に入れるということもあるかもしれません。

 

ということで、ちょっと未来の Java の話をしてきたわけなのですが、ここらへんの問題って .NET/C# だともう織り込み済みだったりするんですよね。Java が停滞していた時に、C# などはどんどん進化していたので、がんばって Java も追いつかないと。

最後に、参考資料を上げておきます。