Computing set union and intersection.
Author Message
Computing set union and intersection.

potentially containing several thousand elements.

Here's my first cut at doing this:

intersection:  Pick one of the arrays, put the other in a hash with
dummy values, and loop through the first array, adding the elements

Quote:
}

union:  Put both arrays in the same hash with dummy values, so
duplicates are ignored, then extract the keys.

Does anyone know a better way of doing this?

Sun, 05 Oct 2003 08:53:00 GMT
Computing set union and intersection.

Quote:

> intersection:  Pick one of the arrays, put the other in a hash with
> dummy values, and loop through the first array, adding the elements

> my %one_hash;

> }

Sun, 05 Oct 2003 10:25:41 GMT
Computing set union and intersection.
Someone pointed out to me elsewhere that "perldoc -q intersection"
provides a method for computing the set union, intersection and
symmetric difference.  The method used there looks nicer than my
approach, and also can be generalized easily to more than two sets.

Sun, 05 Oct 2003 11:42:18 GMT
Computing set union and intersection.

Quote:

Are the arrays sorted?  If they are, you can use a linear merge:

my \$i = 0, my \$j = 0;

my \$cmp = (\$one[\$i] <=> \$two[\$j]);

}

slower than the hash approach below, because it's lower-level code, but
if your arrays are large the memory savings will more than compensate.

Quote:
>my %one_hash;

>}

my %hash;

Quote:
>my %union_hash;

This is probably the fastest way to compute the union only, as long as
you use undef() to build up the hash as above.  (Assigning an empty list
to the hash slice would be almost, but apparently not quite, as fast.)

my %hash;

--
Ilmari Karonen - http://www.sci.fi/~iltzu/
Please ignore Godzilla / Kira -- do not feed the troll.

Sun, 05 Oct 2003 20:32:33 GMT
Computing set union and intersection.
Thanks for the help :)

Wed, 08 Oct 2003 17:40:42 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages