List AとList Bに含まれている要素を比較し、一致する要素を抽出するような処理はHashMapを使えば高速になる場合があります。そのテクニックを教わったので紹介します。
テストデータの作成
次のような感じで、検証用のテストデータを作成します。listAの要素数はMAX_NUMで、listBの要素数はDIVIDEで調整します。Listの要素に重複はない想定です。
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class Sample { public int id; Sample(int id) { this.id = id; } } public class HelloWorld { public static int MAX_NUM = 10000; public static int DIVIDE = 10; public static void main(String[] args) { // テストデータ作成 List<Sample> listA = new ArrayList<Sample>(); List<Sample> listB = new ArrayList<Sample>(); for (int i = 0; i < MAX_NUM; i++) { Sample sample = new Sample(i); listA.add(sample); if (i % DIVIDE == 0) { listB.add(sample); } } // 抽出処理。。 } }
このlistAとlistBの両方に含まれる要素を抽出したlistCの作成処理を考えます。
ぱっと思いつくやり方
listAをループさせ、その中でlistBをループさせて一致するものを比較抽出します。
long start = System.currentTimeMillis(); // 時間計測用(開始時刻) List<Sample> listC1 = new ArrayList<Sample>(); for (Sample sampleA : listA) { for (Sample sampleB : listB) { if (sampleA.id == sampleB.id) { listC1.add(sampleA); break; } } } long stop = System.currentTimeMillis(); // 時間計測用(終了時刻) System.out.println("ぱっと思いつくやり方 :" + (stop - start));
HashMapを使ったやり方
まずlistAをHashMapに格納し、次にlistBをループさせてHashMapに含まれるものを抽出します。
long start = System.currentTimeMillis(); // 時間計測用(開始時刻) // listAの要素をHashMapに詰める Map<Integer, Sample> mapT = new HashMap<Integer, Sample>(); for (Sample sample : listA) { mapT.put(sample.id, sample); } // listBの要素がHashMapに含まれていればlistC2に要素を追加 List<Sample> listC2 = new ArrayList<Sample>(); for (Sample sample : listB) { if(mapT.containsKey(sample.id)) { listC2.add(sample); } } long stop = System.currentTimeMillis(); // 時間計測用(終了時刻) System.out.println("HashMapを使ったやり方:" + (stop - start));
時間計測結果
時間計測結果は次のようになりました。
listA > listB (listAの要素数:100000)
listBの要素数 | 1000 | 100 | 10 |
---|---|---|---|
ぱっと思いつくやり方の処理時間 | 840 | 100 | 35 |
HashMapを使ったやり方の処理時間 | 66 | 68 | 67 |
listA、listBの要素数をそれぞれm、nとすると、ぱっと思いつくやり方の計算量はm × nになります。一方、HashMapを使ったやり方は、MapのcontainsKeyの処理時間が速いので(オーダ(1)?)、直感的な計算量はm + nになります。(例が悪く、listBがlistAの100分の1以下なので処理時間が一定に見えていますが。。)
listBの要素数がlistAのそれと比べてかなり少ない場合は2重ループで、それ以外の場合はHashMapを使うやり方のが良さそうです。また、HashMapを使ったやり方を採用する場合、もしListの要素数の大小が分かっているのであれば、HashMapに詰めるListを要素数の少ない方にすることで、メモリと計算量をさらに少なくすることができます。
結論
List AとList Bに含まれている要素で一致するものを高速に抽出する場合、両方の要素数が多ければHashMapを使ったやり方を採用するのが良さそう。メモリの使用量を気にしないのであれば。