12. デザインパターン(3/x)

Javaの総称型解説

参照： https://www.sejuku.net/blog/22699

アルゴリズムの効率化について考える。

例）

冪乗（べき乗計算）

https://en.m.wikipedia.org/wiki/Addition-chain_exponentiation

冪乗計算を効率的に行うアルゴリズム 繰り返し2乗法 をJava で メソッド pow1 として実装する。

さらに、pow1 を 特定の型以外にも適用できるように、 総称型メソッド を用いて汎用性を持たせる。

プロジェクト名 java7 を作成する。

class L12 を作成し、以下について実験する。

総称型入門

授業で解説を交えながら、以下を作成する。

package java7;

public class L12 {

public static void main(String[] args) {

int x = 1;

int y = 2;

swap(x,y);

System.out.println("x= " + x);

System.out.println("y= " + y);

Pair p = new Pair(1,2);

//Pair2<String> p = new Pair2<>("abc","xyz");

//Pair2<Double> p = new Pair2<>(1.2, 2.2);

System.out.println("px= " + p.first);

System.out.println("py= " + p.second);

p.swap();

System.out.println("px= " + p.first);

System.out.println("py= " + p.second);

p.swap();

System.out.println("px= " + p.first);

System.out.println("py= " + p.second);

}

// うまく行かない例

static void swap(int a, int b) {

System.out.println("a= " + a);

System.out.println("b= " + b);

int tmp;

tmp = a;

a = b;

b = tmp;

System.out.println("a= " + a);

System.out.println("b= " + b);

}

static class Pair {

int first;

int second;

Pair(int f, int s) {

first = f;

second = s;

}

void swap() {

int tmp;

tmp = first;

first = second;

second = tmp;

}

}

static class Pair2<F> {

F first;

F second;

Pair2(F f, F s) {

first = f;

second = s;

}

void swap() {

F tmp;

tmp = first;

first = second;

second = tmp;

}

}

}

ちなみに、2進数の排他的論理和 Xor を利用してビット演算を行えば、2つの変数の整数の値の入れ替えは一時変数なしで行える。

例）

b ^= a;

a ^= b;

b ^= a;

画像の入れ替えバージョン（二進数の０と１を、黒と白と考える）

白黒画像のＡとＢを用意する、

画像Ａ

画像Ｂ

画像Ａに画像Ｂを合成する。

合成方法は、Ｘｏｒ

同じ色の部分は黒 つまり黒と黒は 黒 、白と白は 黒。 髪の毛はどちらも黒なので 黒。背景はどちらも白なので 白。

異なる色部分は白 つまり黒白 白黒 と異なる色は 白になる。

画像Ａはこのようになる。

＝ Ａ xor Ｂ

画像Ｂに、合成後の画像ＡをＸｏｒで合成する。すると画像Ｂは、合成前の画像Ａになる。

なぜなら、合成後の画像Ａは、元の画像Ａと元の画像Ｂのどちらに対しても、

Ｘｏｒで合成する場合 色の変化が必要なら 白

Ｘｏｒで合成する場合 色の変化が不要なら 黒

の状態になっているので。

合成後の画像Ｂ

＝ Ｂ xor Ａ

合成後の画像Ａに合成後の画像ＢをＸｏｒで合成する。すると画像Ａは、合成前の画像Ｂになる。

合成後の画像A

＝ Ａ xor Ｂ←合成後の画像Ｂ

画像Ａと画像Ｂの内容を入れ替えることが出来た。

プロジェクト java7 に以下を追加する。

class L12a を作成し、以下について実験する。

授業で解説を交えながら、以下を作成する。

package java7;

import java.math.BigInteger;

