MathGroup Archive 1995

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

Search the Archive

Re: Re: how can I do this functionally?

  • To: mathgroup at christensen.cybernetics.net
  • Subject: [mg1045] Re: [mg966] Re: how can I do this functionally?
  • From: Allan Hayes <hay at haystack.demon.co.uk>
  • Date: Wed, 10 May 1995 08:15:36 -0400

Roman Maeder <maeder at inf.ethz.ch> in [mg966] Re: how can I do this  
functionally? Gave an efficiency analysis of some solutions of David  
Cabana's <drc at gate.net> problem given in mg[913].

I give some faster coded and some general rules that the changes  
made seem to suggest.


(*1*) Try various styles.
(*2*) Consider using Thread instead of Transpose for threading (also 	
      look at MapThread).

In  Dave Wagner's code

Classify2[s_, f_] :=
   With[{fs = f /@ s},
	Cases[Transpose[{s, fs}], {x_,#}->x]& /@ Union[fs]
   ]

Transpose is used once for every member of Union[fs].  The  
following code avoids this and is faster on the given tests (timings  
are given later). Of course the problem of repeated use of Cases  
remains.

Classify2A[s_, f_] :=
   Module[{fs,gr,c},
	fs = f/@s;
	gr = Thread[{s,fs}];    	   (*2*)
	c[y_] := Cases[gr, {x_,y}:> x];
	c/@Union[fs]
   ]

I have got so used to looking fror integrated funcional and list  
processing code that this came as something of a surprise.

(*3*) Operate on whole structures.

Roman Maeder's final code is

Classify[s_, f_] :=
   Module[{ran, dom, pairs, steps},
        {ran, dom} = Transpose[Sort[ {f[#], #}& /@ s ]];
        pairs = Partition[ran, 2, 1];
        steps = Flatten[Position[pairs, {e1_, e2_}/; e1 =!= e2, 1]];
        Take[dom, #]& /@
            Transpose[
	       {Prepend[steps, 0] + 1, Append[steps,Length[s]]}
	    ]
    ]

Some modifications using the rules  (*2*) and (*3*) give slightly  
faster code.

ClassifyA[s_,f_] :=
   Module[{ran,dom,pairs,steps},
	{ran,dom}= Thread[Sort[Thread[{f/@s, s}]]];  (*2*)
	pairs = Partition[ran, 2, 1];
	steps = Flatten[Position[Apply[SameQ,pairs,1],False,1]];(*3*)
	Take[dom,#]&/@
	   Thread[{Prepend[steps+1,1],Append[steps,Length[s]]}] (*2*)
   ];


TIMINGS

Using Roman's test setup

testdata := Range[size];
makeK[k_] := Mod[#, k]&
test[method_] :=
   Timing[method[testdata, #]][[1]]& /@ makeK /@nclasses /.
   Second -> 1
allMethods = {Classify2,Classify2A, Classify,ClassifyA};

I get (on a NeXT Turbo)

size = 200;
nclasses = Round[{1, size/4, size/2, 3size/4, size}];
test /@ allMethods //
MatrixForm[#, TableHeadings -> {allMethods, nclasses}]&

             1           50          100         150         200
Classify2    0.0833333   1.36667     2.7         4.03333     5.3

Classify2A   0.0833333   0.733333    1.31667     1.91667     2.56667

Classify     0.183333    0.216667    0.266667    0.283333    0.333333

ClassifyA    0.166667    0.2         0.166667    0.2         0.266667


And for lists of length 5000

size = 5000;
nclasses = Round[{1,size/1000, size/500,size/100, size/50, size}];
test /@ allMethods[[{3,4}]] //
MatrixForm[#, TableHeadings -> {allMethods[[{3,4}]], nclasses}]&

            1         5         10        50        100       5000
Classify    3.58333   4.56667   4.63333   4.38333   4.56667   8.13333

ClassifyA   2.23333   3.13333   3.15      3.01667   3.16667   6.3


Allan Hayes
hay at haystack.demon.co.uk


  • Prev by Date: Re: DSolve solution checking
  • Next by Date: Re: Random[BinomialDistribution[..]] wrong ?
  • Previous by thread: Re: how can I do this functionally?
  • Next by thread: Re: Challenge!