Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6891 > unrolled thread

O(n log n) in place median algorithm (was: Difference between these pointer syntaxes)

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-19 23:38 +0100
    Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-19 18:08 -0700
      Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) Öö Tiib <ootiib@hot.ee> - 2016-08-21 14:08 -0700
        Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-22 00:27 -0700
          Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-22 19:31 -0700

#6891 — O(n log n) in place median algorithm (was: Difference between these pointer syntaxes)

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>
>> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
>>>
>>> The O(N log N) method using binary search sounds odd -- the description
>>> does not seem to match any selection algorithm I know.  Can you explain
>>> what you meant?
>>> 
>> Pass through the data, taking maximum and minimum. Then use (max +
>> min)/2 as you first guess for the median. Pass through again counting
>> elements above and below, and the nearest in both directions. If you
>> are wrong, use (max (or min) + guess)/2 as your refined guess and
>> repeat, doing a binary search.
>> If you are right, the nearest rather than the guess is the answer.
>
> Interesting.  I did not know that one.  Maybe the fact that it's not
> linear time makes people overlook it, but there must be times when
> neither copying nor rearranging the array is acceptable.
>
> A bit more searching suggests that some people call this Torben's
> algorithm.  Do you know the inventor or simply a definite name for it?

That's a first name and probably not that of the originator.  Does
anyone know more about it?

