Re: Re: Re: Re: aggregation of related elements in a list
- To: mathgroup at smc.vnet.net
- Subject: [mg61832] Re: [mg61793] Re: [mg61762] Re: [mg61730] Re: aggregation of related elements in a list
- From: leigh pascoe <leigh at cephb.fr>
- Date: Mon, 31 Oct 2005 06:10:10 -0500 (EST)
- References: <djcgcs$6du$1@smc.vnet.net> <djfnjr$b1i$1@smc.vnet.net> <200510270902.FAA19490@smc.vnet.net> <200510280725.DAA08769@smc.vnet.net> <200510300443.AAA09785@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
danl at wolfram.com wrote:
SNIP>
>If I admit Floyd-Warshall was overkill and far too slow for this problem,
>can I play again?
>
>For set of m pairs giving connections between n elements, the code below
>has complexty O(n+m*log(m)). One can get rid of the log factor as the
>sorting is not strictly needed, but in practice it is not the bottleneck
>and actually tends to improve speed.
>
>aggregate[n_, pairs_] := Module[
> {hh, aggs, kk, ll, mm, spairs = Sort[Map[Sort, pairs]], fm},
> aggs = Map[hh, Range[n]];
> Do[
> {kk, mm} = spairs[[j]];
> ll = First[hh[kk]];
> fm = First[hh[mm]];
> If[fm === mm,
> hh[mm] = hh[ll],
> If[ll < fm,
> hh[mm] = hh[ll];
> hh[First[hh[fm]]] = hh[ll],
> hh[ll] = hh[mm]; ll = fm]];
> , {j, Length[spairs]}];
> Last[Reap[Do[ll = hh[j]; Sow[j, ll], {j, n}]]]
> ]
>
>The idea is to use a "marker function" (hh) to record the current smallest
>element related to the one in question. Note that if I set hh[7] tp hh[3],
>and later learn that hh[3] should become hh[1] because element 3 is found
>to be related to element 1, then the assignment hh[3]=hh[1] suffices to
>change it everywhere hh[3] may be found. So there is no backtracing
>needed. We loop once over the pairs to create associations, and once over
>the list elements to put associated elements into buckets.
>
>n = 1000;
>pairs = Table[Random[Integer, {1, n}], {n}, {2}];
>
>In[65]:= Sort[agg0[n,pairs]]===Sort[agg2[n,pairs]]===
> Sort[aggregate[n,pairs]]
>Out[65]= True
>
>We check the speed:
>
>n = 10000;
>pairs = Table[Random[Integer, {1, n}], {n}, {2}];
>
>In[59]:= {Timing[agg0[n,pairs];],Timing[agg2[n,pairs];],
> Timing[aggregate[n,pairs];]}
>Out[59]= {{4.593 Second,Null},{1.297 Second,Null},
> {0.297 Second,Null}}
>
>Now double the size:
>
>n = 20000;
>pairs = Table[Random[Integer, {1, n}], {n}, {2}];
>
>In[62]:= {Timing[agg0[n,pairs];],Timing[agg2[n,pairs];],
> Timing[aggregate[n,pairs];]}
>Out[62]= {{28.609 Second,Null},{5.657 Second,Null},
> {0.656 Second,Null}}
>
>
>Daniel Lichtblau
>Wolfram Research
>
>
>
I very much like this solution, which follows what one might do
manually, and is also efficient. It resembles the Flood-fill algorithm,
which is O(n^2), but by some Ma magic is only linear in n. Using the
existing function ConnectedComponents has the virtue of clarity from the
point of view of reading a program. In any case thanks again to all who
responded to my question.
Surely there will be no further improvements??
LP
- References:
- Re: aggregation of related elements in a list
- From: Maxim <ab_def@prontomail.com>
- Re: Re: aggregation of related elements in a list
- From: "Carl K. Woll" <carlw@wolfram.com>
- Re: Re: Re: aggregation of related elements in a list
- From: danl@wolfram.com
- Re: aggregation of related elements in a list