Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
PHPerのための計算量入門/Complexity101 for PHPer
Search
Ryo Tomidokoro
December 22, 2024
Technology
8
2.8k
PHPerのための計算量入門/Complexity101 for PHPer
PHPカンファレンス2024の登壇資料です。
Ryo Tomidokoro
December 22, 2024
Tweet
Share
More Decks by Ryo Tomidokoro
See All by Ryo Tomidokoro
フロントエンドがTypeScriptなら、バックエンドはPHPでもいいじゃない/php-is-not-bad
hanhan1978
8
13k
どうすると生き残れないのか/how-not-to-survive
hanhan1978
17
13k
100分で本番デプロイ!Laravelで作るWebアプリケーション作成/100min_web_app_cicd
hanhan1978
1
160
集中して作業する技術/how_to_work_deeply
hanhan1978
62
49k
PHPでデータベースを作ってみた/create-data-with-php
hanhan1978
11
10k
ADRを一年運用してみた/adr_after_a_year
hanhan1978
8
4k
B+木入門:PHPで理解する データベースインデックスの仕組み/b-plus-tree-101
hanhan1978
5
5.2k
ADRを一年運用してみた/our_story_about_adr
hanhan1978
5
2.3k
PHPで学ぶ Session の基本と応用 / web-app-session-101-2024
hanhan1978
13
6k
Other Decks in Technology
See All in Technology
原則から考える保守しやすいComposable関数設計
moriatsushi
3
480
Kotlinで学ぶ 代数的データ型
ysknsid25
5
1.1k
DB 醬,嗨!哪泥嘎斯基?
line_developers_tw
PRO
0
900
マルチテナント+マルチプロダクト SaaS への AI Agent の組み込み方
kworkdev
PRO
2
400
25分で解説する「最小権限の原則」を実現するための AWS「ポリシー」大全
opelab
6
830
Rubyで作る論理回路シミュレータの設計の話 - Kashiwa.rb #12
kozy4324
1
330
TODAY 看世界(?) 是我們在看扣啦!
line_developers_tw
PRO
0
900
データプラットフォーム技術におけるメダリオンアーキテクチャという考え方/DataPlatformWithMedallionArchitecture
smdmts
3
320
Azure AI Foundryでマルチエージェントワークフロー
seosoft
0
120
ユーザーのプロフィールデータを活用した推薦精度向上の取り組み
yudai00
0
440
Navigation3でViewModelにデータを渡す方法
mikanichinose
0
150
Model Mondays S2E02: Model Context Protocol
nitya
0
150
Featured
See All Featured
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
780
Reflections from 52 weeks, 52 projects
jeffersonlam
351
20k
A Modern Web Designer's Workflow
chriscoyier
693
190k
Bash Introduction
62gerente
614
210k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
10
910
Typedesign – Prime Four
hannesfritz
42
2.7k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
357
30k
Into the Great Unknown - MozCon
thekraken
39
1.8k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Code Reviewing Like a Champion
maltzj
524
40k
Git: the NoSQL Database
bkeepers
PRO
430
65k
Faster Mobile Websites
deanohume
307
31k
Transcript
PHPerのための計算量入門 PHPカンファレンス 2024/12/22 @hanhan1978
@hanhan1978 名前 富所 亮 所属 株式会社カオナビ CTO室 BackEnd Re-architecturing Team
(BERT) Blog https://blog.hanhans.net Podcast https://podcasters.spotify.com/pod/show/yokohama-north-am 2
本トークの背景 社内ISUCONの解説で「計算量」という言葉が全く伝わらなかったので もっとわかりやすせねば!!!と決意
計算量とは?
その前に...
計算とは?
計算 [参照] アーキテクチャ: コンピュータの仕組み https://www.gsic.titech.ac.jp/matsuda/l/CS/arch/index.htm
PHPにおける計算 [参照] PHP の関数実行とその計測(記事版)https://qiita.com/sj-i/items/836fa5a5e246961c40b6
PHPにおける計算 [参照] PHP の関数実行とその計測(記事版)https://qiita.com/sj-i/items/836fa5a5e246961c40b6 ZendVM による Opcode の実行
PHPにおける計算 普段われわれが書いているPHPのソースコードも 最終的にはOpCode配列に変換され実行される
計算量とは?
コード例1 1から引数$nまでの数を足し算する関数
コード例1 ループの中で n回の足し算を計算する
コード例1 Opcode Opcode Dump (最適化後)
コード例1 Opcode Jump命令を使ったn回計算
余談 - Opcodeの出力方法 PHP 7.x 以降であれば php-cli で出力できる
余談 - Opcodeの出力方法 $ docker run -it -v `pwd`:/hoge php:8.4-cli
bash # docker-php-ext-install opcache # cd hoge # php -d opcache.enable_cli=1 \ -d opcache.opt_debug_level=0x20000 \ sample.php 10 docker 最高!
コード例2 1から引数$nまでの足し算を公式を使って計算
コード例2 nの数に依らず1行の計算
コード例2 Opcode Opcode Dump (最適化後)
コード例2 Opcode nの数によらず6行の計算
O記法 (Big-O notation) オーダー記法【ランダウの記号】O記法 IT用語辞典 e-Words https://e-words.jp/w/オーダー記法.html
O記法 (Big-O notation) 計算量の目安を表す便利な記法。 O記法での表現によって、そのアルゴリズムがどんな 時間計算量特性を持つのかを理解できる。 O(1), O(n), O(n^2), O(n*log
n) 括弧の中身が計算量のオーダーを表す
データ量と時間計算量特性の関係 [引用] 開発新卒に捧ぐ、基本のアルゴリズムと計算量 https://www.techscore.com/
コード例1 引数nに対してn回の計算 ▶ O(n)
コード例2 Nの数に依らず一定数の計算 ▶ O(1)
実測してみよう!
データ量に対する計算時間の比較
2つの計算量 時間計算量(Time Complexity) プログラムの計算の回数 空間計算量(Space Complexity) プログラムが利用するメモリ使用量
時間計算量 先程のコード例1, 2 は時間計算量比較 O(n) O(1)
空間計算量 メモリが枯渇する可能性がある
空間計算量 Bookの個数が増えると共にメモリ使用量が増える
空間計算量をチェックするには? https://www.php.net/manual/ja/function.memory-get-usage.php
空間計算量をチェックするには? https://www.php.net/manual/ja/function.memory-get-peak-usage.php
もう少し現実的なコード例から 計算量を理解してみよう
例題 とあるウェブサービスを運営する会社の社員が会員 データの分析をするためのCSVファイルを作ります。 全ユーザのデータをDatabaseから取得して、各種付帯 情報を追加してCSVファイルを作成します。
コード例(CSVファイル作成)
コードの問題は何? 仕様は満たしている、動作も問題ない ▶ しかし、データの増大と共に問題を起こす可能性がある。 負荷試験を行って、データ量と処理時間の関係を確認する。
データ件数と処理時間の関係
データ件数と処理時間の関係 計算量は O(n^2) と推定
この問題をどのように検出する? なるべく勘や経験に頼りたくはない。 何か良い方法はあるだろうか?
◎負荷試験 本番相当以上のデータ量を用意した負荷試験を行 えば、確実に検出することが可能 ただし、コアドメインじゃない限り負荷試験はコ ストがかかるので行われない…
×静的解析 PHPStan, PHPMD等は検出する対象の問題が 異なる 流石に無理...
▲経験 好きなアプローチではない 現状もっとも低コストで現実的に実行できる対策 はこれになってしまう。 研修や教育によって計算量に対して、意識を向け てもらうようにする。 今、まさにやってるコレ
◯継続的なメトリクスの確認 Mackerel, New Relic, Datadog アラートで早めに気付ければOK
時間計算量の数え方 (練習)
単純な掛け算関数
単純な掛け算関数
単純な掛け算関数 O(n)
計算量視点でコード例を改善しよう
コード例(CSVファイル作成)
コード例(CSVファイル作成)
コード例(CSVファイル作成) O(n^2)
計算量オーダーを下げる
改善例 in_array ▶ array_key_exists ※事前に $purchased_users のid, key を入れ替えておく
改善例 計算量オーダーが下がった!
処理時間を再計測
データ件数と処理時間の関係(改善後)
データ件数と処理時間の関係(改善後)
しかし、常に改善すれば良いわけではない
計算量警察 計算量視点を手に入れたエンジニアは どんな関数でも計算量を改善しようとする...
ここでデータ量と計算量オーダーの関係を 思い出そう
データ量と時間計算量特性の関係 [引用] 開発新卒に捧ぐ、基本のアルゴリズムと計算量 https://www.techscore.com/ データ量が少ない場合 どんなアルゴリズムでも計算量は少ない
良い指摘の仕方 このプログラムが処理するデータ量は3万件で す。アルゴリズムの計算量がO(N^2)なので、処理 時間に懸念があります。 ▶ 計算量を指摘する場合は想定データ量とセット!
よく使う処理の計算量
アルゴリズムと計算量 アルゴリズム 計算量 バブルソート O(n^2) マージソート O(n * log n)
バイナリーサーチ O(log n) 基本情報処理技術者試験!
配列操作関数の計算量 O(1) O(n) O(n^2) array_key_exists array_key_first array_key_last array_push array_pop array_combine
array_flip array_keys array_map array_rand array_shift array_sum array_unique array_values arsort asort in_array array + array range array_fill array_intersect array_merge 配列計算はPHPの華...
Laravel Collection 文字が小さくてゴメン
Redis
仕様変更も視野に入れる
複雑な要件を放置しない
チューニングには限界がある ビジネス要件が複雑すぎる場合... いくらアルゴリズムを調整したところで 計算量を減らす限界がある プログラムのことだけを考えても改善できない
チューニングには限界がある ビジネス要件が複雑すぎる場合... いくらアルゴリズムを調整したところで 計算量を減らす限界がある プログラムのことだけを考えても改善できない 視野を広く!
まとめ
まとめ 1. 「計算」を理解する 2. 「計算量」を理解する 3. よく使う関数の「計算量」を把握する 4. 仕様変更も視野に入れる
まとめ 1. 「計算」を理解する 2. 「計算量」を理解する 3. よく使う関数の「計算量」を把握する 4. 仕様変更も視野に入れる
まとめ 1. 「計算」を理解する 2. 「計算量」を理解する 3. よく使う処理の「計算量」を把握する 4. 仕様変更も視野に入れる
まとめ 1. 「計算」を理解する 2. 「計算量」を理解する 3. よく使う処理の「計算量」を把握する 4. 仕様変更も視野に入れる
参考書籍
数学ガール 乱択アルゴリズム 結城 浩 (2011) SoftBank Creative 第10章 乱択アルゴリズム 物語調で
理解しやすい
みんなのコンピューターサイエンス Wladston Ferreira Filho 著、小山 裕司 翻訳 (2019) 翔泳社 2.
計算量 一番簡潔
アルゴリズムと計算量 野崎昭弘 著 (1987) 共立出版 第一章 アルゴリズムと計算量 ちょっと難しい