Median of Three
Author Message Median of Three

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

Wed, 05 May 2004 05:18:22 GMT  Median of Three

[clp.moderated dropped from Newsgroups]

Quote:
> 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?

\$med = \$x;
(\$Y,\$Z) = (\$y < \$z) ? (\$y,\$z) : (\$z,\$y);  # ensures \$Y <= \$Z

if (\$med < \$Y)  { \$med = \$Y }
if (\$med > \$Z)  { \$med = \$Z }

I don't see any obvious generalization of this to more than 3 items;
nor do I think this is any different from pulling out the middle term
of a 3-item sort().

--
Joe Schaefer             "Life is just one damn thing after another."
--Mark Twain

Wed, 05 May 2004 07:51:46 GMT  Median of Three

(snipped)

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

For a number set containing three entries, the median is always
the second number in the set. No math is needed to find it.

This applies to any odd numbered number set. The median is
the middle number; the entry with an equal number of entries
before and after the entry.

No complicated math is involved nor are complicated formulas
needed. A median solution can be found for either a number set
with an odd number of entries or, a number set with an even
number of entries using simple arithmetic; one liners.

In almost all cases, save for complex decimal numbers,
a median can be calculated mentally by simply visualizing
a typical number line. Same is nearly true for histograms.

This simple visualization does not hold quite so true for
geometric figure medians unless, you are imaginative.

I have removed your cross-posting to various groups.
My personal opinion is this wastes bandwidth and leads
to spamming of groups not interested in an article.

Additionally it is inappropriate to cross-post to a
moderated newsgroup. This is unfair to a moderator;
she or he is instantly mail bombed.

I do not condone mail bombing a newsgroup moderator.

Godzilla!

--

TEST SCRIPT:
____________

#!perl

