From: "Brian Schröder" <ruby.brian@...>
Date: 2005-08-12T19:42:03+09:00
Subject: Re: cartesian product - next to last version

On 12/08/05, Brian Schr�der <ruby.brian@gmail.com> wrote:
> On 12/08/05, Dave Burt <dave@burt.id.au> wrote:
> > Brian Schr�der offered:
> > > def cartprod(base, *others)
> > >   return base.map{|a| [a] } if others.empty?
> > >   others = cartprod(*others)
> > >   base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
> > > *b]) } }
> > > end
> >
> > Wow - that's nice and functional!
> >
> > My procedural solution is much uglier, but it 1) isn't recursive and 2)
> > yields results to a given block as it iterates.
> >
> > If given a block, the following will return nil, but pass the values into a
> > given block:
> >
> > a=[[1,2,3],[4,5,6],[7,8,9]]
> > a.cartprod do |a0e, a1e, a2e|
> >   # ...
> > end
> >
> > class Array
> >   def cartprod
> >
> >     unless block_given?
> >       ret = []
> >       cartprod {|tuple| ret << tuple}
> >       return ret
> >     end
> >     return if any? {|a| a.size == 0 }
> >     index = [0] * size
> >     begin
> >       yield *zip(index).map {|a| a[0][a[1]] }
> >       (index.size - 1).downto(0) do |i|
> >         if index[i] < self[i].size - 1
> >           index[i] += 1
> >           break
> >         else
> >           index[i] = 0
> >         end
> >       end
> >     end while index != [0] * size
> >   end
> > end
> >
> > Cheers,
> > Dave
> >
> >
> >
> >
> 
> Yielding the values is certainly a good idea, but it makes the code a
> lot bigger. Anyhow, here is the recursive, yielding version.
> 
> def cartprod(base, *others)
>   if block_given?
>     if others.empty?
>       base.each{|a| yield [a]}
>     else
>       base.each do | a |
>         cartprod(*others) do | b |
>           yield [a, *b]
>         end
>       end
>     end
>     nil
>   else
>     return base.map{|a|[a]} if others.empty?
>     others = cartprod(*others)
>     base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
>   end
> end
> 
> 

I've got some interesting benchmark results to share:
Benchmark.bm(35) do | b | 
  [[2, 16], [6,7], [25,4], [800,2]].each do | size, depth |
    args = Array.new(depth) { Array.new(size) {|i| i} }    
    b.report("Recursive Array (#{size}**#{depth})") do cartprod(*args) end
    b.report("Recursive Array iterated (#{size}**#{depth})") do
cartprod(*args).each do | e | end end
    b.report("Recursive Yielding (#{size}**#{depth})") do
cartprod_y(*args) do | e | end end
    b.report("Procedural Yielding (#{size}**#{depth})") do
args.cartprod do | *e | end end
    puts
  end
end

                                         user     system      total        real
Recursive Array (2**16)              0.610000   0.130000   0.740000 (  0.840845)
Recursive Array iterated (2**16)     0.890000   0.130000   1.020000 (  1.287632)
Recursive Yielding (2**16)           3.910000   0.760000   4.670000 (  4.779378)
Procedural Yielding (2**16)          4.850000   0.890000   5.740000 (  5.847342)

Recursive Array (6**7)               1.690000   0.310000   2.000000 (  2.027407)
Recursive Array iterated (6**7)      2.300000   0.430000   2.730000 (  2.721382)
Recursive Yielding (6**7)            5.830000   1.330000   7.160000 (  7.166822)
Procedural Yielding (6**7)          11.200000   1.970000  13.170000 ( 13.440081)

Recursive Array (25**4)              1.750000   0.360000   2.110000 (  2.118353)
Recursive Array iterated (25**4)     1.990000   0.510000   2.500000 (  2.507274)
Recursive Yielding (25**4)           9.130000   1.050000  10.180000 ( 10.220420)
Procedural Yielding (25**4)         12.020000   2.120000  14.140000 ( 15.580462)

Recursive Array (800**2)             3.750000   0.630000   4.380000 (  4.375153)
Recursive Array iterated (800**2)    3.050000   0.790000   3.840000 (  3.839810)
Recursive Yielding (800**2)          5.380000   0.930000   6.310000 (  6.308811)
Procedural Yielding (800**2)        17.170000   2.480000  19.650000 ( 20.676642)



In these benchmarks the recursive version is a lot faster. Beware that
only creating and discarding the block is not a good measure,
therefore I also included an iteration about the returned array for
the array method. As you see it depends on the characteristics of the
argument which method is fastest.

regards,

Brian
-- 
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/