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?
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 P.
input[0…index] + input[index+1…-1]
Isn’t it basically just iterating over the list and yielding? In which
case, your original loop:
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
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.
input[0…index] + input[index+1…-1]
Isn’t it basically just iterating over the list and yielding? In which
case, your original loop:
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
On Thu, Jun 19, 2008 at 12:12 PM, Ragunathan P. <
[email protected]> 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
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.
–
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.
On Jun 19, 2:15 am, Ragunathan P.
[email protected] 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?
You are evaluating a product of n-1 terms in each eval.
eval(3212)
eval(4212)
eval(4312)
eval(4322)
eval(432*1)
There is no way to optimize these multiplications away.
Ray
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
[email protected]
Kevin C. wrote:
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}
O(n^2). You are iterating through inp within inp (inject will iterate
through each element).
On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan P.
[email protected] 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 - 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
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
I agree. Pretty neat!
I believe this works in O(n). (I believe reverse, and zip are O(n)) It
is very similar to other solutions, but I like the each_with_index
method.
data=[4, 3, 2, 1, 2]
front=[1];
back=[1]
data.each_with_index{|val, index| front[index + 1] = front[index] * val}
data.reverse.each_with_index {|val, index| back[index+1] = back[index] *
val}
front.pop
back.pop
data=[]
front.zip(back.reverse){|a, b| data.push a * b}
p data
-jacob
Ragunathan P. [email protected] 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.
yesteray [email protected] writes:
eval(4312)
eval(4322)
eval(432*1)There is no way to optimize these multiplications away.
Of course there is a way: factorize them!
eval( 3212)
eval(4 * 212)
eval(43 * 12)
eval(432 * 2)
eval(4321 )
You can see that there is only two multiplications going on.
From: ex [mailto:[email protected]]
There is an array A[N] of N integers. You have to
compose an array
Output[N] such that Output[i] will be equal to the
product of all the elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Note: Solve it without the division operator and in O(n).
=============================================================
it’s friday here, so i guess i’ll just join the fun 
how about,
prod= lambda{|a| a.inject(1){|p,x| p*x}}
=> #Proc:0xb7d708e0@:1(irb)
a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]
pa=[]
=> []
s=a.size
=> 5
s2=s-1
=> 4
here is the meat:
i just concat orig array so i don’t need to rotate
then get subarrays in groups of s2 (a.size-1)
a2=a+a
=> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]
1.upto(s) do |i|
pa << prod.call(a2[i,s2])
end
=> 1
p pa
[12, 16, 24, 48, 24]
=> nil
can i pass google? =)
kind regards -botp
ex [email protected] writes:
OUTPUT:[12, 16, 24, 48, 24]
for k in 0…vals.length
p ans
def google(a)
r=Array.new(a.length,1)
m=1; i=0; while (i<a.length) do r[i]=m; m=a[i]; i+=1 end
m=1; i=a.length-1; while (0<=i) do r[i]=m; m=a[i]; i-=1 end
return r
end
irb(main):060:0> google([4,3,2,1,2])
[12, 16, 24, 48, 24]
On Fri, 2008-06-20 at 16:59 +0900, Peña, Botp wrote:
=> 4
end
=> 1p pa
[12, 16, 24, 48, 24]
=> nilcan i pass google? =)
kind regards -botp
Eyeballing this looks to me like it’s O(n^2). You’re iterating over the
list (1.upto(s)) and on each iteration you’re iterating over the list
(inject).
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).
prod= lambda{|a| a.inject(1){|p,x| p*x}}
This inject still iterates over n-1 elements for n iterations. That is
still bound to n^2.
1.upto(s) do |i|
pa << prod.call(a2[i,s2])
end
=> 1
J
On Jun 15, 1:59 pm, ex [email protected] wrote:
#===============================================================================
Hi, I’m new to this list, here is an implementation that uses just
array index (and pop). With ugly intrumentation.
def resolve(i)
front, back, o = [1], [1], []
0.upto i.length - 1 do |n|
front << i[n] * front[n]
back << i[i.length - 1 - n] * back[n]
@cost[@r]+=1
end
front.pop
back.pop
0.upto front.length - 1 do |n|
o[n] = front[n] * back[ back.length - 1 - n]
@cost[@r]+=1
end
p o
end
@cost = []
1.upto 10 do |@r|
@cost[@r] = 1
resolve([4, 3, 2, 1, 2]*@r)
end
p @cost
Lucas.