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