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
Code as Context 〜 1にコードで 2にリンタ 34がなくて 5にルール? 〜
yodakeisuke
0
120
A full stack side project webapp all in Kotlin (KotlinConf 2025)
dankim
0
100
AI時代のソフトウェア開発を考える(2025/07版) / Agentic Software Engineering Findy 2025-07 Edition
twada
PRO
64
20k
たった 1 枚の PHP ファイルで実装する MCP サーバ / MCP Server with Vanilla PHP
okashoi
1
230
関数型まつりレポート for JuliaTokai #22
antimon2
0
160
新メンバーも今日から大活躍!SREが支えるスケールし続ける組織のオンボーディング
honmarkhunt
3
5.8k
Team operations that are not burdened by SRE
kazatohiei
1
300
第9回 情シス転職ミートアップ 株式会社IVRy(アイブリー)の紹介
ivry_presentationmaterials
1
270
AIコーディング道場勉強会#2 君(エンジニア)たちはどう生きるか
misakiotb
1
290
Discover Metal 4
rei315
2
120
PHPでWebSocketサーバーを実装しよう2025
kubotak
0
270
ISUCON研修おかわり会 講義スライド
arfes0e2b3c
1
410
Featured
See All Featured
Making Projects Easy
brettharned
116
6.3k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.8k
Rails Girls Zürich Keynote
gr2m
94
14k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Mobile First: as difficult as doing things right
swwweet
223
9.7k
Navigating Team Friction
lara
187
15k
Thoughts on Productivity
jonyablonski
69
4.7k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.4k
Producing Creativity
orderedlist
PRO
346
40k
Facilitating Awesome Meetings
lara
54
6.4k
Done Done
chrislema
184
16k
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 :)