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
6
2.3k
PHPerのための計算量入門/Complexity101 for PHPer
PHPカンファレンス2024の登壇資料です。
Ryo Tomidokoro
December 22, 2024
Tweet
Share
More Decks by Ryo Tomidokoro
See All by Ryo Tomidokoro
どうすると生き残れないのか/how-not-to-survive
hanhan1978
16
12k
100分で本番デプロイ!Laravelで作るWebアプリケーション作成/100min_web_app_cicd
hanhan1978
1
98
集中して作業する技術/how_to_work_deeply
hanhan1978
62
47k
PHPでデータベースを作ってみた/create-data-with-php
hanhan1978
11
9.9k
ADRを一年運用してみた/adr_after_a_year
hanhan1978
8
3.9k
B+木入門:PHPで理解する データベースインデックスの仕組み/b-plus-tree-101
hanhan1978
5
5k
ADRを一年運用してみた/our_story_about_adr
hanhan1978
5
2.2k
PHPで学ぶ Session の基本と応用 / web-app-session-101-2024
hanhan1978
13
5.8k
レガシー回避のPHP開発術/avoid_php_legacy
hanhan1978
17
13k
Other Decks in Technology
See All in Technology
Cline、めっちゃ便利、お金が飛ぶ💸
iwamot
19
18k
Dapr For Java Developers SouJava 25
salaboy
1
130
大規模アジャイル開発のリアル!コミュニケーション×進捗管理×高品質
findy_eventslides
0
490
PostgreSQL Unconference #52 pg_tde
nori_shinoda
0
190
スケールアップ企業のQA組織のバリューを最大限に引き出すための取り組み
tarappo
4
920
Riverpod & Riverpod Generatorを利用して状態管理部分の処理を書き換えてみる簡単な事例紹介
fumiyasac0921
0
100
LINEギフトのLINEミニアプリアクセシビリティ改善事例
lycorptech_jp
PRO
0
240
BCMathを高速化した一部始終をC言語でガチ目に解説する / BCMath performance improvement explanation
sakitakamachi
2
1.2k
20250328_OpenAI製DeepResearchは既に一種のAGIだと思う話
doradora09
PRO
0
150
SSH公開鍵認証による接続 / Connecting with SSH Public Key Authentication
kaityo256
PRO
2
220
Engineering Managementのグローバルトレンド #emoasis / Engineering Management Global Trend
kyonmm
PRO
6
980
グループポリシー再確認
murachiakira
0
160
Featured
See All Featured
Building Your Own Lightsaber
phodgson
104
6.3k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
40
2k
Six Lessons from altMBA
skipperchong
27
3.7k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.2k
Embracing the Ebb and Flow
colly
85
4.6k
Designing for humans not robots
tammielis
250
25k
GraphQLとの向き合い方2022年版
quramy
45
14k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Designing for Performance
lara
606
69k
The Pragmatic Product Professional
lauravandoore
33
6.5k
The Language of Interfaces
destraynor
157
24k
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) 共立出版 第一章 アルゴリズムと計算量 ちょっと難しい