In an early article about programming style, Kernighan and Plaugher
look at an example where the programmer is trying to compute the
minimum of three values, approximately as follows:

        if ($x > $y) {
          if ($y > $z) {
            $min = $z;
          } else {
            $min = $y;
          }
        } else {
          if ($x > $z) {
            $min = $z;
          } else {
            $min = $x;
          }
        }

They point out that you can make the code much shorter and simpler
like this:

        $min = $x;
        if ($min > $y) { $min = $y }
        if ($min > $z) { $min = $z }

This also generalizes better to more than three items.

Suppose you want to find the median of three values instead of the
minimum.  Is there an analogous short version?

rd
($p{$_})&6];$p{$_}=/ ^$P/ix?$P:close$_}keys%p}p;p;p;p;p;map{$p{$_}=~/^[P.]/&&
close$_}%p;wait until$?;map{/^r/&&<$_>}%p;$_=$d[$q];sleep rand(2)if/\S/;print

First: Suppose that we compare x and y, as in the outer
comparison in the long form above.  Afterward, we are able to
eliminate either x or y as the minimum value.  But regardless of
the result, either could still be the median, so we don't learn
as much from a single comparison in the median case.

Second (really just a restatement of the first): There are six
possible orderings for a triple of different real numbers:

        x < y < z       x < z < y       z < x < y
        y < x < z       y < z < x       z < y < x

Suppose again that we first compare x and y, as in either form
above.  Whether we are looking for the minimum or the median,
this comparison eliminates either the first or the second line of
possibilities.  If x < y, then there are only two possibilities
left for the minimum (either x or z), so we can decide in one
more comparison; but there are still three possibilities left for
the median, so we need two more comparisons.  So the median is
inherently more difficult to compute than the minimum, even if
there are only three values, and we can't really expect that the
code for it will be as simple.

