MathGroup Archive 2004

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

Search the Archive

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


  • Prev by Date: Converting to Standard LaTeX
  • Next by Date: Re: DSolve change in v5 -- undocumented error message
  • Previous by thread: Re: Computing sets of equivalences
  • Next by thread: Re: Factoring two-dimensional series expansions? (Ince polynomials again)