little problem (google hiring puzzle)

[Calamitas]

array = (1..10_000).map{rand(10_000)}
require 'benchmark'
Benchmark.bmbm do |x|
x.report("10") { ohwan(array[0,10]) }
x.report("100") { ohwan(array[0,100]) }
x.report("1_000") { ohwan(array[0,1_000]) }
x.report("10_000") { ohwan(array[0,10_000]) }
end

botp@jedi-hopeful:~$ ruby test4.rb
Rehearsal ------------------------------------------
10 0.000000 0.000000 0.000000 ( 0.000100)
100 0.000000 0.000000 0.000000 ( 0.002109)
1_000 0.020000 0.000000 0.020000 ( 0.034063)
10_000 0.330000 0.090000 0.420000 ( 0.473850)
--------------------------------- total: 0.440000sec

user system total real
10 0.000000 0.000000 0.000000 ( 0.000103)
100 0.000000 0.000000 0.000000 ( 0.000614)
1_000 0.020000 0.000000 0.020000 ( 0.029036)
10_000 0.350000 0.090000 0.440000 ( 0.519152)

Your solution looks fine. But your benchmarking will yield some weird results.

For starters, I would at least include a few more measuring points.
Now you have two significant ones as the first two are unmeasurably
small and thus useless. Through two points, you can fit pretty much
any type of curve, from sublinear to hypergeometric.

But you are likely to see widely varying results. The puzzle assumes
that multiplication is O(1). That's true for Fixnums , but not for
Bignums. Bignum multiplication is O(n.log(n)) or O(n^2) depending on
Ruby's implementation. So say your random array starts and ends with
0,then you will stay in the Fixnum range and you will measure O(n)
performance. If your random array happens to be full of numbers around
100 or so, your benchmark should show O(n^2.log(n)) or O(n^3)
behavior. To stay in the Fixnum range and get O(1) performance for
multiplication, use an array of all 0 or 1. Then you should see linear
performance. Using an array of all 100 should give predictable
results, but you should see O(n^2.log(n)) or O(n^3) behavior.

Peter

 

[Peña, Botp]

From: Calamitas [mailto:[email protected]]=20
# But you are likely to see widely varying results. The puzzle assumes
# that multiplication is O(1). That's true for Fixnums , but not for
# Bignums. Bignum multiplication is O(n.log(n)) or O(n^2) depending on
# Ruby's implementation. So say your random array starts and ends with
# 0,then you will stay in the Fixnum range and you will measure O(n)
# performance. If your random array happens to be full of numbers around
# 100 or so, your benchmark should show O(n^2.log(n)) or O(n^3)
# behavior. To stay in the Fixnum range and get O(1) performance for
# multiplication, use an array of all 0 or 1. Then you should see linear
# performance. Using an array of all 100 should give predictable
# results, but you should see O(n^2.log(n)) or O(n^3) behavior.

totally.
i tested it again by using different array values, and using a simple =
loop like,

Benchmark.bmbm do |x|
0.step(10_000,100) do |i|
x.report(i.to_s) { ohwan(array[0,i]) }
end
end

the difference is tremendous.

thank you for the enlightenment, Peter.
kind regards -botp