【Java】StreamAPIを用いた階乗(n!)・順列(nPr)・組み合わせ(nCr)の計算記述方法(サンプルコード・計算時間の性能比較有)

# 概要
　本記事はJava8より追加されたStreamAPIを使用した場合と使用していない場合の階乗・順列・組み合わせの記述方法と性能比較について説明します。
　StreamAPIの理解やサンプルコードの流用等でご利用ください。
　また、それぞれの計算は静的メソッドにて、int型の入力、BigIntegerの出力で実装してます。
　本記事に記載されているサンプルコードはJava8以降で実行できます。
　サンプルコードは静的メソッドで記載してますので、クラス内に記載するだけで簡単に流用することができます。

# 階乗計算(n!)
　$n!$の階乗計算をします。
　$n!$は$1$から自然数$n$までの連続する$n$個の自然数の積を計算します。
　例えば、$4!$は自然数$1$から$4$までの$4$個の積、つまり$4!=1\times2\times3\times4=24$です。
　従来通りの実装方法のサンプルコードは以下のものです。
```Java:StreamAPIを用いない場合の階乗計算の静的メソッド
	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorialAtSimpleHonesty(int n) {
		BigInteger val = BigInteger.ONE;
		for (int i = 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}
```
　`BigInteger.ONE`に対して$1$から$n$までの連続する自然数を乗算して算出してます。
　上記コードをStreamAPIを用いて書き換えると以下のようになります。
```Java:StreamAPIを用いた階乗計算の静的メソッド
	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorial(int n) {
		return IntStream.rangeClosed(1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}

```
　`IntStream.rangeClosed(1, n)`は1からnまでの連続する$n$個の自然数のIntStreamオブジェクトを生成しています。
　`mapToObj(a -> BigInteger.valueOf(a))`の中間操作により、IntStreamオブジェクトの要素をBigIntegerに変換してます。
　最後に`reduce(BigInteger.ONE, (a, b) -> a.multiply(b))`によって、IntStreamオブジェクトの要素(1からnまでの自然数)を乗算してます。

# 順列計算(nPr)
　順列の数($_nP_r$)の計算をします。
　$_nP_r$は自然数$n$から$(n-r+1)$までの$r$個の自然数の積を計算します。
　例えば、$_5P_3$は自然数$5$から$5-3+1=3$までの3個の自然数の積、つまり$_5P_3=5\times4\times3=60$です。
　従来通りの実装方法のサンプルコードは以下のものです。
```Java:StreamAPIを用いない場合の順列計算の静的メソッド
	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutationAtSimpleHonesty(int n, int r) {
		BigInteger val = BigInteger.ONE;
		for (int i = n - r + 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}

```
　`BigInteger.ONE`に対して$n-r+1$から$n$までの連続する自然数を乗算して算出してます。
　上記コードをStreamAPIを用いて書き換えると以下のようになります。
```Java:StreamAPIを用いた順列計算の静的メソッド
	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutation(int n, int r) {
		return IntStream.rangeClosed(n - r + 1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}
```
　`IntStream.rangeClosed(n - r + 1, n)`で$n-r+1$から$n$までの連続する自然数の`IntStream`オブジェクトを返却してます。
　その後は階乗の場合と同様、`mapToObj(a -> BigInteger.valueOf(a))`の中間操作により、IntStreamの要素をBigIntegerに変換し、`reduce(BigInteger.ONE, (a, b) -> a.multiply(b))`によって、IntStreamオブジェクトの要素($n-r+1$から$n$までの連続する自然数)をそれぞれ乗算してます。

