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  
 
 [ 5 post ] 

 Relevant Pages 

1. Temporal Paradox Tables, ReadOnly???

2. Set operations (union, intersection, etc...)

3. builtin array union intersection function

4. Union, Intersection, Difference

5. Internal error 216????

6. Is the a IsValidDb or IsValidParadox function in D2 ?

7. Is there a module for set operations (intersection, union etc) ?

8. Need Set Intersection

9. Finding the union of the keys of 2 associative arrays

10. elegant way to do the union of 2 strings

11. union semun error

12. Creating Union/Intersect arrays...

 

 
Powered by phpBB® Forum Software