Actions
Misc #13209
open
fact.rb in ruby/sample variations
Status:
Open
Assignee:
-
Description
I was looking at some of the Sample files that come with Ruby and
saw the example for doing factorials. It's an old example that I
thought I could make simpler/faster. Below are the results.
Maybe upgrading to show the difference between coding idioms can
be instructive to newer Ruby programmers.
def fact(n)
return 1 if n == 0
f = 1
n.downto(1) do |i|
f *= i
end
return f
end
def fact1(n)
return 1 if n | 1 == 1 # if n 0 or 1
f = 2
n.downto(3) do |i|
f *= i
end
return f
end
def fact2(n)
return 1 if n | 1 == 1 # if n 0 or 1
(2..n).reduce(:*)
end
require 'benchmark/ips'
Benchmark.ips do |x|
x.report("original factorial") { fact 100 }
x.report("modified factorial") { fact1 100 }
x.report("enhanced factorial") { fact2 100 }
x.compare!
end
Timings using ruby-2.4.0 on Linux 64-bit, on I7 cpu system.
2.4.0 :001 > load 'factversiontest.rb'
Warming up --------------------------------------
original factorial 4.501k i/100ms
modified factorial 4.594k i/100ms
enhanced factorial 5.271k i/100ms
Calculating -------------------------------------
original factorial 44.962k (± 4.2%) i/s - 225.050k in 5.015176s
modified factorial 46.288k (± 3.2%) i/s - 234.294k in 5.066948s
enhanced factorial 53.425k (± 3.1%) i/s - 268.821k in 5.036635s
Comparison:
enhanced factorial: 53424.9 i/s
modified factorial: 46288.0 i/s - 1.15x slower
original factorial: 44961.5 i/s - 1.19x slower
=> true
2.4.0 :002 >
Updated by jzakiya (Jabari Zakiya) almost 8 years ago
Added another version using the step method, in fact3.
It's faster than using downto and neck-in-neck with using reduce as n gets bigger.
def fact(n)
return 1 if n == 0
f = 1
n.downto(1) do |i|
f *= i
end
return f
end
def fact1(n)
return 1 if n | 1 == 1 # if n 0 or 1
f = 2
n.downto(3) do |i|
f *= i
end
return f
end
def fact2(n)
return 1 if n | 1 == 1 # if n 0 or 1
(2..n).reduce(:*)
end
def fact3(n)
return 1 if n | 1 == 1 # if n 0 or 1
f = 2
3.step(n) {|i| f *= i }
f
end
require 'benchmark/ips'
Benchmark.ips do |x|
n = 100
puts "factorials tests for n = #{n}"
x.report("original factorial") { fact n }
x.report("modified factorial") { fact1 n }
x.report("enhanced factorial") { fact2 n }
x.report("withstep factorial") { fact3 n }
x.compare!
end
Here are benchmark results for various values of n.
2.4.0 :074 > load 'factversiontest.rb'
factorials tests for n = 50
Warming up --------------------------------------
original factorial 12.555k i/100ms
modified factorial 13.201k i/100ms
enhanced factorial 16.157k i/100ms
withstep factorial 15.874k i/100ms
Calculating -------------------------------------
original factorial 130.394k (± 3.0%) i/s - 652.860k in 5.011491s
modified factorial 139.530k (± 3.4%) i/s - 699.653k in 5.020706s
enhanced factorial 168.796k (± 2.9%) i/s - 856.321k in 5.077542s
withstep factorial 168.096k (± 3.8%) i/s - 841.322k in 5.012920s
Comparison:
enhanced factorial: 168795.7 i/s
withstep factorial: 168095.7 i/s - same-ish: difference falls within error
modified factorial: 139530.0 i/s - 1.21x slower
original factorial: 130394.5 i/s - 1.29x slower
=> true
2.4.0 :075 > load 'factversiontest.rb'
factorials tests for n = 70
Warming up --------------------------------------
original factorial 6.986k i/100ms
modified factorial 7.346k i/100ms
enhanced factorial 8.775k i/100ms
withstep factorial 8.729k i/100ms
Calculating -------------------------------------
original factorial 74.263k (± 4.1%) i/s - 377.244k in 5.088997s
modified factorial 77.018k (± 4.2%) i/s - 389.338k in 5.065362s
enhanced factorial 91.759k (± 3.1%) i/s - 465.075k in 5.073560s
withstep factorial 90.324k (± 3.5%) i/s - 453.908k in 5.031665s
Comparison:
enhanced factorial: 91759.4 i/s
withstep factorial: 90323.5 i/s - same-ish: difference falls within error
modified factorial: 77017.6 i/s - 1.19x slower
original factorial: 74262.9 i/s - 1.24x slower
=> true
2.4.0 :076 > load 'factversiontest.rb'
factorials tests for n = 80
Warming up --------------------------------------
original factorial 5.887k i/100ms
modified factorial 6.193k i/100ms
enhanced factorial 7.197k i/100ms
withstep factorial 7.178k i/100ms
Calculating -------------------------------------
original factorial 61.279k (± 3.4%) i/s - 306.124k in 5.001437s
modified factorial 59.091k (±17.6%) i/s - 284.878k in 5.066603s
enhanced factorial 73.394k (± 5.7%) i/s - 367.047k in 5.021211s
withstep factorial 73.323k (± 3.1%) i/s - 373.256k in 5.095652s
Comparison:
enhanced factorial: 73393.6 i/s
withstep factorial: 73323.3 i/s - same-ish: difference falls within error
original factorial: 61279.1 i/s - 1.20x slower
modified factorial: 59091.0 i/s - same-ish: difference falls within error
=> true
2.4.0 :077 > load 'factversiontest.rb'
factorials tests for n = 90
Warming up --------------------------------------
original factorial 5.058k i/100ms
modified factorial 5.269k i/100ms
enhanced factorial 6.110k i/100ms
withstep factorial 5.910k i/100ms
Calculating -------------------------------------
original factorial 52.231k (± 3.1%) i/s - 263.016k in 5.040608s
modified factorial 52.933k (± 5.0%) i/s - 268.719k in 5.090458s
enhanced factorial 62.426k (± 3.1%) i/s - 317.720k in 5.094697s
withstep factorial 61.210k (± 4.1%) i/s - 307.320k in 5.030274s
Comparison:
enhanced factorial: 62426.3 i/s
withstep factorial: 61210.0 i/s - same-ish: difference falls within error
modified factorial: 52933.4 i/s - 1.18x slower
original factorial: 52230.8 i/s - 1.20x slower
=> true
2.4.0 :078 > load 'factversiontest.rb'
factorials tests for n = 100
Warming up --------------------------------------
original factorial 4.450k i/100ms
modified factorial 4.580k i/100ms
enhanced factorial 5.259k i/100ms
withstep factorial 5.195k i/100ms
Calculating -------------------------------------
original factorial 45.211k (± 5.0%) i/s - 226.950k in 5.034319s
modified factorial 46.402k (± 3.7%) i/s - 233.580k in 5.040945s
enhanced factorial 53.148k (± 4.2%) i/s - 268.209k in 5.055701s
withstep factorial 52.588k (± 3.2%) i/s - 264.945k in 5.043348s
Comparison:
enhanced factorial: 53148.1 i/s
withstep factorial: 52588.5 i/s - same-ish: difference falls within error
modified factorial: 46401.9 i/s - 1.15x slower
original factorial: 45210.5 i/s - 1.18x slower
=> true
2.4.0 :079 > load 'factversiontest.rb'
factorials tests for n = 150
Warming up --------------------------------------
original factorial 2.699k i/100ms
modified factorial 2.759k i/100ms
enhanced factorial 3.071k i/100ms
withstep factorial 2.960k i/100ms
Calculating -------------------------------------
original factorial 27.169k (± 4.6%) i/s - 137.649k in 5.078680s
modified factorial 27.344k (± 4.7%) i/s - 137.950k in 5.056891s
enhanced factorial 30.398k (± 3.9%) i/s - 153.550k in 5.059403s
withstep factorial 29.730k (± 3.5%) i/s - 150.960k in 5.084036s
Comparison:
enhanced factorial: 30398.2 i/s
withstep factorial: 29730.3 i/s - same-ish: difference falls within error
modified factorial: 27343.9 i/s - 1.11x slower
original factorial: 27168.7 i/s - 1.12x slower
=> true
2.4.0 :080 >
Updated by jzakiya (Jabari Zakiya) almost 8 years ago
For MRI Ruby (but not JRuby) while loops are consistently faster than all
the other loop constructs (times, each, step, etc). If the goal is fastest
possible speed for MRI Ruby 3x3 it seems internals should use while loops
wherever possible.
Here, fact4 using a while loop is fastest for any value of n.
def fact(n)
return 1 if n == 0
f = 1
n.downto(1) do |i|
f *= i
end
return f
end
def fact1(n)
return 1 if n | 1 == 1 # if n 0 or 1
f = 2
n.downto(3) do |i|
f *= i
end
return f
end
def fact2(n)
return 1 if n | 1 == 1 # if n 0 or 1
(2..n).reduce(:*)
end
def fact3(n)
return 1 if n | 1 == 1 # if n 0 or 1
f = 2
3.step(n){|i| f *= i }
f
end
def fact4(n)
return 1 if n | 1 == 1 # if n 0 or 1
f, i = 2, 3
(f *= i; i += 1) while i <= n
f
end
require 'benchmark/ips'
Benchmark.ips do |x|
n = 100
puts "factorials tests for n = #{n}"
x.report("original factorial") { fact n }
x.report("modified factorial") { fact1 n }
x.report("enhanced factorial") { fact2 n }
x.report("withstep factorial") { fact3 n }
x.report("usewhile factorial") { fact4 n }
x.compare!
end
Example timings.
2.4.0 :010 > load 'factversiontest.rb'
factorials tests for n = 10
Warming up --------------------------------------
original factorial 152.621k i/100ms
modified factorial 169.295k i/100ms
enhanced factorial 124.274k i/100ms
withstep factorial 134.304k i/100ms
usewhile factorial 208.290k i/100ms
Calculating -------------------------------------
original factorial 2.074M (± 2.5%) i/s - 10.378M in 5.006297s
modified factorial 2.328M (± 2.6%) i/s - 11.681M in 5.020649s
enhanced factorial 1.623M (± 2.7%) i/s - 8.202M in 5.058125s
withstep factorial 1.736M (± 2.7%) i/s - 8.730M in 5.032241s
usewhile factorial 3.259M (± 2.8%) i/s - 16.455M in 5.052772s
Comparison:
usewhile factorial: 3259334.0 i/s
modified factorial: 2328303.5 i/s - 1.40x slower
original factorial: 2074354.4 i/s - 1.57x slower
withstep factorial: 1736091.0 i/s - 1.88x slower
enhanced factorial: 1622837.9 i/s - 2.01x slower
=> true
2.4.0 :011 > load 'factversiontest.rb'
factorials tests for n = 25
Warming up --------------------------------------
original factorial 50.369k i/100ms
modified factorial 53.391k i/100ms
enhanced factorial 56.290k i/100ms
withstep factorial 60.209k i/100ms
usewhile factorial 83.857k i/100ms
Calculating -------------------------------------
original factorial 553.152k (± 2.6%) i/s - 2.770M in 5.011731s
modified factorial 598.668k (± 2.7%) i/s - 3.043M in 5.087403s
enhanced factorial 635.598k (± 2.7%) i/s - 3.209M in 5.051865s
withstep factorial 673.752k (± 2.6%) i/s - 3.372M in 5.007842s
usewhile factorial 996.703k (± 2.6%) i/s - 5.031M in 5.051626s
Comparison:
usewhile factorial: 996703.4 i/s
withstep factorial: 673752.0 i/s - 1.48x slower
enhanced factorial: 635598.1 i/s - 1.57x slower
modified factorial: 598668.2 i/s - 1.66x slower
original factorial: 553152.2 i/s - 1.80x slower
=> true
2.4.0 :012 > load 'factversiontest.rb'
factorials tests for n = 50
Warming up --------------------------------------
original factorial 13.772k i/100ms
modified factorial 14.688k i/100ms
enhanced factorial 17.696k i/100ms
withstep factorial 17.501k i/100ms
usewhile factorial 21.318k i/100ms
Calculating -------------------------------------
original factorial 142.356k (± 3.0%) i/s - 716.144k in 5.035290s
modified factorial 152.404k (± 3.0%) i/s - 763.776k in 5.016154s
enhanced factorial 183.865k (± 2.8%) i/s - 920.192k in 5.008924s
withstep factorial 182.771k (± 2.7%) i/s - 927.553k in 5.078797s
usewhile factorial 222.403k (± 3.0%) i/s - 1.130M in 5.085087s
Comparison:
usewhile factorial: 222402.7 i/s
enhanced factorial: 183865.0 i/s - 1.21x slower
withstep factorial: 182770.6 i/s - 1.22x slower
modified factorial: 152404.0 i/s - 1.46x slower
original factorial: 142355.6 i/s - 1.56x slower
=> true
2.4.0 :013 > load 'factversiontest.rb'
factorials tests for n = 100
Warming up --------------------------------------
original factorial 4.933k i/100ms
modified factorial 4.976k i/100ms
enhanced factorial 5.752k i/100ms
withstep factorial 5.607k i/100ms
usewhile factorial 6.060k i/100ms
Calculating -------------------------------------
original factorial 49.084k (± 2.9%) i/s - 246.650k in 5.029407s
modified factorial 49.886k (± 3.4%) i/s - 253.776k in 5.093179s
enhanced factorial 54.025k (± 8.1%) i/s - 270.344k in 5.044646s
withstep factorial 53.487k (± 4.3%) i/s - 269.136k in 5.041225s
usewhile factorial 58.795k (± 9.2%) i/s - 296.940k in 5.096755s
Comparison:
usewhile factorial: 58794.8 i/s
enhanced factorial: 54024.6 i/s - same-ish: difference falls within error
withstep factorial: 53486.8 i/s - same-ish: difference falls within error
modified factorial: 49885.7 i/s - 1.18x slower
original factorial: 49084.0 i/s - 1.20x slower
=> true
2.4.0 :014 >
Actions
Like0
Like0Like0