Re: Computing sets of equivalences
- To: mathgroup at smc.vnet.net
- Subject: [mg46776] Re: Computing sets of equivalences
- From: "Fred Simons" <f.h.simons at tue.nl>
- Date: Sun, 7 Mar 2004 01:34:03 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
My colleague Frans Martens observed that in the solution I posted some time
ago, the use of symbols for the function values is superfluous. We thus
arrive at the very short function
equivalences[lst_] := Block[{f},
Scan[Set @@ f/@#& ,lst];
Reap[Sow[#, f[#]]& /@ Union@@lst][[2]]]
solutions posted so far. But it is very sensible for extra structures in the
data list. If we construct the test data in the following way (n is the
number of points and k the number of classes):
n=10000;k =10;
(f[#]=Random[Integer, {1,k}])& /@ Range[n];
data = Flatten[Partition[#,2,1]& /@ Reap[Sow[#,f[#]]& /@ Range[n]][[2]],1];
then my function becomes terribly slow. But when we place the pairs in a
random order:
n=10000;k =10;
(f[#]=Random[Integer, {1,k}])& /@ Range[n];
data = Flatten[Partition[#,2,1]& /@ Reap[Sow[#,f[#]]& /@ Range[n]][[2]],1];
data = data[[Ordering[Table[Random[], { Length[data]}]]]];
the function becomes very fast. I used these data for the testing for
various values of n and k.
I think it is also amazing that the Sow-Reap construction is so fast.
Regards,
Fred Simons
Eindhoven University of Technology