読者です 読者をやめる 読者になる 読者になる

発熱するマイナー魂

隠れた名作の発掘が生きがい。サブカル作品の感想とIT技術メモ中心のブログです。

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

Java

スポンサードリンク

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