(I've changed the subject and set Followup-To: comp.programming.)

-- 
Ben.

[toc] | [next] | [standalone]

#6893

On Friday, August 19, 2016 at 11:38:31 PM UTC+1, Ben Bacarisse wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
> > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> >
> >> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
> >>>
> >>> The O(N log N) method using binary search sounds odd -- the description
> >>> does not seem to match any selection algorithm I know.  Can you explain
> >>> what you meant?
> >>> 
> >> Pass through the data, taking maximum and minimum. Then use (max +
> >> min)/2 as you first guess for the median. Pass through again counting
> >> elements above and below, and the nearest in both directions. If you
> >> are wrong, use (max (or min) + guess)/2 as your refined guess and
> >> repeat, doing a binary search.
> >> If you are right, the nearest rather than the guess is the answer.
> >
> > Interesting.  I did not know that one.  Maybe the fact that it's not
> > linear time makes people overlook it, but there must be times when
> > neither copying nor rearranging the array is acceptable.
> >
> > A bit more searching suggests that some people call this Torben's
> > algorithm.  Do you know the inventor or simply a definite name for it?
> 
> That's a first name and probably not that of the originator.  Does
> anyone know more about it?
> 
> (I've changed the subject and set Followup-To: comp.programming.)
> 
The algorithm was invented by me, and independently by Torben Mogenson,
and probably by many other people as well.

[toc] | [prev] | [next] | [standalone]

#6895

On Saturday, 20 August 2016 04:08:07 UTC+3, malcolm...@btinternet.com  wrote:
> On Friday, August 19, 2016 at 11:38:31 PM UTC+1, Ben Bacarisse wrote:
> > Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> > 
> > > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> > >
> > >> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
> > >>>
> > >>> The O(N log N) method using binary search sounds odd -- the description
> > >>> does not seem to match any selection algorithm I know.  Can you explain
> > >>> what you meant?
> > >>> 
> > >> Pass through the data, taking maximum and minimum. Then use (max +
> > >> min)/2 as you first guess for the median. Pass through again counting
> > >> elements above and below, and the nearest in both directions. If you
> > >> are wrong, use (max (or min) + guess)/2 as your refined guess and
> > >> repeat, doing a binary search.
> > >> If you are right, the nearest rather than the guess is the answer.
> > >
> > > Interesting.  I did not know that one.  Maybe the fact that it's not
> > > linear time makes people overlook it, but there must be times when
> > > neither copying nor rearranging the array is acceptable.
> > >
> > > A bit more searching suggests that some people call this Torben's
> > > algorithm.  Do you know the inventor or simply a definite name for it?
> > 
> > That's a first name and probably not that of the originator.  Does
> > anyone know more about it?
> > 
> > (I've changed the subject and set Followup-To: comp.programming.)
> > 
> The algorithm was invented by me, and independently by Torben Mogenson,
> and probably by many other people as well.

AFAIK he is Mogensen, not Mogenson. They likely call it "Torben's
algorithm" to avoid embarrassment of misspelling the last name of
author. ;D

[toc] | [prev] | [next] | [standalone]

#6896

On Sunday, August 21, 2016 at 10:08:50 PM UTC+1, Öö Tiib wrote:
> On Saturday, 20 August 2016 04:08:07 UTC+3, malcolm...@btinternet.com  wrote:
> > On Friday, August 19, 2016 at 11:38:31 PM UTC+1, Ben Bacarisse wrote:
> > > Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> > > 
> > > > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> > > >
> > > >> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
> > > >>>
> > > >>> The O(N log N) method using binary search sounds odd -- the description
> > > >>> does not seem to match any selection algorithm I know.  Can you explain
> > > >>> what you meant?
> > > >>> 
> > > >> Pass through the data, taking maximum and minimum. Then use (max +
> > > >> min)/2 as you first guess for the median. Pass through again counting
> > > >> elements above and below, and the nearest in both directions. If you
> > > >> are wrong, use (max (or min) + guess)/2 as your refined guess and
> > > >> repeat, doing a binary search.
> > > >> If you are right, the nearest rather than the guess is the answer.
> > > >
> > > > Interesting.  I did not know that one.  Maybe the fact that it's not
> > > > linear time makes people overlook it, but there must be times when
> > > > neither copying nor rearranging the array is acceptable.
> > > >
> > > > A bit more searching suggests that some people call this Torben's
> > > > algorithm.  Do you know the inventor or simply a definite name for it?
> > > 
> > > That's a first name and probably not that of the originator.  Does
> > > anyone know more about it?
> > > 
> > > (I've changed the subject and set Followup-To: comp.programming.)
> > > 
> > The algorithm was invented by me, and independently by Torben Mogenson,
> > and probably by many other people as well.
> 
> AFAIK he is Mogensen, not Mogenson. They likely call it "Torben's
> algorithm" to avoid embarrassment of misspelling the last name of
> author. ;D
.
Anyway, I've consulted with the bulging brains on Math Exchange,
and the median may not be more than one standard deviation away
from the mean.
So we can implement a more efficient search. It won't totally
solve the problem of data with an exponential-logarithmic 
distribution, but it will substantially alleviate it.

[toc] | [prev] | [next] | [standalone]

#6898

On Monday, August 22, 2016 at 8:27:50 AM UTC+1, malcolm...@btinternet.com wrote:
> On Sunday, August 21, 2016 at 10:08:50 PM UTC+1, Öö Tiib wrote:
> > On Saturday, 20 August 2016 04:08:07 UTC+3, malcolm...@btinternet.com  wrote:
> > > On Friday, August 19, 2016 at 11:38:31 PM UTC+1, Ben Bacarisse wrote:
> > > > Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> > > > 
> > > > > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> > > > >
> > > > >> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
> > > > >>>
> > > > >>> The O(N log N) method using binary search sounds odd -- the description
> > > > >>> does not seem to match any selection algorithm I know.  Can you explain
> > > > >>> what you meant?
> > > > >>> 
> > > > >> Pass through the data, taking maximum and minimum. Then use (max +
> > > > >> min)/2 as you first guess for the median. Pass through again counting
> > > > >> elements above and below, and the nearest in both directions. If you
> > > > >> are wrong, use (max (or min) + guess)/2 as your refined guess and
> > > > >> repeat, doing a binary search.
> > > > >> If you are right, the nearest rather than the guess is the answer.
> > > > >
> > > > > Interesting.  I did not know that one.  Maybe the fact that it's not
> > > > > linear time makes people overlook it, but there must be times when
> > > > > neither copying nor rearranging the array is acceptable.
> > > > >
> > > > > A bit more searching suggests that some people call this Torben's
> > > > > algorithm.  Do you know the inventor or simply a definite name for it?
> > > > 
> > > > That's a first name and probably not that of the originator.  Does
> > > > anyone know more about it?
> > > > 
> > > > (I've changed the subject and set Followup-To: comp.programming.)
> > > > 
> > > The algorithm was invented by me, and independently by Torben Mogenson,
> > > and probably by many other people as well.
> > 
> > AFAIK he is Mogensen, not Mogenson. They likely call it "Torben's
> > algorithm" to avoid embarrassment of misspelling the last name of
> > author. ;D
> .
> Anyway, I've consulted with the bulging brains on Math Exchange,
> and the median may not be more than one standard deviation away
> from the mean.
> So we can implement a more efficient search. It won't totally
> solve the problem of data with an exponential-logarithmic 
> distribution, but it will substantially alleviate it.

This is the first draft.

double medianbs(const double *x, int N)
{
	double mean = 0.0;
	double	M2 = 0.0;
	double delta;
	double sd;
	int i;
	int less, greater, equal;
	double  minx, maxx, guess, maxltguess, mingtguess;
	double answer;
	int Npasses = 0;

	if (N == 0)
		return 0;
	if (N == 1)
		return x[0];
	if (N == 2)
		return (x[0] + x[1]) / 2;

	for (i = 0; i < N; i++)
	{
		delta = x[i] - mean;
		mean += delta / (i + 1);
		M2 += delta*(x[i] - mean);
	}
	sd = sqrt(M2 / (N -1));

	minx = mean - sd;
	maxx = mean + sd;

	while (1) {
		guess = (minx + maxx) / 2;
		less = 0; greater = 0; equal = 0;
		maxltguess = minx;
		mingtguess = maxx;
		for (i = 0; i<N; i++) {
			if (x[i]<guess) {
				less++;
				if (x[i] > maxltguess)
					maxltguess = x[i];
			}
			else if (x[i]>guess) {
				greater++;
				if (x[i] < mingtguess)
					mingtguess = x[i];
			}
			else equal++;
		}
		if (less <= (N + 1) / 2 && greater <= (N + 1) / 2) 
			break;
		else if (less>greater) maxx = maxltguess;
		else minx = mingtguess;
	}

	if (equal == 0)
	{
		if (less == greater)
			answer = (maxltguess + mingtguess) / 2;
		else if (less > greater)
			answer = maxltguess;
		else
			answer = mingtguess;
	}
	else
	{
		if (less == (N + 1) / 2)
			answer = maxltguess;
		else if (less + equal >= (N + 1) / 2)
		{
			if ((N % 2))
				answer = guess;
			else
			{
				if (less == N / 2)
					answer = (maxltguess + guess) / 2;
				else if (greater == N / 2)
					answer = (mingtguess + guess) / 2;
				else
					answer = guess;
			}
		}
		else
			answer = mingtguess;
	}

	return answer;
}

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web