こんにちは、アドベントカレンダーにはpicoCTFかSECCON CTFのwriteupを書こうと思っていたけど思いの外writeupが書けるような問題を解けなかったので急遽ネタを変更した18のmikitです。

さて、題名にもある通り、今回はJavaで競技プログラミングをしている人に向けたStream APIの使い方です。Stream APIというのは、Java8でlambda式の導入に伴い標準ライブラリに追加された新機能です。名前的に紛らわしいのですが、OutputStreamといったIO関連のAPIは今回の記事とは無関係です。AtCoderにおいて利用できるJavaバージョンにはJava7とJava8がありますが、この二者の最も大きな差異がこのlambda&Stream APIの有無になるかと思います。
Java7とJava8が選べるsubmission画面
今回の記事では、Javaは使った事のあるもののStream APIを競技プログラミングで使ったことはないという層を対象として、競技プログラミングで使えるStream APIの活用法を(だいぶ下の方で)ご紹介したいと思います。実はStream APIはJavaのエッセンスが詰まっているような機能で、これをマスターすれば普段競技プログラミングでは得られないようなJavaの機能(クラス, インターフェース, lambda, メソッド参照)を扱えるようになるかと思います。当記事ではそんなStream APIを使いこなすために順序で勉強を進めれば良いかの参考とできるよう、簡単に前提となる知識の説明も挟みつつStream APIの紹介をしたいと思います。多分ここの説明だけじゃクラスとかインターフェースとかの話は完全には理解できないので適宜他のサイトもみると良いと思います(多分30分とかで習得できる内容ではない)。

lambdaってなんだろう

Stream APIを取り扱う前に、lambda(ラムダ)式の概念をさらっと紹介しておきましょう。

既にlambdaは知っているぞ😡
オブジェクト指向よくわからんけどとりあえず便利なStream API使いたいぞ🤩
といった人は飛ばしていただいても構いません。

オブジェクト指向の世界

知っている方が多いとは思いますが、Javaはオブジェクト指向というプログラミングパラダイムを採用している言語です。そのため、様々な対象を「オブジェクト」として表現し、プログラムをオブジェクトの集合として記述することになります。オブジェクト指向の紹介としてよく出てくるのは以下のようなコードでしょうか。

public class Person {
    private final String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public void incrementAge() {
        this.age++;
    }
}

この例では、見ての通り個人を表すクラスを定義し、それに対して年齢をインクリメントするメソッドを定義しています。このように、物理的な「物」をクラスとして表現するというのはそれなりに直感的でわかりやすいのではないでしょうか。しかしながら、オブジェクト指向はそれだけに留まらず、抽象的な一連の処理の塊をもオブジェクトとして表現しようとします。Java競技プログラミングをしている方ならば一度は見たことがあるScannerクラスなどがそれに該当します。Scannerクラスは現実世界の物に対応しているわけではなく、与えられたバイト列の入力から文字列や整数を取り出すという処理を纏めたクラスになっています。このように、オブジェクト指向の世界では全てをオブジェクトにしていこう、という流れが存在しています。

無名クラスの時代

さて、オブジェクト指向では色んな対象をオブジェクトにしたい、という要求があることはおわかり頂けたと思います。しかしながら、Java7以前の時代にはオブジェクトとして表現しにくい対象が身近なところに存在しました。それがメソッドです。Javaにおけるメソッドというのは、JavaScriptにおける関数とは異なり、オブジェクトではありません（正確にはjava.lang.reflect.Methodというクラスは存在したのですが、これは変態さんが使うものであって一般人は使うものではありません）。メソッドをオブジェクトにする、というと感覚的に理解し難いように思えますが、例えば以下のようなシチュエーションがあり得ます。

Stringが格納されているList<String> list;を文字列の長さ順にソートしたいのだが、Collections.sort(list);の呼び出しでは辞書順によるソートになってしまう。文字列の長さに基づいて大小比較するメソッドint compare(String s1, String s2);は用意できたのだが、メソッドはオブジェクトではないのでCollections#sortの呼び出しの引数として指定することはできない。
どうにかしてメソッドgetLengthを値としてCollections#sortの引数に渡すことはできないだろうか?

