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
マツコの知らない「数学」の世界
Search
h.crane
December 26, 2019
Technology
0
270
マツコの知らない「数学」の世界
マツコの知らない「数学」の世界
エンジニアとして知っておきたい計算量O(n)のお話
h.crane
December 26, 2019
Tweet
Share
More Decks by h.crane
See All by h.crane
Getting started with controlling LEGO using Swift
hcrane
0
480
Swift 5.9 と C++ の互換性
hcrane
1
310
Live on iOSDC2023
hcrane
4
1k
自販機で1000円を使い切りたいんじゃ!
hcrane
0
79
Vision.framework - 商品画像からのテキスト検出と並列化実装への試み
hcrane
1
530
DevRel/Japan 2023 - 1つの事業部だけで行う DevRel とは
hcrane
0
790
R2-D2をiOSで動かす
hcrane
2
1.4k
iOSDC2022 - SwiftUI in UIKit で開発する世界
hcrane
6
5.8k
iOSDC2022 - iPadOSDC Japan 2022
hcrane
2
3.3k
Other Decks in Technology
See All in Technology
Terraformあれやこれ/terraform-this-and-that
emiki
8
1.3k
AWS を使う上で知っておきたいオンプレミス知識/aws-on-premise-essentials
emiki
1
4.3k
Postman v10リリース後を振り返る
nagix
0
170
**強い**エンジニアのなり方 - フィードバックサイクルを勝ち取る / grow one day each day
soudai
64
18k
Tableau事例紹介 / Tableau Case Study of Eureka
kazuya_araki_tokyo
1
180
Databricks における 『MLOps』
databricksjapan
2
160
「手動オペレーションに定評がある」と言われた私が心がけていること / phpcon_odawara2024
blue_goheimochi
2
360
Compose Compiler Metricsを使った実践的なコードレビュー
tomorrowkey
1
210
プロトタイピングによる不確実性の低減 / Reducing Uncertainty through Prototyping
ohbarye
5
370
Delivering Millions of Messages within seconds @ Duolingo
pelelgrino
0
340
Discord とビルダー&チャットボットの使い方 / How to use Discord and Builder & Chatbots
ks91
PRO
0
160
MapLibreとAmazon Location Service
dayjournal
1
130
Featured
See All Featured
Designing Experiences People Love
moore
136
23k
The Straight Up "How To Draw Better" Workshop
denniskardys
227
130k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
77
42k
Embracing the Ebb and Flow
colly
79
4.1k
Building Applications with DynamoDB
mza
88
5.6k
GraphQLとの向き合い方2022年版
quramy
31
12k
Reflections from 52 weeks, 52 projects
jeffersonlam
344
19k
Design by the Numbers
sachag
274
18k
Principles of Awesome APIs and How to Build Them.
keavy
120
16k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
154
14k
Imperfection Machines: The Place of Print at Facebook
scottboms
259
12k
The World Runs on Bad Software
bkeepers
PRO
61
6.7k
Transcript
マツコの知らない「数学」の世界 〜 エンジニアとして知っておきたい計算量O(n)のお話 〜 Hiromu Tsuruta
こんな記事がバズってました
動的計画法によるDVDのディスク分割の改善
何でバズってるの?
アルゴリズムを使って実際に業務改善をしている!
・家族の「写真や動画」をDVDにして注文できる機能がある ・「写真や動画」は1枚に収まらないので複数のディスクに分割する ⇨ 「月ごとに分けて各ディスクに入れていく」というアルゴリズム 【前提】
1月の思い出 データベース 2月の思い出 3月の思い出 12月の思い出 ・・・・・ 12枚 【現状】
ディスクの枚数をもっと減らせないのか ⇨ ユーザーから問い合わせが寄せられていた 【課題】
どうやって減らす?
月ごとではなく最適化して入れる!
1月の思い出 データベース 2月の思い出 3月の思い出 12月の思い出 ・・・・・ 12枚よりは少ない 【解決例】
最適化する = データを分割する
ディスクの枚数課題を解決!
ではありません
ただ、分割すれば良いと言うものではない!
なんで?
データ分割の計算量を意識する必要がある
None
ユーザー サーバー ① アルバムの注文 ④ 注文枚数を表示 サーバー/データ ② 枚数の計算を実行 ③
計算結果を返す 〜 注文フロー 〜
計算が遅いとユーザーの画面反映も遅れる
UXの低下・機会損失
ユーザー サーバー ① アルバムの注文 ④ 注文枚数を表示 サーバー/データ ② 枚数の計算を実行 ③
計算結果を返す 〜 注文フロー 〜 この部分をなんとかしたい!
計算量を抑えました
O(MN²) から O(MN log N) まで減らし 最終的に O(NM²) までになりました (1
≦ N ≦ 10⁵, 1 ≦ M ≦ 50)
ん?
O とは?
ランダウの記号 ギリシア文字の O(オミクロン)を用いて表される 大文字をビッグオー、小文字をスモールオーと呼んだりもする 数学においてはオーダーという呼び方をする 計算量を大雑把に評価する(見積もる)際に使用する example O(n) :オーダーのエヌ O(log
n) :オーダーのログエヌ
具体例を見てみよう!
Example.1 「世界のナベアツ」
None
ナベアツは線形探索しているだけ!
線形探索とは?
・検索アルゴリズムの1つ ・リストや配列に入ったデータの検索を行う ・先頭から順に比較を行い、見つかれば終了する
「世界のナベアツ」パターン - 3の倍数 or 3が付くなら true - それ以外は false を必ず1回ずつ確認を行っている
and 40までしか探索しない
「世界のナベアツ」= O(40)
「世界のナベアツ」が 100 まで探索する場合は?
「世界のナベアツ」= O(100)
「世界のナベアツ」が n まで探索する場合は?
「世界のナベアツ」= O(n)
話を戻すと、、 結局、計算量は減ってるの? (ここから普通に数学なのでつまらなかったらすいません)
O(MN²) ⇨ O(MN log N) ⇨ O(NM²) 先の話では、、 計算量を以下の順番で減らした O(NM²)
≦ O(MN log N) ≦ O(MN²) (1 ≦ N ≦ 10⁵, 1 ≦ M ≦ 50)
全然わからん、、から 具体的な数字に落とし込んでみよう!
取りうる最大値を代入する
1 ≦ N ≦ 10⁵ 1 ≦ M ≦ 50
1 ≦ M ≦ 50 1 ≦ M ≦ 10
* 5 1 ≦ M ≦ 10 * 5 ≦ 10 * 10 Mの範囲をNに合わせて拡張する 上記のことから 1 ≦ M ≦ 10²
O(NM²) ≦ O(MN log N) ≦ O(MN²) O(MN²) ≦ O(10²
* (10⁵)²) ≦ O(10² * 10¹⁰) ≦ O(10¹²) O(MN log N) ≦ O(10² * 10⁵ * log10⁵) ≦ O(10⁷ * 10⁵) ≦ O(10¹²) O(NM²) ≦ O(10⁵ * (10²)²) ≦ O(10⁵ * 10⁴) ≦ O(10⁹) N = 10⁵, M = 10²
O(NM²) ≦ O(MN log N) ≦ O(MN²) O(10⁹) ≦ O(10¹²)
≦ O(10¹²) 10⁹ ≦ 10¹² ≦ 10¹²
確かに計算上は計算量が小さくなっている!
どうやって小さくしているの? というのはバズっていた記事にある アルゴリズムを読んでください (この資料はあくまでもO(オーダー)について説明に焦点を当てています)
fin