# How this looks?
def prod_all_but_me(a)
na = a.size
v = 1
ea = Array.new(na){ |i| [v,v*=a[na-i-1]][0] }
v = 1
Array.new(na){ |i| [v*ea[na-i-1],v*=a[i]][0] }
end
# array size
n = (ARGV[0]||5).to_i
# INPUT (random array)
a = (1..n).to_a.sort_by{ rand }
p a
# OUTPUT
p prod_all_but_me(a)
On Jun 16, 10:25 pm, ex <exeQ...@gmail.com> wrote:
I wasn't aware of the unshift overload, here I think I got O(n),
however this looks more like C++ than ruby imho:
Yeah, the challenge is that to insure O(n) you have to use just the
basic Array operations removing some of the Ruby tricks from your
toolbox. Sometimes other constraints dominate, and there's not a
whole lot you can do. But I agree with you that your second solution
is O(n).
By the way, in case it wasn't clear, the problem with Array#unshift is
that by inserting at the beginning of the array, it likely requires
that all other elements to need to shift up by one, making it O(n).
Pushing onto the end of the array is likely O(1). And, Array#reverse
(and Array#reverse!) are likely O(n). So one way around the problem
is to create the array in the "wrong" direction and the reverse it.
I don't think that this solution has all the Ruby niceness, but I'm
pretty sure it's O(n):
On Jun 16, 10:25 pm, ex <exeQ...@gmail.com> wrote:
I wasn't aware of the unshift overload, here I think I got O(n),
however this looks more like C++ than ruby imho.
====
vals = [4, 3, 2, 1, 2]
forward_prods = [1]
0.upto(vals.size - 2) do |i|
forward_prods << forward_prods.last * vals[i]
end
backward_prods = [1]
(vals.size - 1).downto(1) do |i|
backward_prods << backward_prods.last * vals[i]
end
backward_prods.reverse!
answer = forward_prods.zip(backward_prods).map { |f, b| f * b }
p answer
====
Best,
Eric
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ready for Rails Ruby Workshop June 23-24 Ann Arbor, Mich.
Ruby on Rails Workshop June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Workshop June 23-27 Ann Arbor, Mich.
Please visit http://LearnRuby.com for all the details.
Each eval is O(n-1). You do n of them.
I think eval I used in this case is constant time. Any other views?
--
Posted via http://www.ruby-forum.com/\.
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)
On Fri, Jun 20, 2008 at 9:18 PM, Michael T. Richter <ttmrichter@gmail.com> wrote:
I'm guessing it's linear, but I may well be wrong.
There appears to be another minor complication. If one increases the
size of vals
vals *= 200
one gets an error: `Integer': Infinity (FloatDomainError)
its ugly, could be written in any language, but it works and should be
O(n).
def products input
li, ri, prod_left, prod_right = 0, input.length - 1, 1, 1
res = Array.new(input.length, 1)
while (li < input.length)
prod_left = prod_left * (li != 0 ? input[li - 1] : 1)
prod_right = prod_right * (ri != (input.length - 1) ? input[ri + 1] : 1)
res[li] *= prod_left
res[ri] *= prod_right
li += 1
ri -= 1
end
res
end
cheers
simon
On Tue, Jun 17, 2008 at 6:44 AM, Eric I. <rubytraining@gmail.com> wrote:
On Jun 16, 10:25 pm, ex <exeQ...@gmail.com> wrote:
> I wasn't aware of the unshift overload, here I think I got O(n),
> however this looks more like C++ than ruby imho.Yeah, the challenge is that to insure O(n) you have to use just the
basic Array operations removing some of the Ruby tricks from your
toolbox. Sometimes other constraints dominate, and there's not a
whole lot you can do. But I agree with you that your second solution
is O(n).By the way, in case it wasn't clear, the problem with Array#unshift is
that by inserting at the beginning of the array, it likely requires
that all other elements to need to shift up by one, making it O(n).
Pushing onto the end of the array is likely O(1). And, Array#reverse
(and Array#reverse!) are likely O(n). So one way around the problem
is to create the array in the "wrong" direction and the reverse it.I don't think that this solution has all the Ruby niceness, but I'm
pretty sure it's O(n):====
vals = [4, 3, 2, 1, 2]
forward_prods = [1]
0.upto(vals.size - 2) do |i|
forward_prods << forward_prods.last * vals[i]
endbackward_prods = [1]
(vals.size - 1).downto(1) do |i|
backward_prods << backward_prods.last * vals[i]
end
backward_prods.reverse!answer = forward_prods.zip(backward_prods).map { |f, b| f * b }
p answer
====
Best,
Eric
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ready for Rails Ruby Workshop June 23-24 Ann Arbor, Mich.
Ruby on Rails Workshop June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Workshop June 23-27 Ann Arbor, Mich.
Please visit http://LearnRuby.com for all the details.
Correct me if I am wrong, but it seems like when you use the range operator:
input[0...index] + input[index+1..-1]
Isn't it basically just iterating over the list and yielding? In which
case, your original loop:
input.each_index do |index|
odd_man_out = input[0...index] + input[index+1..-1]
starry_night = odd_man_out.join('*')
output << eval(starry_night)
end
will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)
My thoughts...
J
On Thu, Jun 19, 2008 at 2:45 PM, Ragunathan Pattabiraman <ragunathan.pattabiraman@gmail.com> wrote:
Each eval is O(n-1). You do n of them.
I think eval I used in this case is constant time. Any other views?
--
Posted via http://www.ruby-forum.com/\.
You are evaluating a product of n-1 terms in each eval.
eval(3*2*1*2)
eval(4*2*1*2)
eval(4*3*1*2)
eval(4*3*2*2)
eval(4*3*2*1)
There is no way to optimize these multiplications away.
Ray
On Jun 19, 2:15 am, Ragunathan Pattabiraman <ragunathan.pattabira...@gmail.com> wrote:
> Each eval is O(n-1). You do n of them.
I think eval I used in this case is constant time. Any other views?
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
On Fri, Jun 20, 2008 at 6:52 PM, botp <botpena@gmail.com> wrote:
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]) }
endbotp@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.440000secuser 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)
Well, to be fair,
1771117911399122021943501576570463920868438730355453249145726540660962310694485994703406981661443989507309617613625154922865835810313868152815318277751521931338734019325348671637367964185869331777657562542031550576686039535823298586722498517733604903356381988668531963257069336339415675144908390480164171374292523565379769479171592421376
is probably outside the scope of the domain of integers considered by Google when setting the problem, but it's an interesting exercise to see how to scale the log sum, do the work, then scale the answers back. It's still O(N) in that case...
Dave
On Jun 15, 2008, at 3:29 PM, ThoML wrote:
There appears to be another minor complication. If one increases the
size of valsvals *= 200
one gets an error: `Integer': Infinity (FloatDomainError)
input[0...index] + input[index+1..-1]
Isn't it basically just iterating over the list and yielding? In which
case, your original loop:
<snip>
will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)
each_index is iterating over and yielding, there we have the first loop.
But I am not sure how Ruby Array's is implemented when a range is
given. I will take a look when I get a chance (again there is JRuby,
IronRuby, and the native Ruby).
But isn't it safe to assume it would have optimized implementation done
by Ruby implementors than the ad hoc O(n) implementation?
Cheers,
Ragu
--
Posted via http://www.ruby-forum.com/\.
yesteray <Ray.Baxter@gmail.com> writes:
> Each eval is O(n-1). You do n of them.
I think eval I used in this case is constant time. Any other views?
You are evaluating a product of n-1 terms in each eval.
eval(3*2*1*2)
eval(4*2*1*2)
eval(4*3*1*2)
eval(4*3*2*2)
eval(4*3*2*1)There is no way to optimize these multiplications away.
Of course there is a way: factorize them!
eval( 3*2*1*2)
eval(4 * 2*1*2)
eval(4*3 * 1*2)
eval(4*3*2 * 2)
eval(4*3*2*1 )
You can see that there is only two multiplications going on.
On Jun 19, 2:15 am, Ragunathan Pattabiraman > <ragunathan.pattabira...@gmail.com> wrote:
--
__Pascal Bourguignon__
# 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
From: Calamitas [mailto:calamitates@gmail.com]
input[0...index] + input[index+1..-1]
Isn't it basically just iterating over the list and yielding? In which
case, your original loop:<snip>
will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)each_index is iterating over and yielding, there we have the first loop.
But I am not sure how Ruby Array's is implemented when a range is
given. I will take a look when I get a chance (again there is JRuby,
IronRuby, and the native Ruby).But isn't it safe to assume it would have optimized implementation done
by Ruby implementors than the ad hoc O(n) implementation?
I checked Ruby 1.8.7 source code and Array[range] is done at constant
time. Here is the link to array.c
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup
--
Posted via http://www.ruby-forum.com/\.
I checked Ruby 1.8.7 source code and Array[range] is done at constant
time.
IMHO you'd also look at join (iterates over the array) and eval
(parses the string). Eval is IMHO scary in this context because one
(most ruby users or I at least) usually doesn't really know what it
involves.
True enough, since Array uses copy on write, so it can take a slice which
points to the same elements.
BUT the culprit is:
input[0...index] + input[index+1..-1]
Look at input[0...index] + input[index+1..-1]
Those two MEMCPY macro calls are loops and add up to an O(n-1) operation.
On Thu, Jun 19, 2008 at 12:12 PM, Ragunathan Pattabiraman < ragunathan.pattabiraman@gmail.com> wrote:
I checked Ruby 1.8.7 source code and Array[range] is done at constant
time. Here is the link to array.chttp://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup
--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
IMHO you'd also look at join (iterates over the array) and eval
(parses the string). Eval is IMHO scary in this context because one
(most ruby users or I at least) usually doesn't really know what it
involves.
I saw the array#join source which seems to involve a loop. Apparantly
this is O(n^2). Not quite sure about eval though.
I believe Ruby is about elegance and simplicity. Many of the solutions I
saw here were cryptic, at least to me. Stuff from Ruby gurus. I learned
some new stuff studying them.
But simplicity is the virtue that is missing IMHO. I thought I would
attempt at simplicity. But as you pointed out it is not efficient at
all. ("It's another Ruby virtue" says Ruby critic!)
Thank you all for your inputs.
Just wondering... is there any tool which computes the time complexity
given the code? That would be cool as we wouldn't want to checkout ruby
impl everytime.
--
Posted via http://www.ruby-forum.com/\.
There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g. product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too
(but untested):
pre =
post =
prod = 1
n = ary.length - 1
0.upto(n) {|i|
prod *= ary[i]
pre[i] = prod
}
prod = 1
n.downto(0) {|i|
prod *= ary[i]
post[i] = prod
}
product_except = lambda {|i| pre[i-1] * post[i+1]}
Time complexity = O(n) to calculate pre, O(n) to calculate post and
O(1) to calculate product_except(i) for any i, O(n) to calculate them
all for a total of O(n).
martin
On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan Pattabiraman <ragunathan.pattabiraman@gmail.com> wrote:
But simplicity is the virtue that is missing IMHO. I thought I would
attempt at simplicity. But as you pointed out it is not efficient at
all. ("It's another Ruby virtue" says Ruby critic!)
Ragunathan Pattabiraman <ragunathan.pattabiraman@gmail.com> writes:
Just wondering... is there any tool which computes the time complexity
given the code? That would be cool as we wouldn't want to checkout ruby
impl everytime.
Not in general (try to apply that tool to itself!). But for normal
programs, yes such a tool could be written.
--
__Pascal Bourguignon__
how bad is this?
inp = [4, 3, 2, 1, 2]
outp =
inp.each_with_index {|val, idx| inp[idx] = 1; outp << inp.inject(1) { |prod,
val2| prod * val2 }; inp[idx] = val}
On Thu, Jun 19, 2008 at 5:56 PM, Martin DeMello <martindemello@gmail.com> wrote:
On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan Pattabiraman > <ragunathan.pattabiraman@gmail.com> wrote:
>
> But simplicity is the virtue that is missing IMHO. I thought I would
> attempt at simplicity. But as you pointed out it is not efficient at
> all. ("It's another Ruby virtue" says Ruby critic!)There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g. product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too
(but untested):pre =
post =
prod = 1
n = ary.length - 10.upto(n) {|i|
prod *= ary[i]
pre[i] = prod
}prod = 1
n.downto(0) {|i|
prod *= ary[i]
post[i] = prod
}product_except = lambda {|i| pre[i-1] * post[i+1]}
Time complexity = O(n) to calculate pre, O(n) to calculate post and
O(1) to calculate product_except(i) for any i, O(n) to calculate them
all for a total of O(n).martin