ご存知の方もいるかもしれませんが、実はCollections#sortはsort(List<T>)の他にもsort(List<T>,Comparator<? super T>)という呼び出し方ができます。このようにメソッドの引数に対して、ある処理の流れ(関数)を渡すことを高階関数と呼んだりします。高階関数の実現のために、2番目の引数に出現したComparator<? super T>を"無名クラス"で実装するというのが、java7時代のソリューションでした。

Comparatorの実装の一部を覗いてみましょう。

public interface Comparator<T> {
    int compare(T o1, T o2);
}

まず着目すべき点はこれがクラスではなくインターフェースであるという点です。インターフェースは実装を持ちません。インターフェースはあるクラスが実装するべき機能を定義したもので、どのように実装するかといった情報は含んでいないということです。Collections#sortがこのComparatorを引数に取っているという事は、何らかの手段でComparatorの実装をしてからそのインスタンスを渡して下さいね、という要求になっているわけです。そして、そのComparatorの実装によってソートされる順序が変わってくるという仕組みになっています。

さて、インターフェースの実装をする例を下に挙げます。

public class MyComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
}

これはインターフェースComparator<String>を実装するMyComparatorを実装しています。ちゃんとComparator<String>の要求するint compare(String s1, String s2);に対して実装を与えていますね。このクラスの新規インスタンスをnewを用いて作成する事で、Collections#sortに対してソートの方法を指定することができるというわけです。

Collections.sort(list, new MyComparator());

これが最も愚直な「メソッドをオブジェクトに変換する方法」です。しかし、値としてメソッドを渡したかっただけなのにクラスを作成しないといけないというのはあり得ん面倒ですね。このように一箇所でしか利用していないインターフェースに対する実装というものは、「無名クラス」で省略して記述することが可能です。

