       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][]];
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, #]][]& /@ 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

```

• Prev by Date: Re: What's this Mathematica function called?
• Next by Date: Re: How to prevent Solve from DSolve?
• Previous by thread: Re: how can I do this functionally?
• Next by thread: Re: Re: how can I do this functionally?