キャッシュを使用して、二重ループのパフォーマンスを改善した話　Java

問題点：二重ループによる時間計算量の増加

次のように二つのリスト間で一致する要素を見つけるために二重ループを使用したい。

    for (int i : list1) {
        for (int j : list2) {
            if (i == j) {
                System.out.println("Match found: " + i);
            }
        }
    }

このコードではlist1の各要素に対して、list2の全ての要素を比較しているため、時間計算量はO(n^2)となる。この方法はリストの要素数が少なければいいが、要素数が増えると処理時間が急激に増加する問題がある。

解決策：キャッシュを使う方法

二重ループによるパフォーマンス低下の問題を解決するために、Mapを使ってキャッシュを活用する。これにより時間計算量をO(n)に減らすことができる。

以下のサンプルコードでは、list2の要素をMapに保存し、list1の各要素がMapに存在するかをチェックしてます。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MapCacheExample {
	public static void main(String[] args) {
		List<Integer> list1 = new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		
		    // サンプルデータの作成
		    for (int i = 0; i < 1000; i++) {
		        list1.add(i);
		        list2.add(i * 2);
		    }
		
		    // Mapを使ったキャッシュの例
		    Map<Integer, Boolean> cache = new HashMap<>();
		
		    for (int i : list2) {
		        cache.put(i, true);
		    }
		
		    for (int i : list1) {
		        if (cache.containsKey(i)) {
		            System.out.println("Match: " + i);
		        }
		    }
		}
}

この方法では各リストを1度ずつしかループしないため、時間計算量はO(n)となる。

まとめ

二重ループを使用すると時間計算量がO(n^2)となり、要素数が増えると処理時間が大幅に増えパフォーマンスが下がってしまう。Mapを使用してキャッシュを活用することで時間計算量をO(n)に減らすことができる。

他にも方法はあると思いますが、本日習得した内容を記載しました。