Look ma' I know my algorithms!

RubyConf Argentina 2014

Transcript

1. Look ma’, I know my algorithms!
2. Lucia Escanellas raviolicode
3. 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
4. Speed Speed
5. Zen Elegance Elegance
6. Toolbox
7. Theory Theory
8. This example Not so common
9. FROM >30HS TO 18 S
10. WHY USE ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
11. WHY USE ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
12. WHY USING ORDERS? ALGORITHMS ARE POWERFUL AVOID TRAPS IN RUBY
13. Let’s have a look at the PROBLEM
14. Ordered array How many pairs (a,b) where a ≠ b -100 <= a + b <= 100
15. Array: [-100, 1, 100]
16. Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100)
17. Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100) -100 + 1 = 99 YES
18. Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100) -100 + 100 = 0 YES
19. Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100) 1 + 100 = 101 NO
20. Array: [-100, 1, 100] (-100, 1), (-100, 100), (1, 100) Result: 2
21. First solution Combinations of 2 elements Filter by: -100 <= a + b <= 100
22. def count! combinations = @numbers.combination(2).to_a! ! combinations! .map{ |a,b| a + b }! .select do |sum|! sum.abs <= THRESHOLD! end.size! end
23. 10K takes 10s BUT 100M takes 30hs
24. Time to buy a NEW LAPTOP!
25. Big O notation How WELL an algorithm SCALES as the DATA involved INCREASES
26. Calc Array size (length=N) Count elements one by one: O(N)
27. Calc Array size (length=N) Count elements one by one: O(N) Length stored in variable: O(1)
28. Graphical Math Properties Order Mathematical Properties
29. Remember: f < g => O(f + g) = O(g) O(K . f) = O(f) O(1) < O(ln N) < O(N) < O(N2) < O(eN)
30. 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
31. ! 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
32. Ex: Binary Search Worst case: ceil ( Log2 N ) 23 = 8 ONLY 3 steps
33. Typical examples Access to a Hash O(1) Binary search O(log N) Sequential search O(N) Traverse a matrix NxN O(N2)
34. DON’T JUST BELIEVE ME fooplot.com
35. BUT raviolicode, I’m getting BORED
36. I WANT CONCURRENCY I WANT CONCURRENCY
37. wait… was it Concurrency? or Parallelism?
44. GIL+CPU-bound NO I/O OPERATIONS concurrency = OVERHEAD
45. NOT what I was expecting
46. Parallelism... Parallelism
48. What do we REALLY get? O(N2 / cores) = O(N 2 ) jRubyGo Scala
49. NO Spoilers O(N2) O(N.log(N)) O(N)
50. THINKING algorithms is as IMPORTANT as ANY OTHER technique
51. BYE.
52. Wait! It's still slow. Wait! It’s still SLOW
53. Given [1,2,3,4,5] Take 1, then print [5,4,3,2] Take 2, then print [5,4,3] and so on…
54. What’s the ORDER of this code? @nums.each_with_index do |a,i|! ! puts @nums.slice(i+1,N).reverse! .inspect! end
55. 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)
56. 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)
57. Let’s Look at the DOCS Ruby-Doc.org ! #reverse
58. O(N) hidden! O(N)!
59. 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)!
60. Leaky abstractions LEAKY ABSTRACTIONS
61. All Non-trivial abstractions are LEAKY to some degree
62. ABSTRACTIONS DO NOT really SIMPLIFY as they were meant to
63. Knowing THE ALGORITHMS Behind everyday methods PAYS OFF
64. Thanks :) Thanks :)