public class L12a {

public static void main(String[] args) {

// 冪乗（べき乗の計算）

int x = 1;

//long x = 1L;

for(int i=0; i<65; i++){

System.out.println(i +":"+ x);

x *= 2;

}

BigInteger bigx = BigInteger.ONE;

for(int i=0; i<65; i++){

System.out.println(i +":"+ bigx);

bigx = bigx.multiply(BigInteger.valueOf(2L));

}

bigx = BigInteger.valueOf(2L);

for(int i=1; i<65; i*=2){

System.out.println(i +":"+ bigx);

bigx = bigx.multiply(bigx);

}

pow1(2,64);

pow1(2,63);

pow1(2,62);

pow1(3,64);

pow1(3,63);

}

// 繰返し2乗法

// https://en.m.wikipedia.org/wiki/Addition-chain_exponentiation

static BigInteger pow1(int x, int n) {

if(n<1) return BigInteger.ONE;

BigInteger tmp = pow1(x, n/2);

tmp = tmp.multiply(tmp);

if(n % 2 == 1) tmp = tmp.multiply(BigInteger.valueOf(x));

System.out.println(n +":"+ tmp);

return tmp;

}

}

プロジェクト java7 に以下を追加する。

class L12b を作成し、以下について実験する。

授業で解説を交えながら、以下を作成する。

package java7;

import java.math.BigInteger;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.function.BinaryOperator;

public class L12b {

public static void main(String[] args) {

// 冪乗（べき乗の計算）

pow2(BigInteger.valueOf(2), 64, BigInteger.ONE, (a,b)-> a.multiply(b));

pow2(BigInteger.valueOf(2), 63, BigInteger.ONE, (a,b)-> a.multiply(b));

pow2(2L, 63, 1L, (a,b)-> a*b);

pow2("ab", 10, "", (a,b)-> a+b);

// 型推論を利用したダイヤモンド演算子 <> の利用例

ArrayList<ArrayList<Integer>> ai = new ArrayList<>();

ai.add( new ArrayList<Integer>(Arrays.asList(0)));

ai.add( new ArrayList<Integer>(Arrays.asList(1)));

// 冪集合

pow2(

ai,

4,

new ArrayList<ArrayList<Integer>>(),

(xs,ys) -> {

if(xs.isEmpty()) return ys;

ArrayList<ArrayList<Integer>> tmp = new ArrayList<>();

for(ArrayList<Integer> x:xs) {

for(ArrayList<Integer> y:ys) {

ArrayList<Integer> tmp2 = new ArrayList<>();

for(Integer e:x) {

tmp2.add(e);

}

for(Integer e:y) {

tmp2.add(e);

}

tmp.add(tmp2);

}

}

return tmp;

}

);

// 他にも pow2 の利用例を探る

}

// 繰返し2乗法

// https://en.m.wikipedia.org/wiki/Addition-chain_exponentiation

static <T> T pow2(T x, int n, T one, BinaryOperator<T> op) {

if(n<1) return one;

T tmp = pow2(x, n/2, one, op);

tmp = op.apply(tmp, tmp);

if(n % 2 == 1) tmp = op.apply(tmp, x);

System.out.println(n +":"+ tmp);

return tmp;

}

}

繰り返し２乗法で置換を処理する。

置換：

数字の列 0 1 2 の並べ替えは、次の6通りある。

0 1 2 、0 2 1、1 2 0、1 0 2、2 0 1、2 1 0

これを数字を入れ替えて（置換して）並べ変える操作方法が6通りあると考える（置換が6個）。

0 1 2 は並べかえなし(または巡回なし)。

2 1 0 は、1は置換なし。0と2を入れ替える（または0 2 で巡回する）。

1 2 0 は、0→1 、1→2、2→0 になるように入れ替える（または0 1 2の巡回)。

など。

上では置換の方法を元の数字(0 1 2) を どの数字で置き換えるかで表している。

0→2 1→0 2→1 なら 2 0 1

置換は巡回で表すことができる。

0→1→2→0 を (0 1 2)

この表記方法では 2→0 の部分は省略する（必ず先頭の数字に置換するので）。

置換を複数の巡回で表記することができる

1 2 0 4 3

は、1 2 0 の3個の置換と 4 3 の2個の置換に分けることができる（置換する数値で共通のものがないので）。

すると 1 2 0 は (0 1 2) の巡回で、4 3 は (3 4)の巡回である。

1 2 0 4 3 は (0 1 2)(3 4)

巡回の数字は順に並ぶ必要はない。