# 組み合わせ(nCr)
　組み合わせの数($_nC_r$)の計算をします。
　$_nC_r$は自然数$n$から$(n-r-1)$までの連続する$r$個の自然数を1から$r$までの連続する自然数で割った値、つまり$_nC_r=\frac{_nP_r}{r!}$で計算することができます。
　また、$_nC_r$の$r$は$n-r$に置き換えることが可能です。
　例えば、$_5C_3$は$_5C_3=_5C_2=\frac{_5P_2}{2!}=\frac{5\times4}{1\times2}$です。
　ソースコードの実装方法としては、上記サンプルコードで提示した階乗計算のメソッドと順列計算のメソッドを実装して利用することができます。
　StreamAPIを使用しない場合は以下の通りです。
```Java:StreamAPIを用いない場合の組み合わせ計算の静的メソッド
	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorialAtSimpleHonesty(int n) {
		BigInteger val = BigInteger.ONE;
		for (int i = 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}

	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutationAtSimpleHonesty(int n, int r) {
		BigInteger val = BigInteger.ONE;
		for (int i = n - r + 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}

	/**
	 * 組み合わせ計算
	 * nCrの計算を行う
	 * @param n 入力値
	 * @return 組み合わせ計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateCombinationAtSimpleHonesty(int n, int r) {
		r = Math.min(r, n - r);
		return calculatePermutationAtSimpleHonesty(n, r)
				.divide(calculateFactorialAtSimpleHonesty(r));
	}
```
　StreamAPIを利用した場合は以下のようになります。
```Java:StreamAPIを用いた組み合わせ計算の静的メソッド
	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorial(int n) {
		return IntStream.rangeClosed(1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}

	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutation(int n, int r) {
		return IntStream.rangeClosed(n - r + 1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}

	/**
	 * 組み合わせ計算
	 * nCrの計算を行う
	 * @param n 入力値
	 * @return 組み合わせ計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateCombination(int n, int r) {
		r = Math.min(r, n - r);
		return calculatePermutation(n, r).divide(calculateFactorial(r));
	}

```
　`r = Math.min(r, n - r)`は$r$を$n-r$と比較し、小さい方を$r$へ代入してます。
　順列計算の返却値のBigIntegerオブジェクトを階乗計算の返却値のBigIntegerオブジェクトのdivideメソッドによって除算することにより、組み合わせの数は算出可能です。

# 性能比較
　StreamAPIを使用した場合と未使用の場合、それぞれJava8(open-jdk-1.8.0_202)とJava11(open-jdk-11.0.2)で比較しました。
　Java8からJava11にかけてStreamAPIの性能改善がされている可能性を考え、二つのバージョンで比較してます。
　$_{10000} C _{5000}$を10回繰り返して計算した実行速度と、10C5を100000回繰り返して計算した実行速度について100回分計測しました。
　分布を箱ひげ図にしたものが以下のものです。

<b>$_{10000} C _{5000}$を10回繰り返して計算した実行速度の箱ひげ図</b>
![graph1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/846337/b2212119-520c-1cb5-c144-b8770ddd5ed6.png )

<b>$_{10} C _{5}$を100000回繰り返して計算した実行速度の箱ひげ図</b>
![graph3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/846337/3515a896-90ca-5bc4-a87f-0cf523d10b10.png)

　平均はそれぞれ以下の表に示します。
| |10000C5000を10回|| | |10C5を100000回| | | |
|:----|:----|:----|:----|:----|:----|:----|:----|:----|
| |Java8 StreamAPI使用|Java8 StreamAPI未使用|Java11 StreamAPI使用|Java11 StreamAPI未使用|Java8 StreamAPI使用|Java8 StreamAPI未使用|Java11 StreamAPI使用|Java11 StreamAPI未使用|
|平均(ミリ秒)|139.18|139.05|133.15|134.03|40.58|30.03|40.41|23|

　10000C5000を$10$回に関しては速度差が出ませんでした。
　しかし、10C5を$100000$回実行した場合にStreamAPIの方が若干遅くなりました。
　10000C5000を$10$回の場合はIntStreamオブジェクトを$10$個、10C5を$100000$回の場合はIntStreamオブジェクトを$100000$個生成しているます。そのため、オブジェクト生成時のオーバーヘッドが時間差となって表れたものだと思われます。

