public
Last active

Playing with "prior knowledge" and value caching for potentially expensive operations.

  • Download Gist
00_prior_knowledge.rb
Ruby
1 2
FACT=Hash.new{|h,i|i<0?nil:h[i]=i*h[i-1]}; FACT[0]=1
FACT[13] #=> 6227020800
01_benchmarking.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
require 'timestamp'
def simple_bench t=nil, &b
print "#{t}: " if t
a = Time::timestamp
yield
b = Time::timestamp
puts "#{b-a} ns"
end
 
FACT=Hash.new{|h,i|i<0?nil:h[i]=i*h[i-1]}; FACT[0]=1
def fact(i)i<0?nil:(i==0?1:i*fact(i-1));end
 
puts '','First run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fact(50) }
 
puts '','Second run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fact(50) }
 
puts '','Third run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fact(50) }
 
puts '', 'Many times:'
simple_bench('Hash') { 1000.times{FACT[50]} }
simple_bench('Func') { 1000.times{fact(50)} }
 
### New func, with more prior knowledge
puts '','=== MORE PRIOR KNOWLEDGE ==='
 
def fac2(i)
return nil if i<0
case i
when 20; 2432902008176640000
when 19; 121645100408832000
when 18; 6402373705728000
when 17; 355687428096000
when 16; 20922789888000
when 15; 1307674368000
when 14; 87178291200
when 13; 6227020800
when 12; 479001600
when 11; 39916800
when 10; 3628800
when 9; 362880
when 8; 40320
when 7; 5040
when 6; 720
when 5; 120
when 4; 24
when 3; 6
when 2; 2
when 1; 1
when 0; 1
else; i * fact(i-1)
end
end
 
FACT.replace( Hash.new{|h,i|i<0?nil:h[i]=i*h[i-1]} ); FACT[0]=1
 
puts '','First run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac2(50) }
 
puts '','Second run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac2(50) }
 
puts '','Third run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac2(50) }
 
puts '', 'Many times:'
simple_bench('Hash') { 1000.times{FACT[50]} }
simple_bench('Func') { 1000.times{fac2(50)} }
 
### New func, with EVEN more prior knowledge
puts '','=== EVEN MORE PRIOR KNOWLEDGE ==='
 
def fac3(i)
return nil if i<0
case i
when 50; 30414093201713378043612608166064768844377641568960512000000000000
when 49; 608281864034267560872252163321295376887552831379210240000000000
when 48; 12413915592536072670862289047373375038521486354677760000000000
when 47; 258623241511168180642964355153611979969197632389120000000000
when 46; 5502622159812088949850305428800254892961651752960000000000
when 45; 119622220865480194561963161495657715064383733760000000000
when 44; 2658271574788448768043625811014615890319638528000000000
when 43; 60415263063373835637355132068513997507264512000000000
when 42; 1405006117752879898543142606244511569936384000000000
when 41; 33452526613163807108170062053440751665152000000000
when 40; 815915283247897734345611269596115894272000000000
when 39; 20397882081197443358640281739902897356800000000
when 38; 523022617466601111760007224100074291200000000
when 37; 13763753091226345046315979581580902400000000
when 36; 371993326789901217467999448150835200000000
when 35; 10333147966386144929666651337523200000000
when 34; 295232799039604140847618609643520000000
when 33; 8683317618811886495518194401280000000
when 32; 263130836933693530167218012160000000
when 31; 8222838654177922817725562880000000
when 30; 265252859812191058636308480000000
when 29; 8841761993739701954543616000000
when 28; 304888344611713860501504000000
when 27; 10888869450418352160768000000
when 26; 403291461126605635584000000
when 25; 15511210043330985984000000
when 24; 620448401733239439360000
when 23; 25852016738884976640000
when 22; 1124000727777607680000
when 21; 51090942171709440000
when 20; 2432902008176640000
when 19; 121645100408832000
when 18; 6402373705728000
when 17; 355687428096000
when 16; 20922789888000
when 15; 1307674368000
when 14; 87178291200
when 13; 6227020800
when 12; 479001600
when 11; 39916800
when 10; 3628800
when 9; 362880
when 8; 40320
when 7; 5040
when 6; 720
when 5; 120
when 4; 24
when 3; 6
when 2; 2
when 1; 1
when 0; 1
else; i * fact(i-1)
end
end
 
FACT.replace( Hash.new{|h,i|i<0?nil:h[i]=i*h[i-1]} ); FACT[0]=1
 
puts '','First run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac3(50) }
 
puts '','Second run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac3(50) }
 
puts '','Third run:'
simple_bench('Hash') { FACT[50] }
simple_bench('Func') { fac3(50) }
 
puts '', 'Many times:'
simple_bench('Hash') { 1000.times{FACT[50]} }
simple_bench('Func') { 1000.times{fac3(50)} }
02_benchmarking.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
$ ruby2.0 -v prior_knowledge.rb
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-linux]
 
First run:
Hash: 68722 ns
Func: 15923 ns
 
Second run:
Hash: 6146 ns
Func: 13968 ns
 
Third run:
Hash: 5866 ns
Func: 13409 ns
 
Many times:
Hash: 79337 ns
Func: 9031057 ns
 
=== MORE PRIOR KNOWLEDGE ===
 
First run:
Hash: 92467 ns
Func: 19275 ns
 
Second run:
Hash: 6146 ns
Func: 15086 ns
 
Third run:
Hash: 7263 ns
Func: 16482 ns
 
Many times:
Hash: 144987 ns
Func: 9419922 ns
 
=== EVEN MORE PRIOR KNOWLEDGE ===
 
First run:
Hash: 42742 ns
Func: 6705 ns
 
Second run:
Hash: 5308 ns
Func: 5308 ns
 
Third run:
Hash: 5308 ns
Func: 5867 ns
 
Many times:
Hash: 70957 ns
Func: 112302 ns

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.