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
Look ma' I know my algorithms!
Search
Lucia Escanellas
October 24, 2014
Programming
7
460
Look ma' I know my algorithms!
RubyConf Argentina 2014
Lucia Escanellas
October 24, 2014
Tweet
Share
Other Decks in Programming
See All in Programming
dbt民主化とLLMによる開発ブースト ~ AI Readyな分析サイクルを目指して ~
yoshyum
3
1.1k
Hack Claude Code with Claude Code
choplin
7
2.5k
Google Agent Development Kit でLINE Botを作ってみた
ymd65536
2
260
TypeScriptでDXを上げろ! Hono編
yusukebe
3
770
Advanced Micro Frontends: Multi Version/ Framework Scenarios @WAD 2025, Berlin
manfredsteyer
PRO
0
390
DMMを支える決済基盤の技術的負債にどう立ち向かうか / Addressing Technical Debt in Payment Infrastructure
yoshiyoshifujii
3
410
MDN Web Docs に日本語翻訳でコントリビュートしたくなる
ohmori_yusuke
1
130
脱Riverpod?fqueryで考える、TanStack Queryライクなアーキテクチャの可能性
ostk0069
0
500
Rails Frontend Evolution: It Was a Setup All Along
skryukov
0
280
Flutterで備える!Accessibility Nutrition Labels完全ガイド
yuukiw00w
0
170
猫と暮らす Google Nest Cam生活🐈 / WebRTC with Google Nest Cam
yutailang0119
0
170
The Evolution of Enterprise Java with Jakarta EE 11 and Beyond
ivargrimstad
0
260
Featured
See All Featured
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
31
1.3k
Navigating Team Friction
lara
187
15k
Java REST API Framework Comparison - PWX 2021
mraible
31
8.7k
4 Signs Your Business is Dying
shpigford
184
22k
Stop Working from a Prison Cell
hatefulcrawdad
271
21k
GraphQLとの向き合い方2022年版
quramy
49
14k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
18
990
Site-Speed That Sticks
csswizardry
10
700
Git: the NoSQL Database
bkeepers
PRO
430
65k
Transcript
Look ma’, I know my algorithms!
Lucia Escanellas raviolicode
Attributions https://flic.kr/p/6DDvQP https://flic.kr/p/qv5Zp https://flic.kr/p/6SaZsP https://flic.kr/p/edauSN https://flic.kr/p/4uNfK8 https://flic.kr/p/o9ggdk https://flic.kr/p/6kfuHz https://flic.kr/p/5kBtbS
Speed Speed
Zen Elegance Elegance
Toolbox
Theory Theory
This example Not so common
FROM >30HS TO 18 S
WHY USE ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
WHY USE ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
WHY USING ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
Let’s have a look at the PROBLEM
Ordered array How many pairs (a,b) where a ≠ b
-100 <= a + b <= 100
Array: [-100, 1, 100]
Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
-100 + 1 = 99 YES
Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
-100 + 100 = 0 YES
Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
1 + 100 = 101 NO
Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
Result: 2
First solution Combinations of 2 elements Filter by: -100 <=
a + b <= 100
def count! combinations = @numbers.combination(2).to_a! ! combinations! .map{ |a,b| a
+ b }! .select do |sum|! sum.abs <= THRESHOLD! end.size! end
10K takes 10s BUT 100M takes 30hs
Time to buy a NEW LAPTOP!
Big O notation How WELL an algorithm SCALES as the
DATA involved INCREASES
Calc Array size (length=N) Count elements one by one: O(N)
Calc Array size (length=N) Count elements one by one: O(N)
Length stored in variable: O(1)
Graphical Math Properties Order Mathematical Properties
Remember: f < g => O(f + g) = O(g)
O(K . f) = O(f) O(1) < O(ln N) < O(N) < O(N2) < O(eN)
Ex: Binary Search Find 7 in [1, 2, 3, 4,
5, 6, 7, 8] 1. element in the middle is 5 2. 5 == 7 ? NO 3. 5 < 7 ? YES => Find 7 in [6, 7, 8] Step 1
! Find 7 in [0, 1, 2, 3, 4, 5,
6, 7, 8] 1. element in the middle is 7 2. 7 == 7 ? YES! FOUND IT!! Step 2
Ex: Binary Search Worst case: ceil ( Log2 N )
23 = 8 ONLY 3 steps
Typical examples Access to a Hash O(1) Binary search O(log
N) Sequential search O(N) Traverse a matrix NxN O(N2)
DON’T JUST BELIEVE ME fooplot.com
BUT raviolicode, I’m getting BORED
I WANT CONCURRENCY I WANT CONCURRENCY
wait… was it Concurrency? or Parallelism?
None
None
None
None
None
None
GIL+CPU-bound NO I/O OPERATIONS concurrency = OVERHEAD
NOT what I was expecting
Parallelism... Parallelism
None
What do we REALLY get? O(N2 / cores) = O(N
2 ) jRubyGo Scala
NO Spoilers O(N2) O(N.log(N)) O(N)
THINKING algorithms is as IMPORTANT as ANY OTHER technique
BYE.
Wait! It's still slow. Wait! It’s still SLOW
Given [1,2,3,4,5] Take 1, then print [5,4,3,2] Take 2, then
print [5,4,3] and so on…
What’s the ORDER of this code? @nums.each_with_index do |a,i|! !
puts @nums.slice(i+1,N).reverse! .inspect! end
What’s the ORDER of this code? @nums.each_with_index do |a,i|! !
puts @nums.slice(i+1,N).reverse! .inspect! end Looks like O(N)
What’s the ORDER of this code? @nums.each_with_index do |a,i|! !
puts @nums.slice(i+1,N).reverse! .inspect! end Behaves like O(N2)
Let’s Look at the DOCS Ruby-Doc.org ! #reverse
O(N) hidden! O(N)!
What’s the ORDER of this code? @nums.each_with_index do |a,i|! !
puts @nums.slice(i+1,N).reverse! .inspect! end O(N2)!
Leaky abstractions LEAKY ABSTRACTIONS
All Non-trivial abstractions are LEAKY to some degree
ABSTRACTIONS DO NOT really SIMPLIFY as they were meant to
Knowing THE ALGORITHMS Behind everyday methods PAYS OFF
Thanks :) Thanks :)