【Laravel】6000秒かかる処理を100秒まで短縮した話

著者のプロフィール

・SaaSを提供している自社開発企業で開発。
・エンジニア歴3年。

今回はタイトルにもある通り、
約6000秒（1時間40分）かかる処理を100秒（1分40秒）まで縮めた話をしていきます。

結論：計算量を考慮していなかった

計算量とは？

仮に10万件を処理する場合、

O(1)の場合、計算量は1回
O(n)の場合、計算量は10万回
O(n^2)の場合、計算量は100億回

n^2になるとデータ量が増えれば増えるほど計算量が指数関数的に増えていってしまいます。

↓計算量の求め方についてはこちらの記事が分かりやすかったので載せておきます
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c

ここからLaravelのお話

LaravelにはCollectionメソッドがいくつか用意されています
普段の実装で処理速度など意識せず使用してませんか？？
小規模な開発の時は気にしなくていいと思いますが、大規模になるとそこも意識しつつ実装していかなければなりません。

↓LaravelのCollectionメソッドの計算量についてまとめられた資料はこちらになります
https://speakerdeck.com/hanhan1978/laravel-collectionfalseji-suan-liang-wodiao-betemita

今回問題になった関数はflattenです。
計算量O(n^2)

例

ソースコードを公開できないため例となりますが、
↓10万件6000秒の処理

$collection = $collection->map(function ($items)) {
    $array[] = ['hoge' => 'hogehoge'];
    $array[] = ['fuga' => 'fugafuga'];
    return $array;
})->flatten(1);

Collectionメソッドのflatten()の計算量はO(n^2)のため一度に大量データを処理すると、えげつないほど時間がかかってしまいます。
実装当初はそこまで大人数の人が使う想定ではなかったんでしょうね。。。

↓改善後

$collection->chunk(500)->each(function (Collection $chunkedCollection) {
    $collection = $chunkedCollection->map(function ($items)) {
        $array[] = ['hoge' => 'hogehoge'];
        $array[] = ['fuga' => 'fugafuga'];
        return $array;
    })->flatten(1);
});

chunkメソッドを使用して一度に処理するデータ量を減らすことで計算量をガクッと減らすことができます。

	1度の処理件数	計算量
改善前	10万件	10億
改善後	500件	25万

まとめ

今回の改善で約5900秒（1時間40秒）速度向上をすることができました。
みなさんも使用するメソッドの計算量を一度見直してみてください。