Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@shindo-ozon3(Shindo Sansanso)

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

Posted at

概要

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

階乗計算(n!)

　$n!$の階乗計算をします。
　$n!$は$1$から自然数$n$までの連続する$n$個の自然数の積を計算します。
　例えば、$4!$は自然数$1$から$4$までの$4$個の積、つまり$4!=1\times2\times3\times4=24$です。
　従来通りの実装方法のサンプルコードは以下のものです。

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を用いて書き換えると以下のようになります。

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$です。
　従来通りの実装方法のサンプルコードは以下のものです。

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を用いて書き換えると以下のようになります。

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を使用しない場合は以下の通りです。

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を利用した場合は以下のようになります。

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回分計測しました。
　分布を箱ひげ図にしたものが以下のものです。

$_{10000} C _{5000}$を10回繰り返して計算した実行速度の箱ひげ図
graph1.png

$_{10} C _{5}$を100000回繰り返して計算した実行速度の箱ひげ図
graph3.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を利用すれば良さそうです。

付録

性能比較で用いたコード(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));
	}

}
性能比較で用いたコード(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));
	}

}

計測データ(ミリ秒)

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
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?