Listのcontainsは遅いので別の方法で高速処理を実現させる
はじめに
大きなリストに対して特定の要素が存在するか確認する処理を実装した場合、処理の実行完了までに時間を要する可能性があります。
その時の対応策を以下に記載します。
以下のコードは、CSVファイルから読み取った製品情報がDBに登録されているかを確認するサンプルです。以降はこのサンプルをもとに解説します。
/** 製品クラス。 */
public class Product {
private Long id;
public Long getId() {
return id;
}
// ...省略...
}
// CSVファイルから読み取った製品情報リスト
List<Product> productsInCsv = readCsv(file);
System.out.println(productsInCsv.size()); // 50000
// DBに登録されている製品情報リスト
List<Product> productsInDb = productRepository.findAll();
System.out.println(productsInDb.size()); // 50000
// productsInDbから製品IDリストを作成
List<Long> productIdsInDb = productsInDb.stream()
.map(Product::getId)
.collect(Collectors.toList());
// CSVファイルから読み取った製品情報毎の処理
for (Product productInCsv : productsInCsv) {
Long productIdInCsv = productInCsv.getId();
// 製品情報がDBに登録されていない場合
if (!productIdsInDb.contains(productIdInCsv)) {
// ...省略...
}
// ...省略...
}
List内の要素の検索速度
上記サンプルのproductsInCsv（CSVファイルから読み取った製品情報リスト）とproductsInDb（DBに登録されている製品情報リスト）の要素数はともに50,000の状態で実行速度を測定します。
// ...省略...
long startTime = System.currentTimeMillis();
// CSVファイルから読み取った製品情報毎の処理
for (Product productInCsv : productsInCsv) {
Long productIdInCsv = productInCsv.getId();
// 製品情報がDBに登録されていない場合
if (!productIdsInDb.contains(productIdInCsv)) { // 遅い！
}
}
long endTime = System.currentTimeMillis();
long diff = endTime - startTime;
System.out.println("time: " + diff + "ms"); // time: 2137ms
for文の処理の開始から終了までに要した時間は2000ミリ秒を超えました。
上記サンプルで時間がかかっているのは、if (!productIdsInDb.contains(productIdInCsv))の部分です。ここでは、Listのcontainsメソッドを使いリストに特定の要素が含まれるか確認しています。
ArrayListのcontainsメソッドの仕様
上記サンプルのif文中で実行されているcontainsメソッドは、内部的には、リストに含まれる要素の先頭から順に、引数の値と一致するかどうかを確認していくよう実装されています。（線形探索）
そのため、リストの先頭の方にある要素が一致する場合には時間はかかりませんが、そうでない場合には時間がかかります。
上記のサンプルのproductIdsInDbの要素が先頭から順に1, 2, 3, ... 50000となっている場合、productIdsInDb.contains(1L)の処理実行時間は短いですが、productIdsInDb.contains(50000L)の処理実行時間は長くなります。
SetまたはMap内の要素の検索速度
リストではなく、セットまたはマップを代わりに使う場合の実行速度を計測します。
セットを使用する場合のサンプルは以下の通りです。
// ...省略...
long startTime = System.currentTimeMillis();
// productsInDbから製品IDセットを作成
Set<Long> productIdsInDb = productsInDb.stream()
.map(Product::getId)
.collect(Collectors.toSet());
// productsInDbから製品IDリストを作成
for (Product productInCsv : productsInCsv) {
Long productIdInCsv = productInCsv.getId();
// 製品情報がDBに登録されていない場合
if (!productIdsInDb.contains(productIdInCsv)) { // 早い！
}
}
long endTime = System.currentTimeMillis();
long diff = endTime - startTime;
System.out.println("time: " + diff + "ms"); // time: 22ms
マップを使用する場合のサンプルは以下の通りです。
getメソッドを使い要素の有無を確認しています。containsKeyメソッドを用いて確認する方法でも構いませんが、後続処理によってはgetメソッドで要素を取得する方が良いかもしれません。
// ...省略...
long startTime = System.currentTimeMillis();
// productsInDbから製品IDをキーとするマップを作成
Map<Long, Product> productsMap = productsInDb.stream()
.collect(Collectors.toMap(Product::getId, product -> product));
// CSVファイルから読み取った製品情報毎の処理
for (Product productInCsv : productsInCsv) {
Long productIdInCsv = productInCsv.getId();
// 製品情報がDBに登録されていない場合
Product productInDb = productsMap.get(productIdInCsv); // 早い！
if (productInDb == null) {
}
}
long endTime = System.currentTimeMillis();
long diff = endTime - startTime;
System.out.println("time: " + diff + "ms"); // time: 17ms
セット・マップのインスタンスの作成からfor文の処理終了までに要した時間はどちらも30ミリ秒を下回る結果となりました。
要素数が多い場合、上記のようにセット・マップのインスタンスを作成する時間を計測時間に含めたとしても、リストを使用する場合に比べ処理は高速です。
HashMapのget(containsKey)メソッドの仕様
マップ内の要素へのアクセス処理はリストとは異なります。HashMapは内部的にはハッシュテーブルを持っており、要素を保存・取得する際にハッシュ値をもとにオブジェクトの格納先に直接アクセスします。（ハッシュ探索）
そのため、ArrayListのcontainsメソッドのように、要素によっては探し出すまでに時間がかかるといったことがありません。
この仕組みの違いが、要素数が大きくなった時に実行速度に表れています。
HashSetのcontainsメソッドの仕様
セットの要素へのアクセス処理もリストとは異なります。HashSetは内部的にはHashMapを実装しています。HashSetのcontainsメソッドを呼び出すと、メソッド内部ではHashMapのcontainsKeyメソッドが呼び出されるようになっています。
そのためマップ同様に、リストと比較してより高速に要素検索が行えるようになっています。
参考用にHashSetの内部処理を掲載します。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// ...省略...
public boolean contains(Object o) {
return map.containsKey(o);
}
}
まとめ
リスト内に特定の要素が含まれるかどうかを確認する処理を実装することになった場合、リストの代わりにセットまたはマップを利用することを検討しましょう。
要素数が多い場合、セット・マップを利用することで処理を高速化できます。
これは探索アルゴリズムの違いによるものです。
そのため、Javaに限らず、Pythonなど他のプログラミング言語でも同様です。
Discussion