学習雑記 JAVA 19

復習を兼ねて、JAVA SE SILVERの問題を解いてみたが正答率59%、、、

間違えたところをポイントで見直していく。

■意外と頭に入っていなかった「継承」のまとめ

1. 継承というか、interfaceなんだよね

Interfaceの要点

- 継承が前提(インスタンス化できない)

- compilerが自動でpublicで修飾する

- Classと違って多重継承できる

- abstract methodのみ宣言する(実現したクラスが中身を必ず定義する)

- default methodをoverrideしたmethodから呼び出す場合、直接実現したClassでなければ使用できない

Interface Aがdefault methodでsample()を保持する

Class B implements Aは、sample()を呼び出せるし、overrideできる

Class C extends Bは、Aのsample()を呼び出せない

=> A.super.sample()とCに記述できない。オーバーライドしたメソッドから元のデフォルトメソッドの呼び出しは、２つ以上の実現や継承の階層をまたいで行うことはできない。

2. 同じsignatureのdefault methodの存在

interfaceAにもBにも同じ名称のsample()というdefault methodがあり、且つ、Class C imprements A, Bの時、どちらのdefault methodの実装を使うか宣言しなければcompile errorになる。

3. 継承関係にある親子のクラスで同じ名前のフィールドがある

sub classでsuper classに同名のfieldを定義してもerrorにはならない。

どちらを優先して使用するか?のルール

- fieldを参照した場合は、変数の型で宣言された方が使われる

- methodを呼び出した場合は、method中の指示に従う

学習雑記 java 18

HashMap

使ってみると奥が深いので改めて勉強したことをまとめてみる。Hashは肉の薄切りを混ぜ合わせた料理などに形容する言葉で、細片の集まりという意味合いがあります。hash  = chopped meat mixed with something

Mapの方は、よく言われるkey-value-chain-storeで、紐づける・対応づけるという意味でのMapです。この紐付けにはまず「型引数」を設定することが必要です。

1. 基本的な書き方

Mapの変数宣言<>で括る部分に、データ型を指定します。型引数を使用します。HashMapも同様で以下のように宣言できます。

HashMap<String, Integer> map = new HashMap<String, Integer>();

キーと値には指定したクラスしか使えないようにコンパイラがチェックできるようになる。

2. HashMapの代表メソッド

• キーと値を紐付けて保存する / map.put(key, value)

• キーに紐付けられた値を取得 / map.get(key)

• 特定のキーを削除する / map.remove(key)

• キーをすべて削除する / map.clear

• キーを全部取得する / map.keySet()

• 値を全部取得する / map.values()

• 対応付けたキーと値を全部取得する / map.entrySet()

• Mapが空か確認する / map.isEmpty()

3. HashMapのソート方法

まず、key名称でソートする方法（おそらく最も簡単な手法）がある。paizaなどの問題を解いていても、この辺りは出てくる。valueでソートする方法が周りくどいので、HashMapのデータ型を<Integer, String>といったようにkeyを数値にしてしまう方法を私は好ましいと考えています。

// MAP（対応づける）のソート方法
public class Main {

    public static void main(String[] args) {
        // 空のHashMapを宣言します
        HashMap<Integer, String> hashmap = new HashMap<Integer, String>();
        // HashMapにデータを保存していく
        hashmap.put(1, "one");
        hashmap.put(99, "hundred to One");
        hashmap.put(22, "twenty two");
        hashmap.put(55, "fifty five");
        hashmap.put(-3, "minus three");
        // keyでソートをするために
        // keyを取り出して、keyだけの配列データを作る
        int keyList[] = new int[hashmap.size()];
        int index =0;
        for(int key : hashmap.keySet()) {
            keyList[index] = key;
            index++;
        }
        // Arraysクラスのsortメソッドを使ってkeyListを昇順にする
        Arrays.sort(keyList);
        // ソートした配列から数値を順番に取り出し、取り出した数値をkeyとして値を出力
        for(int key : keyList) {
            System.out.print(hashmap.get(key) + ", ");
        }
        System.out.println("");
        for(int i=keyList.length-1; i>= 0; i--) {
            int key = keyList[i];
            System.out.print(hashmap.get(key) + ", ");
        }
    }
}

valueで比較する方法。インターフェースをたくさん利用して勉強にはなりますが

public class Main {

