MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Faster ways to unionize intersecting sets?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg70139] Re: Faster ways to unionize intersecting sets?
  • From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
  • Date: Thu, 5 Oct 2006 03:32:40 -0400 (EDT)
  • Organization: The Open University, Milton Keynes, UK
  • References: <eg02a3$81m$1@smc.vnet.net>

lsha wrote:
> Hi,
> 
> I need to search a list of sets and unionize any sets that intersect. The
> following functions seems to work but may be there are faster ways?
> 
> Thanks in advance.
> 
> 
> 
> intersectQ[s1_, s2_] := If[Intersection[s1, s2] != {}, True, False]
> 
> mergeSets[s_List] := Module[
> {h, r, singles, club, cnt},
> cnt = Length[s];
> If[cnt < 2, Return[s]];
> singles = {};
> club = s;
> 
> While[cnt >= 2,
> h = club[[1]];
> r = Rest[club];
> hit = 0;
> club = If[intersectQ[h, #], hit = 1; Union[h, #], #] & /@ r;
> If[hit == 0, singles = Append[singles, h]];
> --cnt;
> ];
> Join[singles, club]
> ]
> 
> 
Using functional programming, mergeSets2 (see In[5]) is 15 to 20 times 
faster than the original procedural code.

In[1]:=
intersectQ[s1_, s2_] := If[Intersection[s1, s2] != {},
    True, False]
mergeSets[s_List] := Module[{h, r, singles, club,
     cnt}, cnt = Length[s]; If[cnt < 2, Return[s]];
     singles = {}; club = s; While[cnt >= 2,
      h = club[[1]]; r = Rest[club]; hit = 0;
       club = (If[intersectQ[h, #1], hit = 1;
            Union[h, #1], #1] & ) /@ r;
       If[hit == 0, singles = Append[singles, h]];
       --cnt; ]; Join[singles, club]]

In[3]:=
s = Table[Table[Random[Integer, {1, 1000}],
      {Random[Integer, {1, 20}]}], {100}];

In[4]:=
t1 = Timing[res1 = mergeSets[s]; ][[1]]

Out[4]=
1.234 Second

In[5]:=
mergeSets2[s_List] := Module[{list, pos, singles,
     club}, list = MapIndexed[Intersection[#1,
         Flatten[Drop[s, #2]]] & , s];
     pos = Position[list, {}]; singles =
      Extract[s, pos]; club =
      Union[Flatten[Complement[s, singles]]];
     {singles, club}]

In[6]:=
t2 = Timing[res2 = mergeSets2[s]; ][[1]]

Out[6]=
0.063 Second

In[7]:=
t1/t2

Out[7]=
19.5873

Regards,
Jean-Marc


  • Prev by Date: RE: Re: Performance--Dual Core
  • Next by Date: Re: Symbol and Pi and expressions evaluating to Pi
  • Previous by thread: Faster ways to unionize intersecting sets?
  • Next by thread: Re: Faster ways to unionize intersecting sets?