Third: Suppose that we're using an array `p' of three elements
p(0), p(1), p(2), instead of three discrete values.  Let each of
the Boolean variables a, b, c the value 1 if the expression p(0)
< p(1), p(0) < p(2), p(1) < p(2), respectively, is true, 0
otherwise.  Finally, let the output be the 2-bit index into `p',
one of 00, 01, or 10 (representing 0, 1, or 2), of the minimum or
the median, as desired.  Adopting the typical digital logic text
notation of juxtaposition as logical AND, suffix of ' as logical
NOT, and addition as logical OR, we come up with the following as
minimal sum-of-products solutions for the MSB and LSB of the
minimum:
        MSB: b'c'
        LSB: a'c
For the median, on the other hand:
        MSB: b'c + bc'
        LSB: a'b'c' + abc
This looks to me like further evidence that median is more
complex than minimum, even among only three choices.

*shrug*  At this point I'm pretty convinced that there's no
simple solution.  Maybe someone cleverer than me can come up with
one.  I'd be surprised, but in a pleasant way.

--

Stanford PhD Student - MSU Alumnus - Debian Maintainer - GNU Developer
Personal webpage: http://www.msu.edu/~pfaffben

        $i = $x; $j = $y;
        if ($x > $y) {$i = $y; $j = $x;}
        if ($i > $z) { $med = $i }
        if ($j > $z) { $med = $z }
        $med = $j;

The difficulty lies in the difference between the median and the
minimum: the minimum is less than everything, so it's easier to
generalize than the median, which is less than some items but
greater than others.  Thus the extra comparison (and an additional
implicit comparison) and dummy variables.

I believe the above will work if any or all of the values are
equal, which is quite nice.

- --keith

- --

public key:  http://wombat.san-francisco.ca.us/kkeller/public_key
alt.os.linux.slackware FAQ:  http://wombat.san-francisco.ca.us/perl/fom

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iEYEARECAAYFAjv2FFcACgkQhVcNCxZ5ID/sHQCfVGHc33EtbZJbeeZ1E6o8FkfP
pk4AmgInRaQ0INa4aWpAcVhDi0x7axqi
=S7jm
-----END PGP SIGNATURE-----

sub median
{
    my $mean;

    my $difmin = $difs[0]; my $med = $_[0];
    if ($difmin > $difs[1]) { $difmin = $difs[1]; $med = $_[1]; }
    if ($difmin > $difs[2]) { $difmin = $difs[2]; $med = $_[2]; }
    $med;

 "Well, enough of these vague generalities. On to the vague specifics."
  - Larry Wall, in "Apocalypse 3".

--

 "Well, enough of these vague generalities. On to the vague specifics."
  - Larry Wall, in "Apocalypse 3".

--
Oh!  I've said too much.  Smithers, use the amnesia ray.

     #7

So look to sorting algorithms when thinking of how to structure the
$x : $y : $z : ... comparisons. (And this seems to support the
argument that finding the median is inherently more complex than
finding the minimum...)

1;

--

   - Bruce

__bruce_van_allen__santa_cruz_ca__

[mailed and posted]

        if ($x > $y) {
          if ($y > $z) {
            $min = $z;
          } else {
            $min = $y;
          }
        } else {
          if ($x > $z) {
            $min = $z;
          } else {
            $min = $x;
          }
        }

But it turns out that simpler code, not obviously based on sorting, is
possible.

If you run quicksort on three items and look at what it is doing,
you'll find that it follows a tree very much like the one in the
'before' code.              

[mailed and posted]

You points out that an initial comparison, say between x and y,
eliminates three possibilities, but not the three you need to narrow
down the situation for the median.  This makes sense, and I agree that
it shows that the initial comparison (if there is one) shouldn't be
directly between two of the items.

So then I got to thinking about comparisons that would eliminate three
possibilites, but not necessarily the three in the top row or the
three in the bottom row.  

It occurred to me that a different way to proceed is to note that the
sequence x,y,z,x,y,z either contains an increasing sequence of three
values or a decreasing sequence of three values, but not both, and
that perhaps there's some way to find out which of these two
situations holds without knowing anything else about the relative
order of the three numbers.  And it turns out that there *is* a way to
do that:

  my $n = ($x-$y)*($y-$z)*($z-$x);
  my $s = $n < 0 ? 'decreasing' : 'increasing';

This was heartening, but then I realized that this doesn't actually
give you any information about the median.  Any of the three numbers
could be median, regardless of whether the sequence is increasing or
decreasing.  But still, maybe it's a step in the right direction.

But then I thought, suppose z is median.  Then the difference between
x and y must be larger than the difference between x and z or the
difference between y and z, because z is between x and y.  So if we
could find the largest of the three *differences*, that would tell us
which element was in the middle!  And we already have two-comparison
code for computing the maximum.  So here's my first cut at analogous
code to produce the median:

  my $diff = abs($x-$y); my $median = $z;
  if ($diff < abs($x-$z)) { $median = $y; $diff = abs($x-$z) }
  if ($diff < abs($y-$z)) { $median = $x; }

This is rather goofy, because it's so much less efficient than the
if-else tree, and unlike the analogous minimum-value code, it's not
obvious how it works.  But it does work and I don't think anyone can
say it isn't analogous.

I expect (and hope) someone will come up with an improvement to this,
but even if nobody does, I'll be happy, because my original question
asked for analogous code, and at the time I asked, I expected that the
answer would be that there was no such thing.  This is probably the
best Usenet experience I've had this year, because other folks'
articles got me thinking in a different way and I came up with an
answer I don't think I would have otherwise that I didn't think could
be found at all.

Thanks, especially to Ben and Bruce!

        else { $med = $j }

I'd implemented it as a Perl sub initially, with return statements,
then decided to make it less Perl-ish.  I'll never do it again.  :)

- --keith

- --

public key:  http://wombat.san-francisco.ca.us/kkeller/public_key
alt.os.linux.slackware FAQ:  http://wombat.san-francisco.ca.us/perl/fom

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iEYEARECAAYFAjv2wfUACgkQhVcNCxZ5ID8peACfa9X9l3GSdxoWAV6qmQWML56d
ZJMAniUlY5vWx6eteEBJ7R2DebYCx9ch
=CnxC
-----END PGP SIGNATURE-----

sub _sign { $_[0] < 0 ? -1 : $_[0] > 0 : 1 : 0 }



   return if $n < 0 || $n > $#$list;




      if( $n <= $#{$parts[0]} ) { $list = $parts[0]; next }

      if( $n <= $#{$parts[1]} ) { $list = $parts[1]; last }

      $list = $parts[2];
   }
   $$list[$n];

[untested]

Where sort takes O(N log N) time to act on an N item list, nthmin only
takes O(N) time [on average] with an N item list.

It's worst case times is O(N**2), but that only happens if every
partition is bad.  That's nearly impossible unless the data was
*constructed* for that to occur, and since partition selection is
randomized, it's kinda difficult to construct bad data.

NB: To make the speed of this comparable to perl's builtin sort, you
would have to write it in XS.

--
Klein bottle for rent - inquire within.