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.4k
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
17
13k
100分で本番デプロイ!Laravelで作るWebアプリケーション作成/100min_web_app_cicd
hanhan1978
1
110
集中して作業する技術/how_to_work_deeply
hanhan1978
62
48k
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
5.1k
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
Writing Ruby Scripts with TypeProf
mame
0
110
ワールドカフェI /チューターを改良する / World Café I and Improving the Tutors
ks91
PRO
0
120
バックオフィス向け toB SaaS バクラクにおけるレコメンド技術活用 / recommender-systems-in-layerx-bakuraku
yuya4
6
540
Running JavaScript within Ruby
hmsk
3
330
20250413_湘南kaggler会_音声認識で使うのってメルス・・・なんだっけ?
sugupoko
1
480
Mastraに入門してみた ~AWS CDKを添えて~
tsukuboshi
0
230
SnowflakeとDatabricks両方でRAGを構築してみた
kameitomohiro
1
330
AWSで作るセキュアな認証基盤with OAuth mTLS / Secure Authentication Infrastructure with OAuth mTLS on AWS
kaminashi
0
150
新卒エンジニアがCICDをモダナイズしてみた話
akashi_sn
2
230
Porting PicoRuby to Another Microcontroller: ESP32
yuuu
4
410
3月のAWSアップデートを5分間でざっくりと!
kubomasataka
0
120
Amazon S3 Tables + Amazon Athena / Apache Iceberg
okaru
0
270
Featured
See All Featured
The MySQL Ecosystem @ GitHub 2015
samlambert
251
12k
Automating Front-end Workflow
addyosmani
1369
200k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
160
15k
Raft: Consensus for Rubyists
vanstee
137
6.9k
RailsConf 2023
tenderlove
30
1.1k
Faster Mobile Websites
deanohume
306
31k
Navigating Team Friction
lara
184
15k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
390
Statistics for Hackers
jakevdp
798
220k
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) 共立出版 第一章 アルゴリズムと計算量 ちょっと難しい