配列で頑張りすぎてない？パフォーマンス劣化の恐怖から僕を救ってくれた「データ構造」備忘録

1. はじめに：そのコード、データが増えても大丈夫？

実務で「データ量が増えると処理が激重になる」という課題にぶつかったことはありませんか？
僕も先日、数万件の注文データからユニークな商品IDを抽出するコードで、システムをフリーズさせかけました。

原因は 「データ構造の選択ミス」。
「とりあえず使い慣れている ArrayList を使えばいいや」という油断が、恐ろしいパフォーマンス低下を招いていたのです。

2. なぜ ArrayList は遅かったのか

当時の僕が書いていたコード（コードA）がこちらです。

public List<String> extractUniqueProductIds(List<Order> orders) {
    List<String> uniqueProductIds = new ArrayList<>(); 
    
    for (Order order : orders) {
        for (String productId : order.getProductIds()) {
            // 毎回リストの先頭から「君、もういる？」と1つずつ確認しちゃう
            if (!uniqueProductIds.contains(productId)) { 
                uniqueProductIds.add(productId);
            }
        }
    }
    return uniqueProductIds;
}

なぜ遅い？
ArrayList.contains() は、リストの中身を先頭から順に確認する「線形探索」を行います。もしIDの異なるデータが10万件ある場合、約50億回の比較が発生します。これが「データが増えると動かなくなる」正体です。

3. 救世主：Set, Map, List の使い分けと実例

この問題を解決するには、データの「整理ルール（データ構造）」を変える必要があります。Javaの主要な仲間たちを紹介します。

① Set（セット）：重複を許さない「背番号ロッカー」

一番のポイントは、「同じ値を入れようとしても無視される」 点です。

// 1. HashSet: とにかく早い！順序はバラバラ
Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Apple"); // 重複なので無視される
System.out.println(hashSet); // [Banana, Apple] (順不同)

// 2. LinkedHashSet: 重複は消したいけど「入れた順」は守りたい
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
linkedHashSet.add("Apple");
System.out.println(linkedHashSet); // [Apple, Banana] (入れた順)

// 3. TreeSet: 常に「辞書順」で並んでほしい
Set<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
System.out.println(treeSet); // [Apple, Banana] (アルファベット順)

② Map（マップ）：ラベルで探す「下駄箱」

「キー（ID）」を渡して「値（データ）」を取り出す形です。

// 1. HashMap: 基本はこれ。検索が爆速！
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Apple", 100);
hashMap.put("Banana", 200);
System.out.println(hashMap.get("Apple")); // 100

// 2. LinkedHashMap: 登録した順に並んでほしい
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("Apple", 100);
linkedMap.put("Banana", 200);
// forEachで回した時に Apple -> Banana の順で出てくる

// 3. TreeMap: キー（名前など）でソートして保持したい
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Banana", 200);
treeMap.put("Apple", 100);
// キーの辞書順（Apple -> Banana）で管理される

③ List（リスト）：順番を守る「行列」

重複OK！「何番目か」が重要な時に使います。

// 1. ArrayList: 検索に強い。基本のリスト
List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Apple"); // 重複OK
System.out.println(list.get(0)); // Apple (0番目をすぐ取れる)

// 2. LinkedList: 途中の挿入・削除に強い
List<String> linkedList = new LinkedList<>();
linkedList.add("Apple");
linkedList.add(0, "First"); // 先頭への割り込みがArrayListより効率的

4. 解決編：HashSet を使って爆速に改善（コードB）

上記３の中で今回は重複を許さないデータ構造の HashSet に変えるだけで、処理時間は数分から数ミリ秒へ劇的に改善します。

public List<String> extractUniqueProductIds(List<Order> orders) {
    // 魔法のロッカー（HashSet）を用意。これで重複チェックが $O(1)$ に！
    Set<String> uniqueSet = new HashSet<>();
    
    for (Order order : orders) {
        // addAllは内部で「重複してないやつだけ入れる」をやってくれる
        uniqueSet.addAll(order.getProductIds());
    }
    
    // 戻り値の型に合わせてListに変換して返す
    return new ArrayList<>(uniqueSet);
}

5. さいごに

今回はデータ構造について触れてみました。
私は現在デバッグチームとして仕事をする中で、保守性の高いコード・パフォーマンスを意識したコードを書くことを常々求められています。
データ構造の使い分けについてもコードレビュー時にご指導をいただくことがございました。
コードレビューの時に同じ指摘を受けるのは指導する方も受ける方にも多大なるストレスとなるはずです。
この機会にデータ構造について学び直すことで、少しでも円滑なソースレビューを受けることができる一助となれれば幸いです。

参考文献