    public static void main(String[] args) {
        // 空のHashMapを宣言、今度はStringをkeyにします
        HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
        // HashMapにデータを保存していく
        hashmap.put("one", 1);
        hashmap.put("hundred to One", 99);
        hashmap.put("twenty two", 22);
        hashmap.put("fifty five", 55);
        hashmap.put("minus three", -3);

        // Map.Entryインターフェースを利用したリストを作成
        List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(hashmap.entrySet());
        // .entrySet()メソッドはkeyの配列データとvalueの配列データをそれぞれ作成している。
        // Entryを使用することで{String arrayList1[], int arrayList2[]}のようなイメージでデータが代入されている。

        // 比較関数Comparatorを使用してEntryリストの値を比較して、ソートする。
        Collections.sort(list, new Comparator<Entry<String, Integer>>() {
            public int compare(Entry<String, Integer> s1, Entry<String, Integer> s2) {
                return s1.getValue().compareTo(s2.getValue());
            }
        });
        // ソートしたデータを出力する
        for(Entry<String, Integer> entry : list) {
            System.out.print(entry.getKey() + ", ");
        }
    }
}

学習雑記 JAVA17

Heap Soat

ヒープ構造: 2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造のこと。すべてのデータの中で、木の根のデータがもっとも小さい（または大きい）ことが保障される。

これだけだと正直？？で、下記参考リンクの図式と解説をみながら理解しました。

配列インデックスとツリー要素の関係

配列内の任意の要素のインデックスをiとすると，インデックス2i+1の要素が左の子となり，インデックス2i+2の要素が右の子となります。また，インデックスiの任意の要素の親は，(i-1)/2の下界で与えられます。

参考リンク(https://www.programiz.com/dsa/heap-sort) 

親と子を比較して、子が大きければ（出力したい並び順によっては、または小さければ）位置を親と入れ替えることを下から順に行うことでソーティングを達成します。

コードはMax-Heapプロパティで、最大のアイテムはルートノードに格納されて、数が小さくなっていくように作っています。

STEP1 HEAPIFY：ヒープ構造でルートノードが最大値
STEP2 SWAP：根元の要素を削除して配列の末尾（n番目の位置）に置く ツリーの最後の項目（ヒープ）を空いている場所に置く
STEP3 REMOVE：　ヒープのサイズを1だけ小さくします。(swapステップにより最大値が対象からなくなります)
STEP4 RE-HEAPIFY：　ルートの要素を再度ヒープ化して、ルートに一番高い要素を持つようにする。
この処理をリストの全項目がソートされるまで繰り返す。

public static void heapSort(int[] array, int length) {
    for(int i = length/2-1; i>=0; i--) {
        heap(array, length, i);
    }
    for(int i= length-1; i>=0; i--) {
        if (array[0] > array[i]) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heap(array, i - 1, 0);
        }
    }
}
public static void heap(int[] array, int length, int root) {
    int larger = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < length && array[left] > array[larger]) {
        larger = left;
    }
    if (right < length && array[right] > array[larger]) {
        larger = right;
    }
    if (larger != root) {
        int temp = array[root];
        array[root] = array[larger];
        array[larger] = temp;

        heap(array, length, larger);
    }
}

public static void main(String[]args) {
    int[] test = {
            6, 1, 1, 5, 9, 3, 7, 6 ,4 ,2, 0, -8,
            4, 9, 11, 32
    };
    heapSort(test, test.length);
    for (int number : test) {
        System.out.print(number + " ");
    }
}

学習雑記 JAVA16

ソートのアルゴリズム、今回はmerge sort。

merge sortは２つのステップからなる。

1. divide : 読んで字の如く配列の要素を半分に分割した２つの配列を作成する。

2. conquer: 配列の要素を並び替えて結合する。

流れ自体はそれほど難しくも何ともないが、自分で作ったコードと、見本のコードの出来の差が酷くて、色々と学ぶものがあったので、まずはそれをまとめる。

＊再起メソッド

for のような反復的なループを、メソッドで実現する。

メソッドの中身を単純化して、自信を繰り返し呼び出すことを行う。

字面の意味では知っていたが、今回、あ〜こういうことかと納得し、理解した。アルゴリズムを読むことは本当に勉強になります。

＊ b=a++ / b=++a の違い

変数bに代入して、aに１足すか、aに１足してからbに代入するかの違いでしかないのだが、意識していないと

 array[k] = divided_left[j];
 k++;
 j++;

みたいに２行無駄に書いてしまう。慣れだとは思うのですが、知っているのと使えるのとで大分差があるなと一人で納得していた。

＊Merge Sort

public class Main {
    public static void mergeSort(int[] array, int n) {
        if (n<2) {return;}
        int center = n/2;
        int[] divided_one = new int[center];
        int[] divided_left = new int[n-center];

        for (int i=0; i<center; i++) {
            divided_one[i] = array[i];
        }
        for (int i=center; i<n; i++) {
            divided_left[i-center] = array[i];
        }
        mergeSort(divided_one, center);
        mergeSort(divided_left, n-center);
        merge(array, divided_one, divided_left, center, n-center);

    }
    public static void merge(
            int[] array, int[] divided_one, int[] divided_left, int c, int cn) {
        int i=0, j=0, k=0;
        while(i<c && j<cn){
            if(divided_one[i] <= divided_left[j]) {
                array[k++] = divided_one[i++];
            } else {
                array[k++] = divided_left[j++];
            }
        }
        while(i<c) {
            array[k++] = divided_one[i++];
        }
        while(j<cn) {
            array[k++] = divided_left[j++];
        }
    }

