setのinを使ったパフォーマンスチューニング

実務の中で any によるループ検索を Set ＋ in演算子を使って計算量を減らすリファクタを行いました。 知識の定着を目的としたアウトプットとして記事を書きます。

削除処理のリファクタ前

any によるループ検索と、mutableListOf を使った手続き的な書き方です。データ量が増えると計算量が O(N * M) になる懸念あり。 localItemsの要素数がM、targetDataSetの要素数がNとすると、最大M × N（計算量O(M × N)）となります。MとNが10000と10000だとすると1億となります。

// 外部システムで削除済みのデータがあれば、ローカルからも削除する
if (targetDeleteSet.isNotEmpty()) {
    val itemIds = mutableListOf<String>()
    
    localItems.forEach { localItem ->
        // 削除対象の「種別」と「識別子」が一致した場合は削除リストに追加
        if (targetDeleteSet.any { it.first == localItem.type && it.second == localItem.identifier }) {
            itemIds.add(localItem.id)
        }
    }
    
    dataService.deleteItems(itemIds)
}

削除処理のリファクタ後

改善案として Setの検索速度を活かして検索を行います。 今回のtargetDeleteSetは 「Set<Pair<String, String>>」なので、その要素が含まれているかin 演算子を使って検索をすることで計算量を O(1) にできます。 Setやハッシュ化についてはこちらの記事が参考になると思うので、置いておきます。 ①Setにデータ登録する時

• Pair("TypeA", "001") -> ハッシュ値：123
• Pair("TypeB", "002") -> ハッシュ値：456
• Pair("TypeC", "003") -> ハッシュ値：789

②Setからデータを検索するとき

1. カギのハッシュ値を計算する。検索する値が「Pair("TypeB", "002")」の場合、計算結果は 456 になります。
2. anyの場合は1か順番に探していた処理を、直接 456 という場所を探しにいきます。
3. 結果を返す。見つかったなら true、見つからないのであれば false

エンジニア実践的基礎: ハッシュマップ/セット

また forEachを使ってループ処理していた箇所もmapNotNullを使った実装に改修しました。 forEachは外に用意していたitemIdsという変数を準備しなければいけなく、可読性も悪いです。Kotlin の forEach は可読性を下げるにるように今回はデータの検索しヒットしたらデータの変換を行うことが目的なので mapNotNullを使います。mapNotNullを使うことにより、外側に空の変数を置く必要もなく、要素を別の形に変換しながら可読性も上げることができました。

/**
 * 外部システムで削除されたデータがある場合、ローカルの該当データを削除する
 */
private fun syncDeletedItems(
    targetDeleteSet: Set<Pair<String, String>>,
    localItems: List<LocalItem>
) {
    if (targetDeleteSet.isEmpty()) return

    // 削除対象のキー（ペア）を作成し、Setに含まれているか O(1) で確認
    val targetItemIds = localItems.mapNotNull { item ->
        val itemKey = Pair(item.type, item.identifier)
        
        // 条件に一致すればIDを返し、そうでなければnull（除外）
        if (itemKey in targetDeleteSet) item.id else null
    }

    if (targetItemIds.isNotEmpty()) {
        dataService.deleteItems(targetItemIds)
    }
}

更新処理のリファクタ前

こちらも悪いところが any によるループ検索を行っています。

// ローカルに未登録のデータがあれば新規作成
if (targetCreateSet.isNotEmpty()) {
    remoteItems.forEach { remoteItem ->
        // 作成対象の「種別」と「識別子」が一致した場合はデータを作成する
        if (targetCreateSet.any { it.first == remoteItem.type && it.second == remoteItem.identifier }) {
            dataService.createItem(
                parentId = parentId,
                type = remoteItem.type,
                identifier = remoteItem.identifier
            )
        }
    }
}

更新処理のリファクタ後

filterで対象物を絞り込んでから forEachで更新処理を回す構成に改修しました。 こちらも Setの in演算子を使い計算量を O(1) にしているところがポイントです。

/**
 * 外部システムに存在し、ローカルに未登録のデータがある場合、新規作成する
 */
private fun syncNewItems(
    parentId: String,
    targetCreateSet: Set<Pair<String, String>>,
    remoteItems: List<RemoteItem>
) {
    if (targetCreateSet.isEmpty()) return

    remoteItems.filter { remoteItem ->
        // 検索用のキーを作成し、作成対象か判定
        val itemKey = Pair(remoteItem.type, remoteItem.identifier)
        itemKey in targetCreateSet
    }.forEach { targetItem ->
        // 絞り込まれた対象に対して作成処理を実行
        dataService.createItem(
            parentId = parentId,
            type = targetItem.type,
            identifier = targetItem.identifier
        )
    }
}