Embedded Files
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で実装してみるとよい。
Page updated
Google Sites
Report abuse