Map Reduce

7-1. データの集まり

データの集まりとして、あらゆるコンピュータ言語で利用可能なのが配列型です。また、昨今のプログラミング言語で大抵利用可能なのが、線形リストや連想配列です。さらに、 Java8 から、新しいデータの集まりの取り扱い方として Stream が導入されました。

Map

Map とはデータの集まりx1, x2, ..., xn 全てに与えられた関数 f(x)を掛けた集まり f(x1), f(x2), ..., f(xn)を求めるものです。例えば、 Stream に値の2乗を求めるには次のようにします。


      stream.map((x)->x*x)

Reduce

Reduce とは足し算など結合法則の成立する2項演算により、データの集まりを集計するものを言います。データの集まり x1, x2, ..., xn に対して2項演算g(x,y) があった時、 g(g(...,g(g(x1,x2),x3),...),xn) を求めることを言います。但し、結合法則とは、 g(g(x,y),z)=g(x,g(y,z)) が成り立つことを言います。

例えば、 Stream の値のすべての積を求めるには、変数の初期化の値を含め、次のようにします。


      stream.reduce(1,(x,y)->x*y);

並列計算

Map も Reduce も並列計算可能です。 Map はすべてバラバラに別プロセスで実行できます。プロセス数が無制限なら、1ステップですべての処理が行なえます。一方、 Reduce は各ペアごとの集計が並列でできるため、プロセス数が無制限なら、最速では1ステップで要素数を半分にすることができます。つまり最速なら、要素数の対数ステップで集計を完了することができます。

Stream には parallel() メソッド、 sequncial() メソッドがあり、順次処理と並列処理を切り替えることもできます。

7-2. 演習

演習7-2

git://edu.net.c.dendai.ac.jp/git/spro/7/1 より下記のプログラムを読み込み、実行し、プログラムの文法や動作を確認しなさい。


package spro7;

import java.util.Arrays;
import java.util.List;
import java.util.function.DoubleSupplier;
import java.util.stream.Collectors;
import java.util.stream.DoubleStream;

public class Main {
	final private static int n=10000000;
	public static void main(String[] args) {
		double[] a = getRandom(n);
		DoubleStream asp = Arrays.stream(a);
		DoubleStream as = Arrays.stream(a);
		List<Double> al = Arrays.stream(a)
				.boxed()
				.collect(Collectors.toList());
		DoubleSupplier[] ds ={
				()->sumarray(a),
				()->sumstream(as),
				()->sumlist(al),
				()->sumpstream(asp)
		};
		long[] t = new long[ds.length+1];
		double[] result = new double[ds.length];
		int i;
		for(i = 0; i < ds.length; i++){
			t[i] = System.currentTimeMillis();
			result[i] = ds[i].getAsDouble();
		}
		t[i] = System.currentTimeMillis();
		for(i = 0; i < ds.length; i++) {
			System.out.println(result[i]);
			System.out.println(t[i+1] - t[i]);
		}
	}
	private static double sumlist(List<Double> al) {
		double sum = 0;
		for(double x:al) {
			sum+=x;
		}
		return sum;
	}
	private static double sumpstream(DoubleStream as) {
		return as.parallel().sum();
	}
	private static double sumstream(DoubleStream as) {
		return as.sequential().sum();
	}
	private static double sumarray(double[] a2) {
		double sum = 0;
		for(double x:a2) {
			sum+=x;
		}
		return sum;
	}
	private static double[] getRandom(int n2) {
		double[] result = new double[n2];
		for(int i=0; i<n2; i++ ) {
			result[i] = Math.random();
		}
		return result;
	}

}

演習7-3

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
すべてを表示する

演習7-4

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
Math.random によりひとつ乱数を生成する
すべての要素にその乱数をかける
すべてを表示する

演習7-5

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
double 型で一つの値を決める
すべての要素にその値をかける
すべてを表示する

演習7-6

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
double 型で一つの値を決める
すべての要素にその乱数をかけて、小数点以下を求める
小数点以下の平均値を求める
求めた平均値を表示する

7-3. 付録

コレクションのデザインパターン

オブジェクトの集まりに関する重要なデザインパターンにイテレータ(列挙子)があります。これは、集まりから生成するオブジェクトで、イテレータには、次の値を取り出すメソッドと、次の値があるかどうかを調べるメソッドを実装します。

