On Fri, Jun 20, 2008 at 9:18 PM, Michael T. Richter
<ttmrichter / gmail.com> wrote:
> I have a humble suggestion to make for people who think they've solved this
> problem in O(n) time: test it.  Time it with 10 entries, 100 entries and
> 1000 entries in an array and see what happens.  If the time used doesn't
> increase roughly by an order of magnitude each time through and instead
> shoots through the roof, you're not doing O(n).

ok, no more fun :)

how about,

001:0> a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]
002:0> s=a.size
=> 5
003:0>  pr=Array.new(s){[1,1]}
=> [[1, 1], [1, 1], [1, 1], [1, 1], [1, 1]]

005:0>  (1..s-1).each do |i|
007:1*     pr[i][0]     = pr[i-1][0] * a[i-1]
008:1>    pr[s-i-1][1] = pr[s-i][1] * a[s-i]
009:1> end
=> 1..4

>  p pr.map{|x,y| x*y }
[12, 16, 24, 48, 24]


# benchmark test
botp@jedi-hopeful:~$ cat test4.rb

def ohwan(a)
  s=a.size
  pr=Array.new(s){[1,1]}
  (1..s-1).each do |i|
    pr[i][0]     = pr[i-1][0] * a[i-1]
    pr[s-i-1][1] = pr[s-i][1] * a[s-i]
  end
end

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)