Re: how can I do this functionally?
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg966] Re: how can I do this functionally?
- From: Roman Maeder <maeder at inf.ethz.ch>
- Date: Thu, 4 May 1995 04:24:20 -0400
- Organization: Computer Science, ETH Zurich
a straightforward functional program is not always the most efficient...
David Cabana's <drc at gate.net> problem, stated here, triggered a number
of interesting solutions. Below is an efficiency analysis of them.
> Below I define a function, Classify[S_, f_], in an imperative (and
> not particularly efficient) style. Can anyone tell me how to define
> it either functionally or via pattern matching?
>
> The function Classify takes 2 arguments, f and S. f is a function,
> and S is a subset of the domain of S. In particular, S is a list
> of elements of the domain of f, and contains no repeated elements.
>
> The function f induces an equivalence relation on S as follows:
> a is equivalent to b modulo f if and only if f[a] == f[b]. Classify
> returns the equivalence classes of S modulo f.
> *)
>
> (* drc at gate.net (David Cabana) *)
>
> Classify1[S_, f_]:=
> Module[ {values, partition, len, index},
> len = Length[S];
> partition = Table[{}, {len}];
> values = Map[f,S];
>
> Do[
> index = First[Flatten[Position[values, values[[i]]]]];
> partition[[index]] = Prepend[partition[[index]], S[[i]]],
> {i, 1, len}
> ];
> (* remove any empty lists from partition *)
> Select[partition, (#!={})&]
> ]
The prize for elegance belongs clearly to
(* wagner at bullwinkle.cs.Colorado.EDU (Dave Wagner) *)
Classify2[s_, f_] :=
With[{fs = f /@ s},
Cases[Transpose[{s, fs}], {x_,#}->x]& /@ Union[fs]
]
but, as we shall see, his solutions does not "blow us away" as he promises.
A slight variant will turn out much slower,
since f is evaluated over and over:
(* tomi at wri.com (Tom Issaevitch) *)
Classify3[s_, f_]:=
With[{v = Union[Map[f, s]]}, Map[Select[s, Function[{z}, f[z] == #]]&, v]]
What is wrong with Classify2 and Classify3? The time they take
is proportional to the input size times the number of equivalence classes.
If the classifying function f has as many classes as possible
(Identity does this nicely) they take quadratic time.
A more efficient solution was posted:
(* Count Dracula <lk3a at kelvin.seas.virginia.edu> *)
Classify4[domain_, function_] :=
Module[{list, tagged, pairs, steps, runs, sums, elems},
list = function /@ domain;
tagged = Sort[ Transpose[{list, Range[Length[list]]}] ];
pairs = Partition[tagged, 2, 1];
steps = Flatten[Position[pairs, {{e1_,_}, {e2_, _}}/; e1 =!= e2, 1]];
runs = Append[steps, Length[tagged]] - Prepend[steps, 0];
elems = Part[domain, Transpose[tagged][[2]]];
sums = FoldList[Plus, 0, runs];
Take[elems, #]& /@ Transpose[ {Drop[sums + 1, -1], Drop[sums, 1]} ]
]
it uses sorting (which is of complexity n Log[n]) to arrange elements
of the same class into adjacent position.
This code can be cleaned up a bit to give
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]]}]
]
To test the various methods, we time them for functions with a
prescribed number of equivalence classes. The function Mod[#, k]&
has exactly k possible values and serves as our test function.
size = 200;
testdata = Range[size];
nclasses = Round[{1, size/4, size/2, 3size/4, size}];
makeK[k_] := Mod[#, k]&
test[method_] := Timing[method[testdata, #]][[1]]& /@ makeK /@ nclasses /.
Second -> 1
allMethods = {Classify1, Classify2, Classify3, Classify4, Classify}
Here are the results for input size 200 and
1, 50, 100, 150, and 200 classes, respectively:
test /@ allMethods // MatrixForm[#, TableHeadings -> {allMethods, nclasses}]&
> 1 50 100 150 200
Classify1 4.63333 1.85 1.76667 1.75 1.71667
Classify2 0.1 1.86667 3.7 5.55 7.13333
Classify3 0.233333 8.05 14.9333 21.5833 29.3333
Classify4 0.216667 0.283333 0.35 0.416667 0.516667
Classify 0.183333 0.233333 0.3 0.3 0.35
Roman Maeder