Collections.sort(list, new Comparator<String>(){
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

無名クラスというのは今回の記事の主題ではないので文法について詳細な説明は省略しますが、値を利用する箇所に実装を直接書き込むことができる、というのが重要です。また、先ほどまでMyComparatorと名前のついていたものが「無名」になっていることがわかります。後から再利用する事はできない代わりに、だいぶスッキリしましたね。

救世主lambda

「無名クラスの記述長くない?」という要望に応えてlambda式がjava8で導入されました。lambda式はシンプルな記法で関数型インターフェースと呼ばれるインターフェースの一種を実装することができます。関数型インターフェースというのは、抽象メソッドを1つしか含まないインターフェースのことで、ざっくり言えば関数です。Comparatorもcompareという抽象メソッドしか持っていないので関数型インターフェースとなります。javaには標準でも大量の関数型インターフェースが用意されており、競技プログラミングの範囲内では関数型インターフェースを「書く」必要性はありません。lambda式を使うことで先ほどのコードは以下のように記述できます。

Collections.sort(list, (s1, s2) -> {
    return s1.length() - s2.length();
});

無名クラスの記述と比べると、Comparatorといった実装するインターフェースの名前やcompareという実装するメソッドの名前が省略されましたね。こんなに省略して大丈夫なのかと思いますが、コンパイラがCollections#sortに渡されるべきはComparatorで、Comparatorにおいて実装すべき抽象メソッドはcompareだということを読み取って、{return s1.length() - s2.length();}がcompareの実装であると自動で判断してくれます。

lambdaの書き方

lambda式の書き方は至って簡単で、[引数] -> [処理]の形で関数を記述するだけです。引数が単一の際には引数名をただ記述すれば良く、複数の際には上の例のように([引数1],[引数2],...,[引数n])というように括弧の中に列挙しましょう。0個の際には()とだけ書いておいて下さい。また、処理はメソッドと同じように{}で囲って下さい。

[引数] -> {
    doSomething1();
    doSomething2();
    return doSomething3();
}

但し、処理がdoSomething();やreturn doSomething();だけだったりする場合は{}とreturnを省略して、[引数] -> doSomething()とする省略記法が利用できます。

メソッド参照

最初の方にメソッドをオブジェクトとして扱いたいという要求があるというお話をしました。確かにlambda式を使えば(arg0, arg1) -> Receiver.methodCall(arg0, arg1)という形でメソッド呼び出しの関数を作ることができます。しかし、関数に非常に似ているにも関わらずメソッドを一々呼び出すコードを書き出すのは面倒です。そんな時に使えるのがメソッド参照という文法です。lambda式の代わりにReceiver::methodCallを上と同等の表現として使えます。また、コンストラクタに対してはReceiver::newというコンストラクタ参照を使えます。ただ、正直メソッド参照やコンストラクタ参照は使えれば便利ですが使えなくても大幅に利便性が損なわれるわけではないので、ここでは「こういうものもあるよ〜」という紹介に留めておきます。というか語り始めると文字数が死ぬ。メソッド参照を極めたい人はこの記事が大変参考になるので一通り読んでみることをお勧めします。

Stream API

今までの話をまとめると、lambdaを使うと高階関数(:メソッド呼び出しの引数に関数を指定すること)が簡単に実現できるよという話でした。この高階関数を活用することで便利になる処理の代表例として、データ列の処理が挙げられます。ここでいうデータ列というのは配列やList,Set,Mapなどのことです。普段競技プログラミング等ではfor文やIteratorを用いて処理することが多いのではないでしょうか。

Stream APIではデータ列の処理を次の3段階に分けて行うことができます。

生成処理: データ列をStreamオブジェクトに変換する
中間処理: 各データに対して関数を作用させる/並び替える/条件に応じて選択する
末端処理: データを出力する

また、記述の仕方も少し独特で、生成処理から末端処理まで文を区切らずにStream.of().foo().bar().baz()という感じでメソッド呼び出しを連鎖させて書くことが想定されています。

そんな独特なStream APIですが、段階を追ってそれぞれ見ていきましょう。

生成処理

Streamオブジェクトは様々な方法で生成することができます。但し、ここで重要なのはプリミティブ型の存在です。訳を話すと長くなるのですが、int型,long型,double型はStreamオブジェクトでなくそれ専用のIntStream, LongStream, DoubleStreamというものが用意されています。対象のデータ列がそれらのどれかであるならば、対応する特殊なStreamを生成しましょう(まああまり意識しなくても何とかなる)。
生成の方法は大量にあるのですが、競技プログラミングでよく使うStreamの生成方法ベスト4を紹介します。

// 1位
int[] array;
Arrays.stream(array); // => IntStream

// 2位
int n;
IntStream.range(0, n); // => IntStream, (0...n)のn個のデータ

// 3位
List<String> list;
list.stream(); // => Stream<String>

// 4位
Stream.of("foo", "bar", "baz"); // => Stream, A問題で使える

中間処理

Streamオブジェクトを生成したら次にするべきは中間処理です。lambdaが火を吹くのは主にこの中間処理の話になります。必要なければこの処理は飛ばしても構わないのですが、大半の場合は必要だと思います。中間処理も多種多様なことができ割と自由度が高いのですが、逆に自由度が高すぎて全てを紹介できません。同様にこちらもよく使う中間処理ベスト4という形で紹介していきましょう。

int[] a = new int[]{0, 3, 5, 7, 3, 4, 3, 0, 0, 4};

// 1位
// map: データ列の全要素を与えられた関数に通します
//      他にもStreamをIntStreamに変換するmapToIntや
//      IntStreamをStreamに変換するmapToObjなどがあります
// ここでは全ての値をxの2乗で置き換えていることになります。
// {0, 9, 25, 49, 9, 16, 9, 0, 0, 16}
Arrays.stream(a).map(x -> x * x)

// 2位
// sorted: データ列をソートします
// ちなみに上で紹介したComparatorを引数に渡すこともできます
// {0, 0, 0, 3, 3, 3, 4, 4, 5, 7}
Arrays.stream(a).sorted()

// 3位
// filter: 条件に合致するデータのみ取り出します
// ここでは奇数のみ取り出しています
// {3, 5, 7, 3, 3}
Arrays.stream(a).filter(x -> x % 2 == 1)

// 4位
// distinct: 重複するデータを1つにまとめます
// {0, 3, 5, 7, 4}
Arrays.stream(a).distinct()

関数が渡せることでたった4つのメソッドでもかなり自由度が高いことがお分りいただけたかと思います。一つ書き忘れたこととして、この中間処理だけでは元となった配列などのデータは一切変更されず、Streamの中だけに留まることには注意して下さい。

末端処理

Stream APIでできることはこの他にも大量にあるのですが、ここで全てを紹介していると10月31日になってアドベントカレンダーが崩壊してしまうので、この記事を見て下さい。

競技プログラミングでの活用例

競技プログラミングで活きてくる例としてABC103C - Modulo Summationについて考えてみましょう。

$N$ 個の正整数 $a_{1}, a_{2}, \dots, a_{N}$ が与えられます。
非負整数 $m$ に対して、 $f (m) = (m m o d a_{1}) + (m m o d a_{2}) + \dots + (m m o d a_{N})$ とします。
ここで、 $X m o d Y$ は $X$ を $Y$ で割った余りを表します。
$f$ の最大値を求めてください。

求めるべき最大値は $m = (a_{1} - 1) (a_{2} - 1) \dots (a_{N} - 1)$ の時の $f (m) = (a_{1} - 1) + (a_{2} - 1) + \dots + (a_{N} - 1)$ です。

さて、この値を求める所までくれば後はとても簡単ですね。このような簡単な処理を秒で書けるのがStream APIの良い所です。今までのfor文の考え方を捨てて、Stream API的な考え方でこの値を求めてみましょう。

生成処理: n個のデータからなるStreamを生成する
中間処理: 各 $i$ に対して $a_{i}$ を入力する
中間処理: 各 $a_{i}$ に対してそれぞれ $1$ だけ減算する
末端処理: 各値の合計を求める

これをコードに落とし込むと次のようになります。

import java.util.stream.*;
import java.util.*;
public class Main {
 public static void main(String[] a) {
  Scanner s = new Scanner(System.in);
  System.out.println(IntStream.range(0, s.nextInt()).map(i -> s.nextInt() - 1).sum());
 }
}

どの部分がどの部分に対応しているかわかりましたか？
もう少しわかりやすくするため6行目を整形してみましょう。

System.out.println(
    IntStream.range(0, s.nextInt())     //生成処理
            .map(i -> s.nextInt() - 1)  //中間処理
            .sum()                      //末端処理
);

$n$ 個のデータからなるStreamをIntStream#rangeを用いて0...nのデータとして生成している
まとめられる中間処理はmap(i -> s.nextInt() - 1)としてまとめている
IntStreamには合計や最大値・最小値を求めてくれる末端処理があらかじめ実装されている

というのがポイントですね！

最初のうちは処理をStreamで書くというのは慣れないことかもしれませんが、慣れてしまえばfor文よりも圧倒的にスッキリデータ処理を書ける場合があります。僕の競プロの提出にもよく出現していますから、さらなる使途が知りたい人は覗いてみてください。

さて、内容が薄い割に割と長い記事もここまでとなりました。明日はDeeさんとAniieさんがとっっても面白い記事を投稿してくれるはずです、楽しみですね！

競プロだけでは習得しづらいJava Stream API 【アドベントカレンダー 6日目】

lambdaってなんだろう

オブジェクト指向の世界

無名クラスの時代

救世主lambda

lambdaの書き方

メソッド参照

Stream API

生成処理

中間処理

末端処理

競技プログラミングでの活用例

関連する記事

競プロだけでは習得しづらいJava Stream API 【アドベントカレンダー 6日目】

lambdaってなんだろう

オブジェクト指向の世界

無名クラスの時代

救世主lambda

lambdaの書き方

メソッド参照

Stream API

生成処理

中間処理

末端処理

競技プログラミングでの活用例

この記事をシェア

関連する記事