4 3 0 1 2 は (0 4 2)(1 3) や(2 0 4)(3 1) と同じ。(0 2 4)(1 3)とは異なる。

例）

ArrayList で置換テーブルを与え、置換テーブルを繰り返し適用して数値を並べ替えるプログラム

import java.util.ArrayList;

import java.util.Collections;

import java.util.function.BinaryOperator;

import java.util.stream.Collectors;

public class L12c {

public static void main(String[] args) {

// 置換の繰り返し

// 置換なし（元のまま）

ArrayList<Integer> e = new ArrayList<>();

Collections.addAll(e, 0, 1, 2, 3, 4);

// 置換テーブル（１回巡回）

ArrayList<Integer> r = new ArrayList<>();

Collections.addAll(r, 1, 2, 3, 4, 0);

BinaryOperator<ArrayList<Integer>> op = (x, y) -> x.stream()

.map(i -> y.get(i))

.collect(Collectors.toCollection(ArrayList<Integer>::new));

pow2(r,16,e,op);

// 置換なし（元のまま）

ArrayList<Integer> e2 = new ArrayList<>();

Collections.addAll(e2, 0, 1, 2, 3, 4, 5, 6, 7);

// 置換テーブル（１回巡回）

ArrayList<Integer> r2 = new ArrayList<>();

//0, 1, 2, 3, 4, 5, 6, 7

//1, 2, 3, 4, 5, 6, 7, 0 //８回で巡回

//0, 1, 2, 3, 4, 5, 6, 7

//1, 2, 3, 4, 5, 6, 0, 7 //７回で巡回

//0, 1, 2, 3, 4, 5, 6, 7

//1, 2, 3, 4, 5, 0, 6, 7 //６回で巡回

// ８回で巡回×７回で巡回×６回で巡回 を合成

//0, 1, 2, 3, 4, 5, 6, 7

//1, 2, 3, 4, 5, 6, 7, 0

//2, 3, 4, 5, 6, 7, 1, 0

//3, 4, 5, 6, 7, 2, 1, 0

Collections.addAll(r2, 3, 4, 5, 6, 7, 2, 1, 0);

pow2(r2,8,e2,op);

pow2(r2,8*7,e2,op);

pow2(r2,8*7*6,e2,op);

//置換テーブルを分析

//3, 4, 5, 6, 7, 2, 1, 0

//(0 3 6 1 4 7)(2 5) ６回の巡回と２回の巡回の組み合わせ。→６回で元に戻る。

pow2(r2,3*8,e2,op);

}

// 繰返し2乗法

// https://en.m.wikipedia.org/wiki/Addition-chain_exponentiation

static <T> T pow2(T x, int n, T one, BinaryOperator<T> op) {

if (n < 1)

return one;

T tmp = pow2(x, n / 2, one, op);

tmp = op.apply(tmp, tmp);

if (n % 2 == 1)

tmp = op.apply(tmp, x);

System.out.println(n + ":" + tmp);

return tmp;

}

}

対称群の元の最大位数について、こちらの卒業論文に表が記載されている。

www.lab2.toho-u.ac.jp/sci/is/shirayanagi/2013/koizumi.pdf

例えば、P.8の 1≦ｎ≦50でのｎ次対称群の元の最大位数 の表を見ると、

N=8 つまり８個の数字（8次対称群の元）を特定の方法で並べ替える操作を繰り返した場合、

15回以内に元に戻る（元の最大位数が15）

ということがわかる。

さらに、P.13の、1≦ｎ≦50 でのｎ次対称群の元の位数の組み合わせ の表を見ると、

N=8の時の最大位数を与える元の位数の組み合わせをみると、[3,5]

であり、

元に戻るために最大回数の15回を必要とするのは、3回の巡回と5回の巡回を組み合わせた置換、

(0 1 2)(3 4 5 6 7) や (0 2 4)(1 3 5 6 7)

などである

ということがわかる。

次年度検討項目：

余力があれば、Decoratorパターン Template Method パターン Strategy パターン 辺りを扱う。

興味がある受講生は上記のデザインパターンについて調べてJavaで実装してみるとよい。