Laravel Collectionの計算量を調べてみた2023/laravel_collection_time_complexity_2023

Laravel Verison 10 と PHP8.2 で調査しなおしました。

Transcript

1. @hanhan1978 Laravel Collectionの計算量を調べてみた 2023年度版 (非公式)PHPカンファレンス福岡 前夜祭 2023/06/23
2. @hanhan1978 • 富所 亮 • 所属 株式会社カオナビ BackEnd Re-architecturing Team (BERT) • 職業 バックエンドエンジニア • ブログ https://blog.hanhans.net • Yokohama North AM https://anchor.fm/yokohama-north-am 2
3. 2018年に発表していた内容を最新バー ジョンでやってみました
4. これの2023年版 Laravel Version 5.7
5. 計算量についておさらい 本日は時間計算量を扱います
6. https://speakerdeck.com/hanhan1978/basic-knowledge-of-space-complexity 空間計算量については、こっちのスライドを参照
7. 例えばレビューしている時
8. 「この処理遅そう」 これだと分かりにくい。 処理の時間的速度を共通知識で伝えたい
9. 英語だと Time Complexity 時間複雑性 プログラムの処理に どれくらい時間がかかるかを 数学的に扱う
10. O記法 O(1) O(log n) O(n) O(n * log n) O(n^2) プログラムの時間的計算量を表す
11. O記法 データ量が増加した場合の 処理時間の増加傾向が分かる
12. http://www.techscore.com/blog/2016/08/08/開発新卒に捧ぐ、基本のアルゴリズムと計算量 / データ量と計算量 [グラフ引用] 開発新卒に捧ぐ、基本のアルゴリズムと計算量
13. 計算量とアルゴリズム アルゴリズム 計算量 バブルソート O(n^2) マージソート O(n log n) バイナリサーチ O(log n) アルゴリズムによって計算量が異なる
14. さらに詳しく知りたい人 数学ガール4 乱択アルゴリズム 2章と6章を読むべし
15. Laravel Collection各メソッドの計算量
16. 細かすぎて見えない！
17. share しておきます https://docs.google.com/spreadsheets/d/1RbHo6huSTBkdSpWoCMRyS0E5bBvaYJdWUO3NHL VFfYg/edit?usp=sharing
18. 雑にまとめると
19. • ほとんど O(n) O(1) • O(n^2) 以上が30個
20. 要注意メソッド • crossJoin O(n^t) • diff系 O(n^t) • flat系 O(n^t) • flatten系 O(n^2) • merge系 O(n^2) • intersect系 O(n^2)
21. 実測してみた
22. where - O(n)
23. count - O(1)
24. shift - O(n^2)
25. 計算量が分かったとして 何か良いことあるのか？
26. 知らないと悪いことが起きる
27. 実際にあったかもしれない 計算量が問題になったコード例 ※実話を元にしたフィクション
28. 全件取得 ページングのために全 件ループで回す 例1
29. 全件取得 ページングのために全 件ループで回す 例1 ページの後半に行けば行くほど ループが回って遅くなる O(n)
30. 例2 第1ループで全件回す O(n) 第2ループも全件回す O(n)
31. 合わせ技 O(n^2) O(n)を入れ子にすればパワーアップ 例2 第1ループで全件回す O(n) 第2ループも全件回す O(n)
32. 例2 第1ループで全件回す O(n) 第2ループも全件回す O(n) 第一引数は最大で数百件程度だったが 第二引数のデータ数が成長していくと…
33. 事前に検知できないか？
34. 実は例１・２のコードは 単体テスト -> 通過 受け入れテスト -> 通過 通過してしまっていた…
35. データが増えないと問題にならない
36. http://www.techscore.com/blog/2016/08/08/開発新卒に捧ぐ、基本のアルゴリズムと計算量 / データ量と計算量（再掲） [グラフ引用] 開発新卒に捧ぐ、基本のアルゴリズムと計算量
37. 負荷テスト コードレビュー 事前検出可能な砦
38. 負荷テスト データ量が莫大になることが わかっているプロダクトは行っている。 通常のプロダクトだと あんまりやってるの見たこと無い。
39. コードレビュー レビュアーのスキルや経験に依存 事前に計算量について チーム内で勉強会とかしてれば 指摘＆修正は簡単だと思う
40. 監視ツールで、処理時間のメトリクスを見て 理詰めで処理時間の遅い部分を特定できれば まあ、及第点だと思う。 最悪見逃しても
41. まとめ
42. • 計算量はデータのサイジングが肝 • データ量がすくないなら、問題にならない • 過剰品質には気をつけよう！ バランスの良い判断をしよう
43. おまけ
44. 計算量が一目瞭然
45. データの集まりを扱うプログラムは 計算量を確認しましょう
46. random 8.2 で Random が改善
47. たまに、Laravel側の実装変更で思いっき り劣化することがあるので注意！ uniqueとか....
48. おしまい