2つのリストのマージ方法について

質問

2つのリストのマージ方法について
下記の要件を満たしたいと考えています。

・リスト1・2をkeyをキーにマージしたい。
　リスト1[0]：key=2, value1=b
　リスト1[1]：key=3, value1=d
　リスト1[2]：key=4, value1=e
　・
　・
　・

　リスト2[0]：key=1, value2=A
　リスト2[1]：key=2, value2=B
　リスト2[2]：key=5, value2=F
　リスト2[3]：key=6, value2=G
　・
　・
　・

　↓

　リスト3[0]：key=1, value1=A, value=""
　リスト3[1]：key=2, value1=b, value=B
　リスト3[2]：key=3, value1=d, value=""
　リスト3[3]：key=4, value1=e, value=""
　リスト3[4]：key=5, value1="", value=F
　リスト3[5]：key=6, value1="", value=G
　・
　・
　・

・リスト1・2はkeyの昇順でソート済。各リスト内では重複しているkeyはない。
・マージ後もkeyの昇順にしたい。
・実際のリストはそれぞれ数万件～数十万件なので、パフォーマンスを考慮したい。

下記のように作成してみたのですが、無理やりやりました感があり、分かりづらくバグがありそうです。またループでnewもしてたりしてパフォーマンスも悪そうです。もっとスマートにパフォーマンスもよい方法がないでしょうか？

int checkedCount = 0;

for (int i = 0; i < list1.size(); i++) {
String str1 = list1.get(i).get("key");

for (int j = checkedCount; j < list2.size(); j++) {
Map<String, String> map3 = new HashMap<String, String>();
String str2 = list2.get(j).get("key");

if (str1.compareTo(str2) < 0) {
if (i != list1.size() - 1) {
map3.put("key", str1);
map3.put("value1", list1.get(i).get("value1"));
map3.put("value2", "");
list3.add(map3);
break;
} else {
Map<String, String> map4 = new HashMap<String, String>();
map4.put("key", str2);
map4.put("value1", "");
map4.put("value2", list2.get(j).get("value2"));
list3.add(map4);
}
} else if (str1.compareTo(str2) == 0) {
map3.put("key", str1);
map3.put("value1", list1.get(i).get("value1"));
map3.put("value2", list2.get(j).get("value2"));
list3.add(map3);
checkedCount = j + 1;
break;
} else {
map3.put("key", str2);
map3.put("value1", "");
map3.put("value2", list2.get(j).get("value2"));
list3.add(map3);
checkedCount = j + 1;
}
}
}

回答No.2

Tacosan · ベストアンサー

ああ, 再帰するのは「マージ」とは関係ないですから, とりあえず今は無視してもいいです.
で, 形はそんなところ. 実際に動くかどうかは知りませんが....

お礼

有難うございました。動作は色々と確認してみます。

回答No.1

Tacosan

もとのリストが実際にはどのような構造なのかわかりませんが, ごくごく普通のマージを実行すれば事実上終わりでしょう. マージソートについて調べてみてください.

お礼

お返事有難うございます。マージソートを調べてみました。下記が一番分かりやすかったのですが、再帰呼出がいまいちぴんとこなくてまだ理解できていません。

ttp://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html

ただ今回私がやりたいところは再帰呼出とは直接関係ないようなので（勘違いをしていたらご指摘ください）、下記のように作成しなおしてみましたが、こういった方法ということでしょうか？

int i = 0;
int j = 0;

while (i < list1.size() || j < list2.size()) {
Map<String, String> map3 = new HashMap<String, String>();

if (j >= list2.size() || (i < list1.size() && (list1.get(i).get("key").compareTo(list2.get(j).get("key")) < 0))) {
map3.put("key", list1.get(i).get("key"));
map3.put("value1", list1.get(i).get("value1"));
map3.put("value2", "");
list3.add(map3);
i++;
} else if (j >= list2.size() || (i < list1.size() && (list1.get(i).get("key").compareTo(list2.get(j).get("key")) == 0))) {
map3.put("key", list1.get(i).get("key"));
map3.put("value1", list1.get(i).get("value1"));
map3.put("value2", list2.get(i).get("value2"));
list3.add(map3);
i++;
j++;
} else {
map3.put("key", list2.get(j).get("key"));
map3.put("value1", "");
map3.put("value2", list2.get(i).get("value2"));
list3.add(map3);
j++;
}
}