    public static void main(String[]args) {
        int[] test = {
                6, 1, 1, 5, 9, 3, 7, 6 ,4 ,2, 0, -8,
                4, 9, 11, 32
        };
        mergeSort(test, test.length);
        for (int number : test) {
            System.out.print(number + " ");
        }
    }
}

学習雑記15 JAVA

前回の内容から、ソーティングアルゴリズムを１つずつ実行してまとめていこうと思う。wikiなどで調べると本当に様々なアルゴリズムで勉強になります。https://en.wikipedia.org/wiki/Sorting_algorithm

ひとまずは基本のシンプルなソートをJAVAで作成してみた。

次回は Merge / Heap / Quick / Shell を実行していきたい。

＊Bubble Sort

- 1 先頭の要素と、次の要素とを比較して、先頭が大きければ入れ替える。

- 2 同じように次々の要素を比較していく。

- 3 最終的に最大値が配列の最後の要素になる。

- 4 1に戻って同じことを行うが、最大値の順番は変更しないので、継続条件を考慮する(そのループ数から-1)

bubble sort (java)

＊Selection Sort

- 配列の先頭要素とそれ以外の要素を比較し、最小値を先頭要素に代入する。これを繰り返すことで配列の中身を入れ替える。

- からの配列かクローンを作って順に代入してやるか、比較した値同士を常に入れ替えるようにするか。

＊Insertion Sort

- 要素を一つ（a）取り出して並べる

- 次の要素(b)を取り出して並べ、先に並べた一つ目の要素(a)の大小を比較する。この時、小さい時は前に、大きい時は後ろに入れ替える。

- 次の要素(c)も順に比較し、小さければ前の要素(b)と位置を交換し、さらに最初の要素(a)と比較し、交換するかしないかを確認する。

- この繰り返し

insertion sort (java)

学習雑記6 JAVA14

配列のsort考え方

ArraysとCollectionsを利用すれば一瞬で終わります。

Arrays.sort(配列); 　　// 小-->大

Arrays.sort(配列, Collections.reverseOrder());　　// 大-->小

入力する複数（必ず偶数）の任意の1桁の数値を２つ並べて、2桁の整数とし、それらの和の総数で最大値を求めるという問題の中で、配列を作って中身を入れ替えて大小の順を作り、大きい順に半分を10倍して総和を求めた。

その仮定で上記のクラスを使用しないことが必要だったため、

for ループで入力順に配列 array[ i ]に代入し、その配列 arrayから１つずつデータを取り出し比較していく計算を行った。

バブルソートは効率悪い、頭のよくない並び替えと教わったが、この考え方しかわからなかった（知らなかった）ので時間内に書ききることだけ考えた。ソーティングに関してはもっと考え方ややり方を勉強したいと思いました。

[追記]アルゴリズムを調べたところ下記は"選択ソート"というようだ。バブルソートから記述量減らそうとしたら結果的にこうなったのだが、もの知らずで恥ずかしい、、

for (int i=0; i<array.length-1; i++) {

   int max = array[ i ];

   int max_i = i;

   for (int j=i+1; j<array.length; j++) {

      if ( array[ j ] > max ) {

         max = array[ j ];

         max_i = j;

      }

   }

   array[ max_i ] = array[ i ];

   array[ i ] = max;

}

学習雑記 JAVA13

抽象化プログラミング

interfaceのポイント

- 型を規定するだけで実装がない。

- 実装を持たない抽象メソッドを定義する。

- interfaceを実現するクラスは定義された抽象メソッドをオーバーライドする必要がある（強制）

- interface自身はインスタンス化できない。

- interfaceの継承やクラスの多重実現により、複数のinterfaceを同時に実現できる。

Classとinterfaceの違い

Class

- ポリモーフィズムを使って扱うための共通の型の定義（ここは同じ）

- どのようなメソッドを持つべきかという定義 => 具体的な処理 = 実装がある（具象メソッド）。

対して、interfaceはデータの型（扱い方）だけが規定される。

intefaceには抽象メソッドだけでなくフィールドも定義可能。しかし、定義できるフィールドは定数のみであることに注意が必要。

interfaceはClassと違い、インスタンス化できないので、値が変更できるフィールドを定義できない。定数は必ず何らかの値を持ち、そのため、定数の宣言は必ず初期化と一緒にしなければいけない。

public interface SampleInterface {

   int NUM;

}

*初期化していないため、コンパイルエラー

public interface SampleInterface {

   int NUM = 10;

}

*フィールド宣言と初期化を同時に実行

*また、その特性から暗黙的にpublic final staticと修飾されている。書く必要はないが明示的にpublic final static int NUM = 10;とした方がわかりやすい。