java.util.Collection のサブクラス(List, Set)は、java.lang.Iterable インタフェースを implement しています。これは iterator() メソッドを実装していることを意味します。これで取得したオブジェクトは java.util.Iterator インタフェースを実装しています。これは、 next() メソッドと、 hasNext() メソッドを実装していることを意味します。

例7-1


List<String> list = getList();
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
    String string = iterator.next();
    System.out.println(string);
}

しかし、Java では Iterable なオブジェクトの集まりには拡張for文が適用できます。

例7-2


List<String> list = getList();
for(Strng string : list){
    System.out.println(string);
}

java.util.Iterator には値を変更したり消去したり挿入したりすることはできません。しかし、java.util.ListIterator はそれらが可能になります。


List<Integer> list = getList();
ListIterator<Integer> iterator = list.listIterator();
while(iterator.hasNext()){
    int x  = iterator.next();
    iterator.set(x+1);
}

7-4. 演習解答

演習7-3

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
すべてを表示する

配列

  
int[] a = new int[10000];
for(int i=0; i<a.length; i++){
  a[i]=i;
}
for(int x : a){
  System.out.println(x);
}

ArrayList

  
List<Integer> a = new ArrayList<>();
for(int i=0; i<10000; i++){
  a.add(i);
}
for(int x : a){
  System.out.println(x);
}

Stream

  
IntStream a = IntStream.iterate(0,x->x+1).limit(10000);
a.forEach(System.out::println);

演習7-4

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
Math.random によりひとつ乱数を生成する
すべての要素にその乱数をかける
すべてを表示する

配列

  
double[] a = new double[10000];
for(int i=0; i<a.length; i++){
  a[i]=i;
}
double r = Math.random();
for(int i=0; i<a.length; i++){
  a[i]*=r;
}
for(double x : a){
  System.out.println(x);
}

ArrayList

  
List<Double> a = new ArrayList<>();
for(int i=0; i<10000; i++){
  a.add((double)i);
}
double r = Math.random();
for(ListIterator<Double> i = a.listIterator(); i.hasNext();){
  double x = i.next();
  i.set(x*y);
}
for(Double x : a){
  System.out.println(x);
}

Stream

  
double r = Math.random();
DoubleStream.iterate(0,x->x+1.0).limit(10000)
.map(x->x*r)
.forEach(System.out::println);

演習7-5

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
double 型で一つの値を決める
すべての要素にその値をかける
すべてを表示する

配列

  
double[] a = new double[10000];
for(int i=0; i<a.length; i++){
  a[i]=i;
}
final double r = 3.14;
for(int i=0; i<a.length; i++){
  a[i]*=r;
}
for(double x : a){
  System.out.println(x);
}

ArrayList

  
List<Double> a = new ArrayList<>();
for(int i=0; i<10000; i++){
  a.add((double)i);
}
final double r = 3.14;
for(ListIterator<Double> i = a.listIterator(); i.hasNext();){
  double x = i.next();
  i.set(x*y);
}
for(Double x : a){
  System.out.println(x);
}

Stream

  
final double r = 3.14;
DoubleStream.iterate(0,x->x+1.0).limit(10000)
.map(x->x*y)
.forEach(System.out::println);

演習7-6

以下の処理を配列、ArrayList、Stream でそれぞれ作ること

0から9999までの値を持つ集まりを作る
double 型で一つの値を決める
すべての要素にその乱数をかけて、小数点以下を求める
小数点以下の平均値を求める
求めた平均値を表示する

配列

  
double[] a = new double[10000];
for(int i=0; i<a.length; i++){
  a[i]=i;
}
final double r = 3.14;
for(int i=0; i<a.length; i++){
  a[i]*=r;
  a[i]-=(int)a[i];
}
double sum=0;
for(int i=0; i<a.length; i++){
  sum+=a[i];
}
double average = sum/a.length;
System.out.println(average);

ArrayList

  
List<Double> a = new ArrayList<>();
for(int i=0; i<10000; i++){
  a.add((double)i);
}
final double r = 3.14;
for(ListIterator<Double> i = a.listIterator(); i.hasNext();){
  double x = i.next()*y;
  x -= (int) x;
  i.set(x);
}
double sum=0;
for(Double x : a){
  sum+=x;
}
double average = sum/a.size();
System.out.println(average);

Stream

  
final double r = 3.14;
double average = DoubleStream.iterate(0,x->x+1.0).limit(10000)
.map(x->{x*=y;x-=(int)x; return x;})
.average();
System.out.println(average);