# 考察
　StreamAPIを用いた場合、大量に呼び出した場合に限りオーバーヘッドによる時間差が若干でますが、気にしなくてもよさそうです。
　使い分けとしては無理してStreamAPIを使う必要はなく、読みやすくなる場合に限りStreamAPIを利用すれば良さそうです。
# 付録
```Java:性能比較で用いたコード(StreamAPIを使用した場合)
import java.io.IOException;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class SampleCalculator {

	public static void main(String[] args) throws IOException {
		try (Scanner sc = new Scanner(System.in)) {
			// 一度の計算で繰り返す数
			int times = sc.nextInt();
			// nの値の入力
			int n = sc.nextInt();
			// rの値の入力
			int r = sc.nextInt();
			// 出力する時刻を格納するリスト
			List<String> results = new ArrayList<String>();
			System.out.println("計算開始");
			for (int i = 0; i < 100; i++) {
				// 開始時刻の取得(ミリ秒)
				long startTime = System.currentTimeMillis();
				// 入力されたtimes回計算を繰り返す
				IntStream.rangeClosed(1,times).forEach(e->calculateCombination(n, r));
				// 計算時刻の格納
				results.add(String.valueOf(System.currentTimeMillis() - startTime));
			}

			// 結果の出力
			Files.write(Paths.get(times+"times"+n + "C" + r + "stream.log"), results);
			System.out.println("計算終了");
		}
	}

	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorial(int n) {
		return IntStream.rangeClosed(1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}

	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutation(int n, int r) {
		return IntStream.rangeClosed(n - r + 1, n).mapToObj(a -> BigInteger.valueOf(a))
				.reduce(BigInteger.ONE, (a, b) -> a.multiply(b));
	}

	/**
	 * 組み合わせ計算
	 * nCrの計算を行う
	 * @param n 入力値
	 * @return 組み合わせ計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateCombination(int n, int r) {
		r = Math.min(r, n - r);
		return calculatePermutation(n, r).divide(calculateFactorial(r));
	}

}

```
```Java:性能比較で用いたコード(StreamAPIを使用しない場合)
import java.io.IOException;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class SampleCalculatorAtSimpleHonesty {

	public static void main(String[] args) throws IOException {
		try (Scanner sc = new Scanner(System.in)) {
			// 一度の計算で繰り返す数
			int times = sc.nextInt();
			// nの値の入力
			int n = sc.nextInt();
			// rの値の入力
			int r = sc.nextInt();
			// 出力する時刻を格納するリスト
			List<String> results = new ArrayList<String>();
			System.out.println("計算開始");
			for (int i = 0; i < 100; i++) {
				// 開始時刻の取得(ミリ秒)
				long startTime = System.currentTimeMillis();
				// 計算
				IntStream.rangeClosed(1,times).forEach(e->calculateCombinationAtSimpleHonesty(n, r));
				// 計算時刻の格納
				results.add(String.valueOf(System.currentTimeMillis() - startTime));
			}


			// 結果の出力
			Files.write(Paths.get(times+"times"+n + "C" + r + "simple.log"), results);
			System.out.println("計算終了");
		}
	}


	/**
	 * 階乗計算
	 * n!の計算を行う
	 * @param n 入力値
	 * @return 階乗計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateFactorialAtSimpleHonesty(int n) {
		BigInteger val = BigInteger.ONE;
		for (int i = 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}

	/**
	 * 順列計算
	 * nPrの計算を行う
	 * @param n 入力値
	 * @return 順列計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculatePermutationAtSimpleHonesty(int n, int r) {
		BigInteger val = BigInteger.ONE;
		for (int i = n - r + 1; i <= n; i++) {
			val = val.multiply(BigInteger.valueOf(i));
		}
		return val;
	}

	/**
	 * 組み合わせ計算
	 * nCrの計算を行う
	 * @param n 入力値
	 * @return 組み合わせ計算の結果をBigIntegerで返却する
	 */
	public static BigInteger calculateCombinationAtSimpleHonesty(int n, int r) {
		r = Math.min(r, n - r);
		return calculatePermutationAtSimpleHonesty(n, r)
				.divide(calculateFactorialAtSimpleHonesty(r));
	}

}
```
<b>計測データ(ミリ秒)</b>
|10000C5000を10回|| | |10C5を100000回| | | |
|:----|:----|:----|:----|:----|:----|:----|:----|
|Java8 StreamAPI使用|Java8 StreamAPI未使用|Java11 StreamAPI使用|Java11 StreamAPI未使用|Java8 StreamAPI使用|Java8 StreamAPI未使用|Java11 StreamAPI使用|Java11 StreamAPI未使用|
|278|283|301|308|196|135|158|87|
|185|176|145|145|40|40|121|64|
|217|210|138|138|33|16|73|64|
|137|137|136|137|40|32|40|57|
|226|209|138|138|32|25|32|24|
|209|201|129|129|72|24|41|16|
|129|137|137|129|56|24|40|24|
|129|129|169|168|33|33|40|16|
|129|137|129|137|40|64|33|25|
|169|160|129|129|40|40|39|16|
|145|178|136|144|40|24|41|24|
|161|153|137|145|104|24|32|24|
|153|136|137|138|81|25|40|16|
|128|137|137|161|32|24|40|24|
|137|129|153|145|32|24|32|16|
|129|137|145|145|32|40|41|25|
|131|121|145|152|41|64|32|16|
|137|152|137|145|32|64|40|24|
|130|129|134|145|32|57|40|24|
|137|137|129|137|40|24|33|16|
|131|136|129|128|33|24|40|24|
|137|129|128|137|64|24|40|16|
|129|137|130|129|96|24|32|24|
|129|129|129|129|89|24|40|24|
|136|136|137|128|88|25|40|16|
|130|137|129|145|73|24|41|24|
|137|129|138|129|32|24|40|16|
|137|137|129|129|40|24|40|25|
|128|128|129|129|32|25|41|16|
|137|129|129|137|32|24|40|24|
|129|137|129|128|41|24|40|24|
|129|129|129|129|35|48|32|16|
|136|136|129|128|32|64|40|16|
|137|129|134|129|32|64|40|25|
|129|137|128|129|32|65|40|24|
|137|129|129|129|41|64|48|16|
|136|137|129|129|32|65|72|26|
|129|137|129|129|32|48|40|19|
|137|129|129|137|40|25|41|24|
|129|128|129|129|32|24|32|13|
|137|137|129|128|32|24|40|24|
|137|137|137|129|41|24|32|25|
|129|137|129|129|32|16|40|16|
|136|129|121|129|32|32|40|24|
|137|137|129|128|32|24|32|24|
|129|129|129|129|41|24|41|16|
|137|137|137|129|31|32|40|24|
|137|136|129|129|40|24|32|16|
|129|129|133|129|32|24|40|24|
|137|137|129|129|32|24|33|24|
|137|129|129|129|41|25|40|16|
|137|137|121|129|32|24|40|25|
|129|136|129|129|32|24|32|48|
|137|138|129|128|40|24|41|48|
|137|137|137|129|32|25|24|16|
|128|129|129|129|41|24|48|25|
|138|137|132|129|32|24|32|24|
|128|129|130|136|40|24|48|16|
|138|137|128|129|32|24|32|24|
|136|136|122|129|32|24|40|16|
|129|129|129|129|33|24|40|24|
|137|137|129|129|39|24|33|16|
|128|137|129|128|32|25|40|24|
|145|129|129|129|32|24|32|17|
|129|137|137|129|40|24|40|24|
|137|137|121|129|33|24|32|16|
|137|129|136|129|32|24|41|15|
|128|136|129|130|40|24|40|32|
|137|129|129|132|32|27|32|16|
|137|146|130|129|33|24|40|24|
|129|129|136|129|31|24|24|17|
|137|136|129|129|41|24|48|24|
|130|129|129|129|32|24|40|24|
|137|137|121|129|40|25|32|16|
|128|129|137|129|32|24|41|24|
|137|137|129|129|32|24|32|16|
|137|137|129|129|32|24|40|24|
|137|129|129|129|40|24|32|16|
|129|136|137|129|32|25|41|24|
|137|129|129|129|41|24|40|16|
|129|137|129|129|32|24|40|16|
|137|137|129|133|32|24|32|24|
|136|128|129|128|32|24|41|16|
|129|137|129|129|41|25|32|25|
|137|137|129|129|32|24|40|16|
|137|137|129|129|32|24|40|24|
|145|146|130|137|40|25|32|16|
|137|137|129|137|33|24|40|24|
|129|137|129|129|32|24|33|16|
|137|128|129|128|32|24|40|24|
|137|137|129|129|32|24|40|16|
|129|129|129|129|40|32|32|17|
|137|137|121|138|32|24|40|24|
|129|129|137|121|40|24|40|24|
|137|137|130|128|32|24|41|16|
|137|137|129|137|32|24|32|24|
|129|129|129|129|33|25|40|8|
|136|136|129|129|40|24|24|32|
|130|137|129|129|32|24|47|16|
|137|129|129|128|33|24|41|24|