\$median = \$Array[(\$#Array / 2)];

print \$median;

print "\n\n";

\$median = \$Array[int(\$#Array / 2)] + ((\$Array[int(\$#Array / 2) + 1] - \$Array[int(\$#Array / 2)]) / 2);

print \$median;

exit;

Wed, 05 May 2004 08:27:25 GMT  Median of Three
[ Note:  This time I removed comp.lang.perl.moderated from
the Newsgroups: line. ]

Quote:
>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?

This is certainly analogous in a way, although I'm pretty sure it only
works for three numbers and it's ugly:

\$average = (\$x + \$y + \$z) / 3;

\$median = \$x;
if (abs (\$y - \$average) < abs (\$median - \$average)) { \$median = \$y; }
if (abs (\$z - \$average) < abs (\$median - \$average)) { \$median = \$z; }

This relies on the idea the median of three numbers is the closest
number to the average of those three numbers.  So what it's really
doing is finding the minimum difference between the average and the
median.

The proof that this is correct is probably something like this:

* The average always falls between the two extreme points on
the number line.

* The average falls on one side or the other of the median.

* If the average falls to the left of the median, it falls
closer to the median than to the minimum.  The average of all
three points must be greater than the average of the median and
the minimum (because the average of the three points also
includes the maximum which is greater than either).  So the
average of all three points is to the right of the midpoint
between the minimum and medium, meaning the average is closer to
the median than to the minimum.

* Similar (symmetrical) reasoning applies if the average falls
to the right side of the median.

* Special cases (median == average, some of the numbers equal,
etc.) are omitted, but they're fairly straightforward.

I can't imagine that this code is something you'd want to use in a real
program...

- Logan
--
"In order to be prepared to hope in what does not deceive,
we must first lose hope in everything that deceives."

Georges Bernanos

Wed, 05 May 2004 08:41:24 GMT  Median of Three

Quote:

>[ Note:  This time I removed comp.lang.perl.moderated from
>  the Newsgroups: line. ]

This refers to my original post, which will never show up, since I'm
not that e{*filter*}d about bothering to register so my post can make it to
comp.lang.perl.moderated.

So I'll just say here again what I said in that post.

One simple way to do it is just write this:

\$median = (sort \$x, \$y, \$z);

I'm not sure if that's in the spirit of the original challenge or not.
If not, see my previous post.

- Logan
--
"In order to be prepared to hope in what does not deceive,
we must first lose hope in everything that deceives."

Georges Bernanos

Wed, 05 May 2004 08:46:45 GMT  Median of Three

Quote:
> 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?

I think the answer to this question is "no".  I will try to back
up that answer with some less-than-airtight arguments.  In the
process, I'll assume that x, y, and z all have different values.
This is mostly a mathematical or computer science question, not a
programming or Perl question, so I'll use language-neutral
notations in my discussion.

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

Wed, 05 May 2004 07:25:18 GMT  Median of Three
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quote:

> 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:
[snip]
> 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?

This should work, but I don't think it's easily generalizable:

\$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-----

Wed, 05 May 2004 08:40:24 GMT  Median of Three

Quote:

> (snipped)

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

> For a number set containing three entries, the median is always
> the second number in the set. No math is needed to find it.

gtoomey

Wed, 05 May 2004 09:21:36 GMT  Median of Three

Quote:

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

The way to determine the complexity of median algorithms is the number of
comparisons. The naive method is to sort and find the value in the middle of
the sorted data. This is O(n log n).

There are linear i.e. O(n) algorithms. See Dor & Zwick, Selecting the
Median, Siam Jour. Comp 28(5),pp 2722-1758, 1999.
There is an  approximate algorithm at  www.cs.wpi.edu/~hofri/medsel.pdf

gtoomey

Wed, 05 May 2004 09:24:10 GMT  Median of Three

Quote:

> For a number set containing three entries, the median is always
> the second number in the set.  No math is needed to find it.

No.  That is only true if the set is ordered.

Peter

--
#!/local/bin/perl5 -wp -*- mode: cperl; coding: iso-8859-1; -*-
# matlab comment {*filter*} (strips comments from Matlab m-files)
s/^((?:(?:[])}\w.]'+|[^'%])+|'[^'\n]*(?:''[^'\n]*)*')*).*/\$1/x;

Wed, 05 May 2004 09:00:12 GMT  Median of Three

| Additionally it is inappropriate to cross-post to a
| moderated newsgroup. This is unfair to a moderator;
| she or he is instantly mail bombed.
|
| I do not condone mail bombing a newsgroup moderator.

http://www.plover.com/clpm/moderators

Have you realized MJD is a moderator?
--
\$_=q;0cb212c210b0bb010c0113bb0c410c0b516c0bb3d212c2b0b0b016b6cb2b2c21010c0
b41110b3bba0e0c0d2c4b2b6bc013d2c0d0b01012b0b0;;s/\n//g;s/(\d)/\$1<2?\$1:'0'x

Wed, 05 May 2004 11:36:50 GMT  Median of Three

(snipped)

Quote:
> | I do not condone mail bombing a newsgroup moderator.
> http://www.plover.com/clpm/moderators
> Have you realized MJD is a moderator?

Your rationale is related to something intelligent
in what way?

You are certainly free to mail bomb Mr. Plover
based on your logic, whatever the heck it is.

It is my choice to not mail bomb others.

* wonders if this bozo's brain is on vacation *

Godzilla!

Wed, 05 May 2004 17:04:48 GMT  Median of Three

(snipped)

Quote:
> > For a number set containing three entries, the median is always
> > the second number in the set.  No math is needed to find it.

> No.  That is only true if the set is ordered.

Your enrollment in and successful completion of an
elementary Algebra class could benefit you greatly.

Godzilla!

Wed, 05 May 2004 17:11:26 GMT  Median of Three

Quote:
> ...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?

In the case of three values the median is guaranteed to be closest to
the mean, so we can take the mean of the absolute value of the diffs
from the mean and then use that.  Something like.

sub median
{
my \$mean;

my \$difmin = \$difs; my \$med = \$_;
if (\$difmin > \$difs) { \$difmin = \$difs; \$med = \$_; }
if (\$difmin > \$difs) { \$difmin = \$difs; \$med = \$_; }
\$med;

Quote:
}

This doesn't work for more values, alas.
--

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

Wed, 05 May 2004 17:27:11 GMT  Median of Three

...

Quote:
>This should work, but I don't think it's easily generalizable:

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

This code gives \$med = 5 for \$x = 3, \$y = 5, \$z = 4, so it's wrong.

--

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

Wed, 05 May 2004 17:28:26 GMT

 Page 1 of 2 [ 25 post ] Go to page:  

Relevant Pages