FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »配列操作
このページの記事一覧

【Java】配列, リスト(List), 連想配列(Map) の初期化  


 今までのサンプルコードにも散々使ってるけど、少し複雑なものになると書くのが結構大変なので、テンプレ用にまとめてみようと思った。調べてみたら意外と使われていない(?)んだよね。ただし、あくまで値をあらかじめセットしておくグローバルな初期化のみでやってみる。ローカルの場合はブロック表記「{~}」が不要なだけで、基本的には同じ。

 よく使う例として、リスト(List)リストを配列化したもの(List[])連想配列(Map)もついでにやってみよう。

●1次元配列の初期化 : int[]
public class ArrayInitTest {

int[] arr = {1, 2, 3};

public static void main(String[] args) throws Exception {
new ArrayInitTest();
}

public ArrayInitTest() {
for (int v : arr) {
System.out.print(v + " ");
}
}
}

1 2 3

 2次元での初期化も同じように書ける。

●2次元配列の初期化 : int[][]
public class ArrayInitTest {

int[][] arr = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
};

public static void main(String[] args) throws Exception {
new ArrayInitTest();
}

public ArrayInitTest() {
for (int[] is : arr) {
for (int v : is) {
System.out.print(v + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9

 例をグローバル変数にしたのは、初期化ブロック(「{~}」で囲まれた部分)というものが使えるというのを説明するためだ。もちろんローカル変数なら必要ない。連番とか計算値をあらかじめ入れておくのには良い。内容的には全く同じものになる。

●初期化ブロックを使った、2次元配列の初期化 : int[][]
public class ArrayInitTest {

int[][] arr = new int[3][3];
{
for (int i = 0, p = 1; i < 3; i++) {
for (int j = 0; j < 3; j++) {
arr[i][j] = p++;
}
}
}

public static void main(String[] args) throws Exception {
new ArrayInitTest();
}

public ArrayInitTest() {
for (int[] is : arr) {
for (int v : is) {
System.out.print(v + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9

 静的(static)な変数やメソッドとして使いたい場合は、ブロック自体に「static」を書くと良い(クラス共通となる)。

●静的初期化ブロックを使った、2次元配列の初期化 : static int[][]
public class ArrayInitTest {

static int[][] arr = new int[3][3];
static {
for (int i = 0, p = 1; i < 3; i++) {
for (int j = 0; j < 3; j++) {
arr[i][j] = p++;
}
}
}

public static void main(String[] args) throws Exception {
for (int[] is : arr) {
for (int v : is) {
System.out.print(v + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9


- - - - - - - - - - - - - - - - - - 
■リスト(List) の初期化

 次にリスト(List)を初期化してみよう。「{~}」が2重になるが、メソッドを使った初期化もできる。

●リストの初期化 : List<E>
public class ListInitTest {

@SuppressWarnings("serial")
List<Integer> list = new ArrayList<Integer>(){
{
add(1); add(2); add(3);
}
};

public static void main(String[] args) throws Exception {
new ListInitTest();
}

public ListInitTest() {
for (int v : list) {
System.out.print(v + " ");
}
}
}

1 2 3

 通常の配列と同じように、初期化ブロックを使って、for ループなどで追加しても良いだろう。「@SuppressWarnings()」は警告を消しているだけなので、無くても動く。

 リストの2次元(ネスト)も同じように考えればできる。ちょっと中括弧「{~}」が多くなるが、ある程度まとめてしまえば、それほど難しくはないだろう。

●2次元のリスト(ネスト)の初期化 : List<List<E>>
public class ListInitTest {

@SuppressWarnings("serial")
List<List<Integer>> list = new ArrayList<List<Integer>>(){{
add(new ArrayList<Integer>(){{
add(1); add(2); add(3);
}});
add(new ArrayList<Integer>(){{
add(4); add(5); add(6);
}});
add(new ArrayList<Integer>(){{
add(7); add(8); add(9);
}});
}};

public static void main(String[] args) throws Exception {
new ListInitTest();
}

public ListInitTest() {
for (List<Integer> li : list) {
for (int is : li) {
System.out.print(is + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9

 通常の配列のときのように、連番や計算値などなら初期化ブロックを使うのも良いだろう。

●初期化ブロックを使った、2次元のリスト(ネスト)の初期化 : List<List<E>>
public class ListInitTest {

List<List<Integer>> list = new ArrayList<List<Integer>>();
{
for (int i = 0, p = 1; i < 3; i++) {
list.add(new ArrayList<Integer>());
for (int j = 0; j < 3; j++) {
list.get(i).add(p++);
}
}
}

public static void main(String[] args) throws Exception {
new ListInitTest();
}

public ListInitTest() {
for (List<Integer> li : list) {
for (int is : li) {
System.out.print(is + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9


 リストと配列を絡めることもできる。長さが決まってるなら、通常の配列を使った方が実行速度が速いので、選択肢の1つとして考慮してみるのも良いだろう。構造的には配列の初期化リストの初期化を混ぜあわせたものになる。隣接リストなどにも向いている気がする。

●配列化されたリストを初期化する : List<E>[]
public class ListInitTest {

@SuppressWarnings({ "rawtypes", "serial" })
List[] list = {
new ArrayList<Integer>(){{
add(1); add(2); add(3);
}},
new ArrayList<Integer>(){{
add(4); add(5); add(6);
}},
new ArrayList<Integer>(){{
add(7); add(8); add(9);
}},
};

public static void main(String[] args) throws Exception {
new ListInitTest();
}

public ListInitTest() {
for (List<Integer> li : list) {
for (int is : li) {
System.out.print(is + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9

 もちろん同じように、初期化ブロックを使っても良い。

●初期化ブロックを使って、配列化されたリストを初期化する : List<E>[]
public class ListInitTest {

@SuppressWarnings("unchecked")
List<Integer>[] list = new List[3];
{
for (int i = 0, p = 1; i < list.length; i++) {
list[i] = new ArrayList<Integer>();
for (int j = 0; j < 3; j++) {
list[i].add(p++);
}
}
}

public static void main(String[] args) throws Exception {
new ListInitTest();
}

public ListInitTest() {
for (List<Integer> li : list) {
for (int is : li) {
System.out.print(is + " ");
}
System.out.println();
}
}
}

1 2 3
4 5 6
7 8 9


- - - - - - - - - - - - - - - - - - 
■連想配列(Map) の初期化

 ここまで見てれば、もう連想配列(Map)の初期化も想像がつくだろう。クラスで共通に使うなら静的な初期化ブロック「static」にするのも良い。

●連想配列(Map) の初期化 : Map<K, V>
public class MapInitTest {

@SuppressWarnings("serial")
Map<String, Integer> map = new TreeMap<String, Integer>() {
{
put("Candy", 6);
put("Eliza", 9);
put("Becky", 10);
put("Alice", 13);
put("Daisy", 99);
}
};

public static void main(String[] args) throws Exception {
new MapInitTest();
}

public MapInitTest() {
for (Map.Entry<String, Integer> e : map.entrySet()) {
System.out.println(e.getKey() + " = " + e.getValue());
}
}
}

Alice = 13
Becky = 10
Candy = 6
Daisy = 99
Eliza = 9

 基本的には他のオブジェクトも同じ考え方でできるので、色々やってみると良いだろう。


(関連記事)
【Java】2次元配列のソート
【Java】連想配列(Map)を foreach(for, forEach) で取り出す
【Java】連想配列(Map)を値でソートする
【Java】配列要素の反転(reverse)
【Android】【Java】SparseArray で foreach


関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 配列操作  連想配列 
tb: 0   cm: --

【Java】lower_bound(), upper_bound() 関数を作る  


 「プログラミングコンテストチャレンジブック [第2版]」(通称:アリ本)を見ていて、ちょっと気になる解法があったのだが、C++ のライブラリの「lower_bound()」を使っていたので Java では試せなかった。というわけで Java に lower_bound(), upper_bound() を移植してみた。ちなみにこの2つの関数は二分探索の関数で、lower_bound() は「指定した値以上の先頭の要素を返す」関数で、upper_bound() は「指定した値より大きい先頭の要素を返す」関数だ。Java 標準ライブラリの「Arrays.binarySearch()」も二分探索のライブラリだが、同じ値が並んでいるときは、返ってくる要素は不定になり、見つからなかった場合は負の値になる。これら関数は、基本的に見つかった値に対して、返ってくる要素(インデクス)が違うだけと考えて良い。今回は配列内の要素での探索に使う。

●Java 版 lower_bound(), upper_bound()
/**<h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が0のときは、0が返る。</p>
* @param arr : 探索対象配列(単調増加であること)
* @param value : 探索する値
* @return<b>int</b> : 探索した値以上で、先頭になるインデクス
*/
public static final int lowerBound(final int[] arr, final int value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}

/**<h1>指定した値より大きい先頭のインデクスを返す</h1>
* <p>配列要素が0のときは、0が返る。</p>
* @param arr : 探索対象配列(単調増加であること)
* @param value : 探索する値
* @return<b>int</b> : 探索した値より上で、先頭になるインデクス
*/
public static final int upperBound(final int[] arr, final int value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}

 気になった解法というのは、「アリ本 [第2版]」の P.135 ページにある「Subsequence」(部分列問題)のはじめの方の解法だ。問題としては、

長さ N の数列 A と、整数 S が与えられます。A の連続する部分列で、その総和が S 以上となるようなもののうち、最小の長さを求めなさい。

というものだが、「最初から各インデクスまでの部分和を配列に記録し、各インデクスからの部分和で S 以上となる、先頭のインデクスを二分探索する」というアルゴリズムで解いている。これは要素がすべて正の数なら、その部分和は単調増加になるので、二分探索が適用できるというものだ。上の「lowerBound()」を使って、Java で書いてみよう。

●Java 版 二分探索を使った Subsequence 解法
//メインコード
int[] A = new int[]{5, 1, 3, 5, 10, 7, 4, 9, 2, 8}; //数列
int N = A.length; //数列の長さ
int S = 15; //求める和(以上)

static final int INF = 100000000;

System.out.println(solve()); //答え


//二分探索での解法
int solve() {
int ans = INF;
int[] sum = new int[N + 1];

for (int i = 0; i < N; i++) {
sum[i + 1] = sum[i] + A[i];
}

for (int i = 0; S <= sum[N] - sum[i]; i++) {
int t = lowerBound(sum, sum[i] + S);
ans = Math.min(ans, t - i);
}

return (ans == INF ? 0 : ans);
}

2

 といっても、この問題はその後にある「しゃくとり法」の方が、より効率が良いんだけどね。ただ、配列の中身がバラバラの数値(単調増加でない数列)だったので、部分和の二分探索は思い付かなかった。単純な全探索でも解けるけど、要素数が多いと計算量が間に合わないからね。解法は色々知っていて損はない。まぁ、ライブラリがないとこの解法はすぐにはできないが…。


 また、これら2つの関数を組み合わせると、「同じ値の連続した区間」を高速に求めることができる。例えば以下のように配列にデータが入っていたとして、探す値を v としたとき、2つの関数の差分を取れば良い。

●「同じ値の連続した区間」を二分探索で求める
int[] data = {1, 2, 2, 3, 3, 3, 4, 5, 5, 6};     //ソート済みであること
int v = 3; //検索する値
int k = upperBound(data, v) - lowerBound(data, v); //差分が個数になる(ないとき=0)
System.out.println(k);

3

 これは 3 の値が「連続で 3 個」あることを表している。


 ちなみにもう一つ工夫して、引数に Comparator を使ったりすると、単調減少でも利用することができる。ただし返る値は「見つかった値より後ろのインデクス」のようになるけどね。ほんの少し改造版も載せておこう。

●Comparator を追加した、単調減少で探索できる lower_bound(), upper_bound()
/**<h1>指定した値と同じか後ろにある、先頭のインデクスを返す</h1>
* <p>配列要素が0のときは、0が返る。</p>
* @param arr : 探索対象配列(単調増加/減少であること)
* @param value : 探索する値
* @param comparator : Comparator<Integer> インターフェイス
* @return<b>int</b> : 探索した値と同じか後ろで、先頭になるインデクス
*/
public static final int lowerBound(final int arr[], final int value, final Comparator<Integer> comparator) {
int low = 0;
int high = arr.length;
int mid;
int cmp;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
cmp = comparator.compare(arr[mid], value);
if (cmp < 0) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}

/**<h1>指定した値より後ろにある、先頭の要素を返す</h1>
* <p>配列要素が0のときは、0が返る。</p>
* @param arr : 探索対象配列(単調増加/減少であること)
* @param value : 探索する値
* @param comparator : Comparator<Integer> インターフェイス
* @return<b>int</b> : 探索した値より後ろで、先頭になるインデクス
*/
public static final int upperBound(final int arr[], final int value, final Comparator<Integer> comparator) {
int low = 0;
int high = arr.length;
int mid;
int cmp;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
cmp = comparator.compare(arr[mid], value);
if (cmp <= 0) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}


//メインコード例(A は単調減少の配列)
int ans = lowerBound(A, K, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; //降順
}
});


 あとは、探索対象の開始と終了インデクスも引数に追加して、配列の一部のみの探索も可能にするといいね。この記事でのコードは1つ1つの関数で書いてしまっているけど、一番多く引数を持つ関数を1つだけ作って、あとは引数を変えた関数をオーバーロードをしてしまう方が楽だ。必要ならば自分で作ってみると良いだろう。


(関連記事)
【Java】二分探索を汎用的に使えるようにする
【Ruby】二分探索, lower_bound, upper_bound
【Java】配列要素の反転(reverse)
【Java】2次元配列のソート
【Java】連想配列(Map)を値でソートする


■参考になる書籍


関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 二分探索  配列操作  アルゴリズム  練習問題 
tb: 0   cm: --

【Java】連想配列(Map)を値でソートする  


 キーでのソート(昇順)は TreeMap を使えば勝手にやってくれる。しかし集計など、値でのソートをしたいことも多い。その場合はリストなどを中継し、Comparator で並び変えると良い。

●連想配列(Map)を値でソート(昇順/降順)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

//初期化
Map<String, Integer> map = new HashMap<String, Integer>(){ //TreeMap でも良い
{
put("Alice", 13);
put("Becky", 10);
put("Candy", 6);
put("Daisy", 99);
put("Eliza", 9);
}
};

//Map.Entry のリストを作る
List<Entry<String, Integer>> entries = new ArrayList<Entry<String, Integer>>(map.entrySet());

//Comparator で Map.Entry の値を比較
Collections.sort(entries, new Comparator<Entry<String, Integer>>() {
//比較関数
@Override
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
return o1.getValue().compareTo(o2.getValue()); //昇順
//return o2.getValue().compareTo(o1.getValue()); //降順
}
});

//確認用
for (Entry<String, Integer> e : entries) {
System.out.println(e.getKey() + " = " + e.getValue());
}

//Java 8 なら...
//entries.forEach(e -> System.out.println(e.getKey() + " = " + e.getValue()));


 構造としてはキーと値のペア(Map.Entry)のリストを作り、そのリストをソートしている感じ。要素はオブジェクトの参照なので、キーでも値でも取り出せる。この例では Comparator を匿名クラスで作ってるが、「2次元配列のソート」のときのように、独立したクラスとして定義して置いて、フラグで昇順・降順を切り替えるのも良いだろう。


 キーを逆順(降順)ソートしたい場合は、同じような考え方でできる。

●連想配列(Map)をキーで降順ソート
//キーのリストを作る
List<String> keylist = new ArrayList<String>(map.keySet());

//Comparator でキーを降順ソート
Collections.sort(keylist, new Comparator<String>() {
//比較関数
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});

//確認用
for (String key : keylist) {
System.out.println(key + " = " + map.get(key));
}

//Java 8 なら...
//keylist.forEach(e -> System.out.println(e + " = " + map.get(e)));


 昇順なら Collections.sort(keylist) だけで良いね(TreeMap なら必要ない)。いずれにしても連想配列は順番(連番)という概念はあまりないので、List などを間に挟むと、色々操作しやすい。





(関連記事)
【Java】連想配列(Map)を foreach(for, forEach) で取り出す
【Java】配列, リスト(List), 連想配列(Map) の初期化
【Android】【Java】SparseArray で foreach
【Java】2次元配列のソート
【Java】配列要素の反転(reverse)


関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 連想配列  配列操作  ソート 
tb: 0   cm: --

【Java】配列要素の反転(reverse)  


 List の要素の操作は Collections.reverse() でできるのだが、プリミティブ型の配列の場合、Arrays を使うので、いくつか欲しい機能が無かったりするね。

 reverse() もそのうちの1つなのだが、自作するのも簡単なので、2次元配列版も含めて作ってみた。

●1次元配列の要素を反転する
/**<h1>1次元配列の要素を反転する</h1>
* <p></p>
* @param arr : 対象配列
*/
public static final void reverse(int[] arr) {
final int len = arr.length;
int tmp;
for (int i = 0; i < len / 2; i++) {
tmp = arr[i];
arr[i] = arr[len - 1 - i];
arr[len - 1 - i] = tmp;
}
}


 配列の最初と最後の方から交換して、真ん中まで来たら終わりというアルゴリズム。一番わかりやすくて良いね。検索してたら再帰を使って反転するなんてものもあったが、練習問題としては良いが、実際に使わない方がいいね。ソートのときにも書いたが、再帰はメモリを喰うので、携帯やスマホみたいなメモリが小さい端末にはあまり良くない。よく再帰アルゴリズムの例として「階乗の計算」が挙げられるが、あれも実際には使わないしね。私はいつも単純明快でいきますよ(笑)。

(参考) Javaで配列の逆順表示をやってみよう
(参考) 再帰アルゴリズム


 2次元の場合は横方向(列の入れ替え)と縦方向(行の入れ替え)が考えられるので、2通り用意した。

●2次元配列の要素を反転する(横方向)
/**<h1>2次元配列の要素を反転する(横方向)</h1>
* <p>col 方向の反転(arr[row][col])。長さの違う配列は基本的に不可。</p>
* @param arr : 対象配列
*/
public static final void reverseCol(int[][] arr) {
final int col = arr[0].length;
final int row = arr.length;
int i, j, tmp;
for (i = 0; i < col / 2; i++) {
for (j = 0; j < row; j++) {
tmp = arr[j][i];
arr[j][i] = arr[j][col - 1 - i];
arr[j][col - 1 - i] = tmp;
}
}
}


 ソートのときと同じで、入れ替えを列での処理にしただけ。

 ただ注意点としては、各行の長さが違う配列には対応してないことだ。特に例外処理は設けてないので、必要なら「ArrayIndexOutOfBoundsException」を catch か throws するようにした方が良いだろう。

●2次元配列の要素を反転する(縦方向)
/**<h1>2次元配列の要素を反転する(縦方向)</h1>
* <p>row 方向の反転(arr[row][col])。</p>
* @param arr : 対象配列
*/
public static final void reverseRow(int[][] arr) {
final int row = arr.length;
int[] tmp;
for (int i = 0; i < row / 2; i++) {
tmp = arr[i]; //行は配列の配列(ネスト)なので、行ごと入れ替えればいい
arr[i] = arr[row - 1 - i];
arr[row - 1 - i] = tmp;
}
}


 縦方向の場合は、行をまるごと入れ替えているようなものなので(参照を入れ替えている)、各行の長さが違う配列でも構わない。Java の配列ってネストしてるんだよね。List を反転する Collections.reverse() と同じ結果となる。




■Collections を用いた List の reverse

 比較用に List での reverse も書いておく。といっても簡単な使い方と結果だけ。

●1次元のリスト(List)の要素を反転する
//初期値を定義
@SuppressWarnings("serial")
List<Integer> list = new ArrayList<Integer>(){
{
add(1); add(2); add(3); add(4); add(5);
}
};

Collections.reverse(list); //要素を反転

//確認用
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();



●2次元のリスト(List のネスト)の要素を反転する(縦方向)
//初期値を定義
@SuppressWarnings("serial")
List<List<Integer>> list = new ArrayList<List<Integer>>(){{
add(new ArrayList<Integer>(){{
add(1); add(2); add(3); add(4); add(5);
}});
add(new ArrayList<Integer>(){{
add(5); add(4); add(3); add(2); add(1);
}});
add(new ArrayList(){{
add(4); add(1); add(5); add(3); add(2);
}});
}};

Collections.reverse(list); //要素を反転

//確認用
for (List<Integer> li : list) {
for (Integer i : li) {
System.out.print(i + " ");
}
System.out.println();
}


 「@SuppressWarnings("serial")」は警告を消しているだけなので、無くても動く。初期化は無理矢理やってるが、単純に list.add() で追加しても良い。ただし、2次元のリストは入れ子で new してオブジェクトを作らないといけないので注意(この例の場合、ArrayList の中に ArrayList を作ってる感じ)。

 2次元のリストの場合、この例では reverse は縦方向の反転になるが、横方向でやりたければ、各要素を取り出して「Collections.reverse(list.get(i))」のようにすれば良い。ただし、各行の長さ(要素数)が違う場合は、意図した並びにならない可能性もあるので注意。

 プリミティブ型の配列と List の使い分けは静的配列か動的配列かという感じだが、長さが変わらないのであれば、プリミティブ型の配列の方が処理は速い。特に要素数が増えたときは List はどんどん重くなっていくので、その辺を考慮に入れるのもいいだろう。「ArrayList は get() が速く、LinkedList は add(), remove() が速い」という話もあるが、まぁ、試してみるのが一番だろう。



 余談だが、並び替えには値のスワップをよく使うので、CやC++みたいな swap() 関数みたいのないかな~、と検索してたら、色々やってるので笑ってしまった。Java にはポインタはないからね。一時的に配列を使うとか Point クラスを使うとか、何かを中継しているものが多かったが、XOR 演算なんかも「なるほどな~」と思った。でも元のコード(一時変数を使うコード)よりも長かったり、演算をしてたりすると処理に時間がかかるし、オブジェクトを頻繁に new するとガベージコレクタも動きまくるし、メモリも喰うので、やっぱり使えないな~と思った。何をやっているのかわかりにくいというのも、長い目で見れば意外と重要だしね(後から改造しにくい)。色々な言語をやってると「これあったらいいのに…」と思えるものがよく出てくるので、そういうのをあらかじめ作って置くと便利かもね。

(参考) 一時変数を使わずスワップする方法
(参考) How to write a basic swap function in Java (stackoverflow)


(関連記事)
【Java】2次元配列のソート
【Java】連想配列(Map)を値でソートする
【Java】配列, リスト(List), 連想配列(Map) の初期化


関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 配列操作  アルゴリズム 
tb: 0   cm: --

【Java】2次元配列のソート  


 2次元配列でのソートを調べていたところ、基本的に Comparator でのやり方が多かったのと、Comparator の例 だと縦方向(array[y][x] の場合)でのソートが中心なので、横方向でのソート一般的なソートアルゴリズムでやってみようと思った。


(※) ソートの結果は Comparator の作り方による


■Comparator を用いた2次元配列のソート(縦方向)

 はじめに、Comparator を用いた、縦方向の2次元ソートを書いておこう。こっちの方が汎用性は高いので、使い方を覚えれば、柔軟なソートができて便利だ。ソート自体は「Arrays.sort()」を使う。

●Comparator を用いた2次元配列のソート(一番単純な例)
import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
int[][] arr = {
{5, 2},
{1, 4},
{3, 5},
{4, 3},
{2, 1}
};

Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0]; //[0] をキーにソート(昇順)
//return o2[0] - o1[0]; //[0] をキーにソート(降順)
}
});
}

 結果は一番上の画像(右側)のようになる。

 この例では同じ値はないが、ソートするキーが同じ値の場合、比較関数を少しいじれば、第2ソートキーを付け加えることもできる。

●Comparator を用いた2次元配列のソート(第2ソートキーを加える)
import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
int[][] arr = {
{5, 2},
{1, 4},
{3, 5},
{4, 3},
{2, 1}
};

Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) {
return o2[1] - o1[1]; //第2ソートキー [1] でソート(降順)
} else {
return o1[0] - o2[0]; //第1ソートキー [0] でソート(昇順)
}
}
});
}

 ポイントは、Comparator インターフェイス の「compare()」メソッドを Override しなくてはならないわけだが、この関数の戻値が「負の値」のとき、配列の要素は昇順になり、「正の値」のときは降順になるという点だ(要するに a < b のとき、a - b = 負の値、a > b のとき、a - b = 正の値、a == b のとき、a - b = 0 として並びを決めていると考えれば良い)。今回は int 型なので、引き算をしているが、他のオブジェクト(Integer、String 等)でも比較できるものはだいたい「Comparable インターフェイス」を持っているので、そのオブジェクトの「compareTo()」の戻値をそのまま返せば良い。


 毎回同じようなソートをするなら、Comparator を implements した比較用クラスを作ってしまえば、使い回しも可能だ。

●Comparator を用いた2次元配列のソート(比較用クラスを作る)
import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
int[][] arr = {
{5, 2},
{1, 4},
{3, 5},
{4, 3},
{2, 1}
};

MyComparator comparator = new MyComparator(0);
Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

/** ソートキーとなる col インデクス (arr[row][col]) */
public int sortIndex = 0;

//コンストラクタ
public MyComparator(int sortIndex) {
this.sortIndex = sortIndex;
}

//比較関数
@Override
public int compare(int[] o1, int[] o2) {
return o1[sortIndex] - o2[sortIndex]; //a<b(<c<d...) としたいとき
}
}

 「sortIndex」は面倒なので public スコープにしてあるが、private スコープにして setter を作るのも良いだろう。

 降順(逆順)にするには、上記の比較関数(compare())の戻値を逆にする。

●Comparator を用いた2次元配列のソートを降順(逆順)にする(比較関数のみ)
・・・(略)・・・
//比較関数
@Override
public int compare(int[] o1, int[] o2) {
return o2[sortIndex] - o1[sortIndex]; //a>b(>c>d...) としたいとき
}
・・・(略)・・・


 また毎回書き直すのが面倒だと思ったら、とりわけ int 型などは使用頻度は高いので、メンバを付け加えた独立したクラスとして作って置くのが良い。その方が機能を追加しやすい。例えば、ソートオーダー(昇順/降順)を自由に切り替えられるようにするには、以下のようにする。

●Comparator を用いた2次元配列のソートにソートオーダー(昇順/降順)を加える
import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
MyComparator comparator = new MyComparator(0, false); //降順になる
Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

/** ソートキーとなる col インデクス (arr[row][col]) */
public int sortIndex = 0;

/** 昇順フラグ (true = 昇順 / false = 降順) */
public boolean ascend = true;

//コンストラクタ
public MyComparator(int sortIndex) {
this.sortIndex = sortIndex;
}
public MyComparator(int sortIndex, boolean ascend) {
this.sortIndex = sortIndex;
this.ascend = ascend;
}

//比較関数
@Override
public int compare(int[] o1, int[] o2) {
if (ascend) {
return o1[sortIndex] - o2[sortIndex]; //a<b(<c<d...) としたいとき
} else {
return o2[sortIndex] - o1[sortIndex]; //a>b(>c>d...) としたいとき
}
}
}


 またこのように考えれば、同値のときの第2ソートキーを付け加えるのも簡単だ。同じようにメンバを追加して、比較関数の条件を加えれば良い。

●Comparator を用いた2次元配列のソートに第2ソートキーを加える
import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
MyComparator comparator = new MyComparator(1, false); //降順になる
comparator.sortIndex2 = 0; //第2ソートキー
comparator.ascend2 = false; //降順になる
Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

/** ソートキーとなる col インデクス (arr[row][col]) */
public int sortIndex = 0;

/** 昇順フラグ (true = 昇順 / false = 降順) */
public boolean ascend = true;

/** ソートキー(第2キー)となる col インデクス (arr[row][col]) */
public int sortIndex2 = 1;

/** 昇順フラグ(第2キー) (true = 昇順 / false = 降順) */
public boolean ascend2 = true;

//コンストラクタ
public MyComparator(int sortIndex) {
this.sortIndex = sortIndex;
}
public MyComparator(int sortIndex, boolean ascend) {
this.sortIndex = sortIndex;
this.ascend = ascend;
}

//比較関数
@Override
public int compare(int[] o1, int[] o2) {
if (o1[sortIndex] == o2[sortIndex]) { //第1キーが等しいときは、第2キーで比較
if (ascend2) {
return o1[sortIndex2] - o2[sortIndex2]; //a<b(<c<d...) としたいとき
} else {
return o2[sortIndex2] - o1[sortIndex2]; //a>b(>c>d...) としたいとき
}
} else {
if (ascend) {
return o1[sortIndex] - o2[sortIndex]; //a<b(<c<d...) としたいとき
} else {
return o2[sortIndex] - o1[sortIndex]; //a>b(>c>d...) としたいとき
}
}
}
}

 今回は割愛したが、第2ソートキーを加えたコンストラクタを付け加えるのも良いだろう。

 この手のインターフェイスや関数は他の言語にもあるので(C系やVB等の IComparer など)、考え方がわかれば、色々応用は効く。


- - - - - - - - - - - - - - - - - - 
■一般的なソートアルゴリズムを用いた2次元配列のソート(横方向)

 次に、横方向でのソートを一般的なソートアルゴリズムでやってみる。これは Arrays.sort() ではできないので、自作することになる。

●2次元配列のクイックソート(横方向)
/**<h1>2次元配列のクイックソート(範囲指定)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param first : 範囲の開始インデクス
* @param last : 範囲の終了インデクス
*/
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last) {
int i, j, k, p, tmp;

i = first; //前方検索インデクス
j = last; //後方検索インデクス
p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2; //基準値(※オーバフロー注意)

final int row = arr.length;

while (true) {
while (arr[sortIndex][i] < p) { //基準値以上の位置まで前方検索
i++;
}
while (arr[sortIndex][j] > p) { //基準値以下の位置まで後方検索
j--;
}
if (i >= j) { //交差したら終了
break;
}

//スワップ
for (k = 0; k < row; k++) {
tmp = arr[k][i];
arr[k][i] = arr[k][j];
arr[k][j] = tmp;
}

i++;
j--;
}

//基準値より2分割して再帰呼び出し(2分割できないときは再帰停止)
if (first < i - 1) {
qsort(arr, sortIndex, first, i - 1);
}
if (j + 1 < last) {
qsort(arr, sortIndex, j + 1, last);
}
}

/**<h1>2次元配列のクイックソート</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
*/
public static final void qsort(int[][] arr, final int sortIndex) {
qsort(arr, sortIndex, 0, arr[0].length - 1);
}

逆順(降順)でのクイックソート

 クイックソートのアルゴリズムは検索すればいくらでも出てくるので割愛。なお、基準値(p : Pivot) は簡略のため検索範囲の最初と最後の値を加算して2で割っているが(平均値)、Wikipedia の med3 関数のような中間値(中央値)でも良い。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

 また注意点としては、このクイックソートは安定ソートではないので、同値の場合は、他の行の並びは不定になる。他の行の順序も考慮に入れたいのなら、安定ソートのもので第2ソートキー比較などを入れる工夫が必要になるだろう。マージソートを2回使う手もある。連番なら問題はない。

 逆順(降順)にしたいなら、後述する Comparator を用いる方法がある。昇順/降順の切り替えのみなら、boolean 型のフラグを引数にして、比較を逆にしても良いだろう。

 それと仕様として、各行の長さが違う配列には対応してない。特に例外処理は設けてないので、必要なら「ArrayIndexOutOfBoundsException」を catch か throws するようにした方が良いだろう。

 また、開始インデクスと終了インデクスの引数を持っている方の「qsort(int[][],int,int,int)」は主に再帰用なので、直接使うことがないなら、private スコープにしても良いだろう。引数の少ない「qsort(int[][],int)」の方は初めから最後までのインデクスで、引数の多い方をオーバーロードしてる感じになっている。

 あと、これを作っているとき、2次元ということもあり、アルゴリズムによる実行速度も気になったので、他のアルゴリズムとの比較もしてみた。とはいえ、測定してみたら、今回作ったものではクイックソートが一番速かったので、とりあえず qsort を使っていれば事足りるかもしれない。結果は環境や言語仕様などにも違いはあるみたいだね。アルゴリズムはあまり工夫してないし(ただスワップを列にしただけ)、スマホや携帯の場合、再帰構造はメモリを喰うので、要素数によっても変わるだろう。だからこの辺りはあくまでも適当な目安として考えて欲しい。

●今回の実行速度の結果
要素数実行速度
10クイックソート>マージソート>挿入ソート
50クイックソート>挿入ソート>マージソート
100クイックソート>マージソート>挿入ソート
1000クイックソート>マージソート>挿入ソート
10000クイックソート>マージソート>挿入ソート
50000クイックソート>マージソート>挿入ソート
※速い>遅い

 特に挿入ソートは 50~100 くらいだとむしろ速かったが、このアルゴリズムは要素数によってかなり遅くなるので、10000以上は使わない方がいいだろう。ちなみに以下の参考はC++での比較。

(参考) 50以下挿入ソート、5万以下マージソート、あとはクイックソート
(参考) ソート(Wikipedia)

 ちなみに、Wikipedia の「ソートアルゴリズムの一覧」の「O(n²)」のような記号は「オーダー記法(ランダウの記号)」と言って、計算時間のおおよその目安を計るのに使われる。とりあえずよく使われるものとして、

 O(1) < O(log n) < O(n) < O(n log n) < O(n²)

※O(n) ・・・ データ量が 2倍, 3倍,... のとき、計算時間が 2倍, 3倍,... になる。
※O(n²) ・・・ データ量が 2倍, 3倍,... のとき、計算時間が 4倍(2²), 9倍(3²),... になる。
※計算量小[=速い] < 計算量大[=遅い]

の順に計算時間がかかると覚えて置けば良いだろう。


●2次元配列のマージソート(横方向)
/**<h1>2次元配列のマージソート</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
*/
public static final void msort(int[][] arr, final int sortIndex) {
final int col = arr[0].length;
if (col <= 1) { //分割できなくなったら、再帰停止
return;
}

//配列を2分割
final int row = arr.length;
final int m = col / 2; //半分より左(半端は切捨て:5 / 2 = 2)
final int n = col - m; //半分より右(半端はこっち:5 - 2 = 3)
int[][] arr1 = new int[row][m];
int[][] arr2 = new int[row][n];
int i, j;
for (i = 0; i < m; i++) {
for (j = 0; j < row; j++) {
arr1[j][i] = arr[j][i];
arr2[j][i] = arr[j][i + m];
}
}
if (n > m) {
for (j = 0; j < row; j++) {
arr2[j][n - 1] = arr[j][col - 1]; //2分割のため、半端は必ず最後の1つになる
}
}

//再帰分割と結合
msort(arr1, sortIndex); //再帰呼び出し(左半分の配列)
msort(arr2, sortIndex); //再帰呼び出し(右半分の配列)
merge(arr, sortIndex, arr1, arr2); //配列のマージ
}

/**<h1>2次元配列のマージ(マージソート用)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
* @param dst : マージされた結果配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param arr1 : マージする配列1
* @param arr2 : マージする配列2
*/
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2) {
final int col1 = arr1[0].length;
final int col2 = arr2[0].length;
final int row = arr1.length; //通常、arr1 と arr2 の row は同じ
int i = 0; //arr1 用インデクス
int j = 0; //arr2 用インデクス
int p = 0; //dst 用インデクス

//小さい方を dst に追加
int k;
while (i < col1 && j < col2) {
if (arr1[sortIndex][i] <= arr2[sortIndex][j]) {
for (k = 0; k < row; k++) {
dst[k][p] = arr1[k][i];
}
i++;
p++;
} else {
for (k = 0; k < row; k++) {
dst[k][p] = arr2[k][j];
}
j++;
p++;
}
}

//まだ残ってれば dst に追加
while (i < col1) {
for (k = 0; k < row; k++) {
dst[k][p] = arr1[k][i];
}
i++;
p++;
}
while (j < col2) {
for (k = 0; k < row; k++) {
dst[k][p] = arr2[k][j];
}
j++;
p++;
}
}

(参考) マージソート

逆順(降順)でのマージソート

●2次元配列の挿入ソート(横方向)
/**<h1>2次元配列の挿入ソート</h1>
* <p>col 方向のソート。長さの違う配列は基本的に不可。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
*/
public static final void isort(int[][] arr, final int sortIndex) {
final int row = arr.length;
final int col = arr[0].length;
final int[] tmp = new int[row];
int i, j, k, t;
for (i = 1; i < col; i++) {
t = arr[sortIndex][i];
if (arr[sortIndex][i - 1] > t) {
//列の退避
for (k = 0; k < row; k++) {
tmp[k] = arr[k][i];
}

//比較
j = i;
do {
for (k = 0; k < row; k++) {
arr[k][j] = arr[k][j - 1]; //右へずらす
}
j--;
} while (j > 0 && arr[sortIndex][j - 1] > t);

//退避した列のストア
for (k = 0; k < row; k++) {
arr[k][j] = tmp[k];
}
}
}
}

(参考) 挿入ソート

 まぁ、ほぼまんまなので(無理矢理に列を追加したというか(笑))、改良できそうならやった方が良いかもしれない。

- - - - - - - - - - - - - - - - - - 
■Comparator を用いて横(列)方向の逆順(降順)ソートをしてみる

 例えば、前述のクイックソートマージソートを逆順(降順)にしてみる。上記の MyComparator と同じ作り方で、int 型に互換性のある Integer 型で Comparator を作ってみよう。Integer(int) 型はよく使うので、独立したクラスとして作って置くのも良い。

●Integer(int) 型の比較クラス
import java.util.Comparator;

/** Integer(int) 型での比較クラス */
public class IntegerComparator implements Comparator<Integer> {

/** 昇順フラグ (true = 昇順 / false = 降順) */
public boolean ascend = true;

/**<h1>デフォルトコンストラクタ</h1>
* <p>昇順リスト用。</p>
*/
public IntegerComparator() {
}

/**<h1>並び方向の指定のコンストラクタ</h1>
* <p>比較関数を昇順または降順にする。</p>
* @param ascend : true = 昇順 / false = 降順
*/
public IntegerComparator(final boolean ascend) {
this.ascend = ascend;
}

//比較関数
@Override
public int compare(Integer o1, Integer o2) {
if (ascend) {
return o1.compareTo(o2); //昇順
} else {
return o2.compareTo(o1); //降順
}
}
}

●逆順(降順)でのクイックソート (qsort に Comparator<Integer> を加えたもの)
/**<h1>2次元配列のクイックソート(範囲指定)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param first : 範囲の開始インデクス
* @param last : 範囲の終了インデクス
* @param comparator : Comparator<Integer>
*/
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last,
final Comparator<Integer> comparator) {
int i, j, k, p, tmp;

i = first; //前方検索インデクス
j = last; //後方検索インデクス
p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2; //基準値(※オーバフロー注意)

final int row = arr.length;

while (true) {
while (comparator.compare(arr[sortIndex][i], p) < 0) { //基準値以上の位置まで前方検索
i++;
}
while (comparator.compare(arr[sortIndex][j], p) > 0) { //基準値以下の位置まで後方検索
j--;
}
if (i >= j) { //交差したら終了
break;
}

//スワップ
for (k = 0; k < row; k++) {
tmp = arr[k][i];
arr[k][i] = arr[k][j];
arr[k][j] = tmp;
}

i++;
j--;
}

//基準値より2分割して再帰呼び出し(2分割できないときは再帰停止)
if (first < i - 1) {
qsort(arr, sortIndex, first, i - 1, comparator);
}
if (j + 1 < last) {
qsort(arr, sortIndex, j + 1, last, comparator);
}
}

/**<h1>2次元配列のクイックソート</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param comparator : Comparator<Integer>
*/
public static final void qsort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
qsort(arr, sortIndex, 0, arr[0].length - 1, comparator);
}

基本的なクイックソート

●逆順(降順)でのマージソート (msort に Comparator<Integer> を加えたもの)
/**<h1>2次元配列のマージソート</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
* @param arr : 対象配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param comparator : Comparator<Integer>
*/
public static final void msort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
final int col = arr[0].length;
if (col <= 1) { //分割できなくなったら、再帰停止
return;
}

//配列を2分割
final int row = arr.length;
final int m = col / 2; //半分より左(半端は切捨て:5 / 2 = 2)
final int n = col - m; //半分より右(半端はこっち:5 - 2 = 3)
int[][] arr1 = new int[row][m];
int[][] arr2 = new int[row][n];
int i, j;
for (i = 0; i < m; i++) {
for (j = 0; j < row; j++) {
arr1[j][i] = arr[j][i];
arr2[j][i] = arr[j][i + m];
}
}
if (n > m) {
for (j = 0; j < row; j++) {
arr2[j][n - 1] = arr[j][col - 1]; //2分割のため、半端は必ず最後の1つになる
}
}

//再帰分割と結合
msort(arr1, sortIndex, comparator); //再帰呼び出し(左半分の配列)
msort(arr2, sortIndex, comparator); //再帰呼び出し(右半分の配列)
merge(arr, sortIndex, arr1, arr2, comparator); //配列のマージ
}

/**<h1>2次元配列のマージ(マージソート用)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
* @param dst : マージされた結果配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param arr1 : マージする配列1
* @param arr2 : マージする配列2
* @param comparator : Comparator<Integer>
*/
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2,
final Comparator<Integer> comparator) {
final int col1 = arr1[0].length;
final int col2 = arr2[0].length;
final int row = arr1.length; //通常、arr1 と arr2 の row は同じ
int i = 0; //arr1 用インデクス
int j = 0; //arr2 用インデクス
int p = 0; //dst 用インデクス

//小さい方を dst に追加
int k;
while (i < col1 && j < col2) {
if (comparator.compare(arr1[sortIndex][i], arr2[sortIndex][j]) <= 0) {
for (k = 0; k < row; k++) {
dst[k][p] = arr1[k][i];
}
i++;
p++;
} else {
for (k = 0; k < row; k++) {
dst[k][p] = arr2[k][j];
}
j++;
p++;
}
}

//まだ残ってれば dst に追加
while (i < col1) {
for (k = 0; k < row; k++) {
dst[k][p] = arr1[k][i];
}
i++;
p++;
}
while (j < col2) {
for (k = 0; k < row; k++) {
dst[k][p] = arr2[k][j];
}
j++;
p++;
}
}

基本的なマージソート

 内容的には、比較部分を Comparator.compare() に置き換え、再帰呼び出しの引数にも加えただけである。

 メインは、
int[][] arr = {
{5, 1, 3, 4, 2},
{2, 4, 5, 3, 1}
};
qsort(arr, 0, new IntegerComparator(false)); //降順
//msort(arr, 0, new IntegerComparator(false)); //降順

のような感じで良い。結果は以下の様になる。

 他のアルゴリズムでも色々やってみると良いだろう。


(関連記事)
【Java】連想配列(Map)を値でソートする
【Java】配列要素の反転(reverse)
【Java】配列, リスト(List), 連想配列(Map) の初期化


■参考にできる書籍


関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 配列操作  ソート  アルゴリズム実証実験 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR