【テクニック】List AとList Bに含まれている要素で一致するものを高速に抽出する

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を使ったやり方を採用するのが良さそう。メモリの使用量を気にしないのであれば。