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?
>
>
>
>
> 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?