Re: [FWP] Cartesian Cross-Products

[John Carter <john@netsys.co.za>]

On Wed, 12 Apr 2000, Jeff Pinyan wrote:

>   Write a subroutine that returns the Cartesian cross product of a set of
>   sets, where each set is represented by a single array.  Thus, the sub
>   should take an arbitrary number of arrays (i.e. refs to arrays) and
>   return an arbitrary number of arrays.  You may assume that it will never
>   be called in scalar context.  (Remember that the Cartesian cross product
>   of n sets is the set of all possible n-tuples (ordered sets of size
>   n) whose first element is from the first of the n sets, the second
>   element is from the second of the n sets, etc.)

The next step is to go to a natural join as per SQL

<SPEAKING SQL>
describe TABLEA;
FieldA
FieldB

describe TABLEB;
FieldA
FieldC

select TABLEA.FieldA, FieldB, FieldC from TABLEA, TABLEB where 
TABLEA.FieldA = TABLEB.FieldA;

</SPEAKING SQL>

The obvious algorithm is order(n*m) where n and m are the size of table A
and B.

But a nice _fast_ sneak way is to load up table A into a perl hash and
then wade through table B. Result is order(n+m) _much_ faster.

Just take care to load the smaller table into the hash. ;-)


John Carter

Work Email : john@netsys.co.za Private email : cyent@mweb.co.za 
Yell Phone : 083-543-6915      Phone         : 27-12-348-4246

Death is nature's gentle way of saying, "Relax".


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe