Embedded Files
2019年度向けメモ
Stream APIは jshell で段階的に操作する演習を入れると楽しそう。
excel でも50万行のcsvのファイルを読み込めた。Excelで作業内容をかしかしてみるのも
Stream の 生成 中間処理 終端処理について
・Java 8 Stream API にテキストを流してみた（終端操作編）https://qiita.com/kumazo/items/284098c530fceb05805c
・Java 8 Stream API にテキストを流してみて（中間操作編）https://qiita.com/kumazo/items/104fa685da8705b8cfd8
課題提出 第７回～第１３回 で作成した Javaプロジェクトを
１つの zip ファイルにまとめ、Webclassにアップロードする。
第12回の続き
L12b の繰り返し２乗法の解説
2のべき乗の計算について
2を１５回掛けてみます。
1*2 = 2
2*2 = 4
4*2 = 8
8*2 = 16
16*2 = 32
32*2 = 64
64*2 = 128
128*2 = 256
256*2 = 512
512*2 = 1024
ここまでで、10回。
1024*2 = 2048
2048*2 = 4096
4096*2 = 8192
8192*2 = 16384
16384*2 = 32768
2の15乗は、32768です。お疲れ様です。
2の15乗は、 2^15 と書いたり、2の右肩に15を載せて書いて表します。
前回は、プログラムで２のｎ乗を求めました。
2倍することをｎ回行うループで求めました。
(2*2) * (2*2) は、2回掛けたものどうしを掛けるので、2回の倍の4回掛けたことになります。
これを利用すると、2回、4回、8回、16回掛けた結果は、
1*2=2
2*2=4
4*4=16
16*16=256
256*256=65536
で求まります。
2^15 を15回で求めたのに、それよりも1回多い2^16は5回の掛け算で求められます。
2^15 は、
1*2=2
2*2=4
4*4=16
16*2=32
32*32=1024
1024*32=32768
と、計算方法を工夫すれば6回の掛け算で求められます。
繰り返しの掛け算を効率的に求めることが出来る理由は、掛け算では計算する順序を入れ替えることが出来るからです。どこの位置の掛け算から計算しても問題が無いからです。
（引き算、割り算はダメですね）
2*2*2*2*2*2*2*2 = ((((((2*2)*2)*2)*2)*2)*2)*2 = (((( (2*2)*(2*2) )*2)*2)*2)*2 = (( ( (2*2)*(2*2) ) * (2*2))*2)*2 = (( (2*2)*(2*2) ) * (2*2))*(2*2) = ( (2*2)*(2*2) ) * ( (2*2)*(2*2) )
ほかの計算についてはどうでしょうか？
足し算もどこの位置から足し始めても問題が無いので、このような計算方法が使えます。
2*16 を、足し算で求めてみます。
2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2 = (((2+2)+(2+2))+((2+2)+(2+2)))+(((2+2)+(2+2))+((2+2)+(2+2)))
ですから、
2+2=4
4+4=8
8+8=16
16+16=32
と、計算方法を工夫すれば１５回の足し算の代わりに、４回の足し算で求められます。
数値計算の他の例を考えます。
文字列の結合はどこの位置から結合しても問題ありません。
"abc" + "abc" + "abc" + "abc" + "abc" + "abc" + "abc" + "abc" = "abcabcabcabcabcabcabcabc"
より効率的に求めると、
"abc" + "abc" = "abcabc"
"abcabc" + "abcabc" = "abcabcabcabc"
"abcabcabcabc" + "abcabcabcabc" = "abcabcabcabcabcabcabcabc"
7回の結合操作を3回に減らせます。
集合についての操作、べき集合について考えます。
2種類の記号 〇 と ◇ の４回の組み合わせは、
〇か◇ と 〇か◇ と 〇か◇ と 〇か◇ ＝
〇〇〇〇 か 〇〇〇◇ か 〇〇◇〇 か 〇〇◇◇ か 〇◇〇〇 か 〇◇〇◇ か 〇◇◇〇 か 〇◇◇◇ か
◇〇〇〇 か ◇〇〇◇ か ◇〇◇〇 か ◇〇◇◇ か ◇◇〇〇 か ◇◇〇◇ か ◇◇◇〇 か ◇◇◇◇
より効率的に求めると、
〇か◇ と 〇か◇
＝ 〇〇 か ◇〇 か 〇◇ か ◇◇
〇〇 か ◇〇 か 〇◇ か ◇◇ と 〇〇 か ◇〇 か 〇◇ か ◇◇
＝
〇〇〇〇 か ◇〇〇〇 か 〇◇〇〇 か ◇◇〇〇 か
〇〇◇〇 か ◇〇◇〇 か 〇◇◇〇 か ◇◇◇〇 か
〇〇〇◇ か ◇〇〇◇ か 〇◇〇◇ か ◇◇〇◇ か
〇〇◇◇ か ◇〇◇◇ か 〇◇◇◇ か ◇◇◇◇
３回の集合を組み合わせる操作を２回に減らすことができました。
この様に数値計算以外についても効率に処理できます。
他にも、
くっつき算～結合法則だけが成り立つ計算 - MUSYOKUTOUMEI
上記の方法で正しく結果を得られる操作には条件があります。
準備：
操作を ｆ で表して 対象を A B Cで表し、
ｆ（A，B）
をAをBで操作することを表します。
操作の条件：
ｆ（ｆ（A，B），C）
と
ｆ（A，ｆ（B，C））
の処理結果が一致すること。
これを ｆは結合法則が成り立つ といいます。
A+B や A*B を f(A,B) と考えると、
(2+2)+2 = (2+(2+2)) = f(f(2,2),2)=f(2,f(2,2))
(2*2)*2 = (2*(2*2)) = f(f(2,2),2)=f(2,f(2,2))
です。
操作する対象に繰り返し同じ操作をする際に ２、４、８、１６…と２のべき乗の回数だけ繰り返す場合は、↑上記のような処理を行えば効率が良いことが分かりましたか？
次に、それ以外の回数について考えます。
どんな回数でも、
(1*2+0)*2+1 = 5
(1*2+1)*2+0 = 6
(1*2+1)*2+1 = 7
((1*2+0)*2+0)*2+1 = 9
の様に２進数に変換できます。
そこで、
a. 処理回数が２倍になるような処理
b. 処理回数を１回増やす処理
を組み合わせて必要な処理回数になるようにします。
これが繰り返し２乗法です。
注意）
繰り返し２乗法は、常に最適な処理（処理回数が最小）とは限りません。
例えば１５は、
((1*2+1)*2+1)*2+1 = 15
なので、繰り返し2乗法で2の15乗の計算すると、2(a. の場合）と1(b.の場合)の処理で7回の掛け算が必要です。
((((1*2*2)*2)*((1*2*2)*2))*2)*((((1*2*2)*2)*((1*2*2)*2))*2)*2
しかし、先に示した通り1回少ない6回の掛け算で求めることが出来ます。
(((1*2*2)*(2*2))*2)*(((1*2*2)*(2*2))*2)*(((1*2*2)*(2*2))*2)
=
(((1*2*2)*(2*2))*2)*
(((1*2*2)*(2*2))*2)*
(((1*2*2)*(2*2))*2)
=
(((1*2*2)*
(2*2))
*2)*
(((1*2*2)*(2*2))*2)*
(((1*2*2)*(2*2))*2)
総称型による繰り返し2乗法
L12aの pow1(2,64)は、2を64回掛けた結果を求める関数です。
処理の概要：
半分の処理回数（端数切捨て）の結果 tmpを求める。再帰呼び出しを利用する。
BigInteger tmp = pow1(x, n/2);
半分の回数による処理結果を2乗する。（端数を切り捨てた回数の2倍の回数の処理結果になる）
tmp = tmp.multiply(tmp);
切り捨てたられた処理（奇数の回数の時に発生）1回分を処理する。（ｘを１回掛ける）
if(n % 2 == 1) tmp = tmp.multiply(BigInteger.valueOf(x));
再帰呼び出しにより、処理回数は最終的に残り0回になる。
※処理回数は再帰的に毎回半分になって呼び出されるので、最終的に０になる。
その場合は最初の数として １ を処理結果とする。
if(n<1) return BigInteger.ONE
pow1のコード：
pow1(2,64); // main()での呼び出し例１
pow1(3,64); // main()での呼び出し例２
// 繰返し2乗法
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;
}
↑上のコードのpow1 は、BigInteger型の整数のべき乗を求める専用のコードになっている。
pow1を汎用化する。
BigInteger型以外の型に対してもこのアルゴリズムを利用できるように修正を加える。
総称型の型変数 T を BigInteger の代わりに使用する。
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;
}
コードの解説：
型変数の宣言 <T>
pow2は Ｔ型の値 x を n 回処理して、T型の値を求める関数。
処理は op として関数インターフェースで指定する。
T pow2(T x, int n, T one, BinaryOperator<T> op)
関数インターフェース BinaryOperator<T> は、T型の値を2つ処理するプログラム。
例）
1 + 1 2 * 2 "a" + "a" T foo(T x, T y) など
関数リテラル（ラムダ式）：
関数宣言 T foo(T x, T y) { コード } の代わりに、関数をデータとして扱う表記法。
(int x, int y) -> return x + y
引数の型を省略して使用できる場合がある。（代入先の関数インターフェースの型から推測可能など）
(x, y) -> return x + y
java7b の動作確認。整数の冪乗、文字列の繰り返し結合、冪集合の処理を確認する。
Elixir から Elm の流れで、いよいよオブジェクト指向に対する懐疑心が無視できないレベルに達した2017年冬
JavaのStream API についてＷｅｂで調べ、実験用コードを試す。
参考サイト：
https://qiita.com/takumi-n/items/369dd3fcb9ccb8fcfa44
http://www.atmarkit.co.jp/ait/articles/1404/30/news017.html
http://www.atmarkit.co.jp/ait/articles/1405/20/news032.html
プロジェクト名 java8 を作成する。
L13 クラスを作成する。
実験用コードを書き、実行する。
例） http://www.atmarkit.co.jp/ait/articles/1405/20/news032.html を参考に進める。
package java8;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;
public class L13 {
public static void main(String[] args) {
// Stream の元となるデータの生成
List<String> list = Arrays.asList("あ", "き", "す", "と", "ぜ", "ね", "こ");
String[] array = { "ア", "キ", "ス", "ト", "ゼ", "ネ", "コ" };
// Streamインスタンスの生成
Stream<String> stream1 = list.stream();
Stream<String> stream2 = Arrays.stream(array);
Stream<String> stream3 = Stream.of("１", "２", "３", "４", "５");
Stream<String> stream4 = Stream.of(array);
// Streamの各要素を標準出力します。
stream1.forEach(e -> System.out.println("stream1:" + e));
System.out.println("--------------------------------------");
stream2.forEach(e -> System.out.println("stream2:" + e));
System.out.println("--------------------------------------");
stream3.forEach(e -> System.out.println("stream3:" + e));
System.out.println("--------------------------------------");
stream4.forEach(e -> System.out.println("stream4:" + e));
System.out.println("--------------------------------------");
}
}
以下、連載記事のコードを参考に実験を続ける。
並列処理のコードを試そう。
https://builder.japan.zdnet.com/sp_oracle/35056789/3/
IntStream.range(10, 20)
.forEach(i -> System.out.print(i + " "));
System.out.println("\n--------------------------------------");
IntStream.range(10, 20)
.parallel()
.forEach(i -> System.out.print(i + " "));
System.out.println("\n--------------------------------------");
OptionalLong sum = LongStream.rangeClosed(1L, 1000000L)
.parallel()
.reduce((i, j) -> i + j);
System.out.println(sum.getAsLong());
System.out.println("\n--------------------------------------");
OptionalLong max = LongStream.rangeClosed(1L, 1000000L)
.parallel()
.reduce((i, j) -> {if(i>j) {return i;} else return j;});
System.out.println(max.getAsLong());
System.out.println("\n--------------------------------------");
OptionalLong min = LongStream.rangeClosed(1L, 1000000L)
.parallel()
.reduce((i, j) -> {return (i<j)?i : j;});
System.out.println(min.getAsLong());
System.out.println("\n--------------------------------------");
Random rnd = new Random();
OptionalInt rmin = IntStream.rangeClosed(1, 100_0000)
.map(e -> rnd.nextInt(1000_0000))
.reduce((i, j) -> {return (i<j)?i : j;});
System.out.println(rmin.getAsInt());
rmin = IntStream.rangeClosed(1, 100_0000)
.map(e -> rnd.nextInt(1000_0000))
.min();
System.out.println(rmin.getAsInt());
応用：
CPUのcoreの動作状況を確認する。
タスクバー（右クリック） → タスクマネージャー → パフォーマンス
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.Random;
import java.util.stream.IntStream;
public class L13a {
public static void main(String[] args) {
Random rnd = new Random();
//ランダムな整数をストリームで1000_0000個生成して最小値を求める
long start = System.currentTimeMillis();
OptionalInt rmins = IntStream.rangeClosed(1, 1000_0000)
.map(e -> rnd.nextInt(10000_0000))
.min();
System.out.println(rmins.getAsInt());
long end = System.currentTimeMillis();
System.out.println(end - start);
//ランダムな整数をパラレルにストリームで1000_0000個生成して最小値を求める
//外部のrndオブジェクトに依存するので並列化が阻害される
start = System.currentTimeMillis();
OptionalInt rminp = IntStream.rangeClosed(1, 1000_0000)
.parallel()
.map(e -> rnd.nextInt(10000_0000))
.min();
System.out.println(rminp.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println("---");
//rndオブジェクトの代わりにMath.random()を使用しても並列化は阻害される
start = System.currentTimeMillis();
OptionalInt rmins2 = IntStream.rangeClosed(1, 1000_0000)
.map(e -> (int)(Math.random()*10000_0000))
.min();
System.out.println(rmins2.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
start = System.currentTimeMillis();
OptionalInt rminp2 = IntStream.rangeClosed(1, 1000_0000)
.parallel()
.map(e -> (int)(Math.random()*10000_0000))
.min();
System.out.println(rminp2.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println("---");
//ランダムな整数を1000_0000個生成して配列に格納し、最小値を求める
start = System.currentTimeMillis();
OptionalInt rmins3 = Arrays.stream(
IntStream.rangeClosed(1, 10000_0000)
.map(e -> rnd.nextInt(10000_0000))
.toArray())
.min();
System.out.println(rmins3.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
//ランダムな整数を1000_0000個生成して配列に格納し、並列化して最小値を求める
//配列の生成コストが大きいので並列化の効率を測定できない
start = System.currentTimeMillis();
OptionalInt rminp3 = Arrays.stream(
IntStream.rangeClosed(1, 10000_0000)
.map(e -> rnd.nextInt(10000_0000))
.toArray())
.parallel()
.min();
System.out.println(rminp3.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println("---");
//ランダムな整数を20000_0000個生成して配列に格納する
int[] rands = IntStream.rangeClosed(1, 20000_0000)
.map(e -> rnd.nextInt(10000_0000))
.toArray();
//順次処理で最小値を求める。
start = System.currentTimeMillis();
OptionalInt rmins4 = Arrays.stream(rands).min();
System.out.println(rmins4.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
//並列処理で最小値を求める。
start = System.currentTimeMillis();
OptionalInt rminp4 = Arrays.stream(rands).parallel().min();
System.out.println(rminp4.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
//rndオブジェクトの代わりに hash値を使う
start = System.currentTimeMillis();
OptionalInt rmins5 = IntStream.rangeClosed(1, 10_0000_0000)
.map(e -> Integer.hashCode(e))
.min();
System.out.println(rmins5.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
start = System.currentTimeMillis();
OptionalInt rminp5 = IntStream.rangeClosed(1, 10_0000_0000)
.parallel()
.map(e -> Integer.hashCode(e))
.min();
System.out.println(rminp5.getAsInt());
end = System.currentTimeMillis();
System.out.println(end - start);
}
}
Stream API のメソッドを試す。
limit(個数)
filter( e -> e > 3)
第７回～第13回で作成した Javaのプロジェクトを全て提出する。
内容：
プロジェクト java1 ～ java8 および関連リソース（画像・サウンド）ファイル
workspace フォルダを zip ファイルに圧縮してまとめる。
zip ファイルを Webclass にアップロードする。
補足：
NAIST Japanese Dictionary https://ja.osdn.net/projects/naist-jdic/releases/53500 ダウンロード元
辞書ファイルは src フォルダではなく、プロジェクトフォルダに配置する。
naist-jdic.csv の単語辞書から、アナグラムを検索するコードの例）
Wikipedia: アナグラム
Java で ファイル を扱う方法 と 文字コードの扱い と Stream API の利用例です。
naist-jdic.csv には日本語の単語と品詞の分類、読み方が記載されています。
この辞書ファイルの12カラム目に 単語のよみかた が記載されているので、以下のコードで抽出して利用しています。
package java8;
import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Anagram {
public static void main(String[] args) {
//ファイルから読み込んだ文字列を行単位で格納するListオブジェクトを準備
List<String> lines = new ArrayList<String>();
// naist-jdic.csv ファイルを読み込む。文字コードは EUC-JP を指定する。
try (BufferedReader br = Files.newBufferedReader(Paths.get("naist-jdic.csv"), Charset.forName("EUC-JP"))) {
// ファイルから1行ずつ読み取る。
br.lines()
// 各行毎に処理する
.forEach(e -> { // 行全体の文字列を , で分割して文字列の配列に変換し、その１２個目の文字列を取得して、linesに追加する。
lines.add(e.split(",")[11]);
});
} catch (IOException ex) {
}
// 重複する単語を除去する
Stream<String> dict = lines.stream().distinct();
// dictに記載された単語をグループにまとめる。 // Collectors.groupingBy に、グループ化の単位となる値を求める関数を渡す。
// 集計結果は、 Map anag に記録する。
// Map は、key と value を持つデータ構造。キーワード（見出し）を付けて値を記録する。 // ここでは、
// マップanag[ 見出し => {データ…} ; … ; "たもり" => {"たもり","もたり","もりた"} ; … ]
// のようなアナグラム辞書anagを作成している
// collect は、渡された集計方法に従って dict を集計する。
// ここでは、合計のような値を1つ求める集計ではなく、グループ化を行う。
// Collectors.groupingBy に、グループ化の単位となる値を求める関数を渡す。
Map<Object, List<String>> anag = dict.collect(Collectors.groupingBy(e -> {
// 単語を文字単位に分解する。
char[] cs = e.toCharArray();
// 辞書dictから読み取った単語の、アナグラム用見出しを求める
// 単語の読み仮名を五十音順に並べ替えて見出しにする
// アナグラムになる単語どうしは、ここで求めた同じ見出しを持つ
Arrays.sort(cs);
return String.valueOf(cs);
}));
// アナグラム辞書 anag から、見出しではなく値を読み取ってStreamを作る。.values().stream()
// 同じ見出しとして登録された単語の個数 e.size() が 5 を超えたものだけを抽出する。 .filter() // 抽出結果を表示する。forEach()
anag.values().stream().filter(e -> e.size() > 5).forEach(e -> System.out.println(e));
}
}
実行結果：
[キュウジョ, キョジュウ, キョウジュ, ジュキョウ, ジュウキョ, ジョキュウ]
[キカワタ, カワキタ, カワタキ, タキカワ, カタワキ, キタカワ, ワキカタ]
[タマサカ, サカマタ, マサタカ, タカマサ, マサカタ, カタサマ, マタサカ]
[マヤカシ, カシマヤ, カシヤマ, カヤシマ, シカヤマ, ヤカマシ]
[カタイ, タカイ, イカタ, カイタ, タイカ, イタカ]
[イカダ, ダイカ, カダイ, カイダ, ダカイ, イダカ]
[イカス, カイス, イスカ, カスイ, スイカ, スカイ]
[サカイ, イサカ, カサイ, サイカ, イカサ, カイサ]
[マイコ, コマイ, イマコ, コイマ, マコイ, イコマ]
[タイコ, イコタ, コタイ, コイタ, タコイ, イタコ]
[タワイ, イワタ, タイワ, ワタイ, ワイタ, イタワ]
[タイマ, イマタ, タマイ, マイタ, マタイ, イタマ]
[タイセ, イセタ, セタイ, セイタ, タセイ, イタセ]
[シカタ, タカシ, タシカ, カシタ, シタカ, カタシ]
[カナタ, タカナ, タナカ, ナカタ, カタナ, ナタカ]
[キタミ, キミタ, ミタキ, ミキタ, タキミ, タミキ]
[イセタン, イタセン, セイタン, センタイ, タイセン, タンセイ]
[シュジョウ, ジュショウ, シュウジョ, ジュウショ, ジョシュウ, ショウジュ, ジョウシュ]
[シンジュ, シジュン, シュジン, ジュシン, シュンジ, ジュンシ, ジンシュ]
[モトノリ, ノリモト, ノリトモ, トモノリ, モノトリ, トリモノ]
Page updated
Google Sites
Report abuse