MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Delete elements from list..

On Sat, 26 Feb 2011 at 21:19:39 +0100, "Maarten van der Burgt" 
 <Maarten.VanDerBurgt at> wrote
> Ray,
> You are correct:  my rule would reduce {1, 9, 2, 3, 4, 5, 6, 7, 8} to
> {1, 9}.
> But as the y_i data are generally strictly increasing with only a few %
> or less of the points where the y_i make a dip, this is not a problem.
> Maarten

I didn't mean to suggest that your data would be as extreme as the
example I gave. I mostly wanted to make the point that monotonicity
is a symmetric concept, and there is no reason why it should not be
evaluated from right to left. It turns out that it matters: the two
directions pick systematically different sets of points.

Here are two routines that select monotone x,y pairs:
monup works from left to right, mondo works from right to left.

monup = Compile[{{x,_Real,1},{y,_Real,1}}, (* going up *)
Module[{i, j, m, n, rs}, n = Length@x; j = 1; m = y[[j]];
rs = Table[{0.,0.},{n}]; rs[[j]] = {x[[j]],m}; Do[
If[y[[i]] > m, m = y[[i]]; rs[[++j]] = {x[[i]],m}], {i,2,n}];

mondo = Compile[{{x,_Real,1},{y,_Real,1}}, (* going down *)
Module[{i, j, m, n, rs}, n = Length@x; j = n; m = y[[j]];
rs = Table[{0.,0.},{n}]; rs[[j]] = {x[[j]],m}; Do[
If[y[[i]] < m, m = y[[i]]; rs[[--j]] = {x[[i]],m}], {i,n-1,1,-1}];

Generate some sample data:

x = N@Range[n = 1000]; f = Sqrt;
y = f@x + RandomReal[NormalDistribution[],n];

Plot it, along with four different monotone lines:
the true function (green), monup & mondo (red & black),
and the nameless function (blue) that I described
in my post last night.

If speed and closeness to the green line are the important
criteria then the blue line has much to recommend it.

ListPlot[Transpose@{x,y}, PlotRange->All, Frame->True, 
Axes->None, AspectRatio->1, Prolog-> {Thickness[.005],
 Red,   Line@monup[x,y],
 Green, Line@Transpose@{x,f@x}, 
 Blue,  Line@Transpose@{x,Sort@y}, 
 Black, Line@mondo[x,y],
 PointSize[.005]}, ImageSize->450{1,1}]

> -----Original Message-----
> From: Ray Koopman [mailto:koopman at]
> Sent: Friday, 25 February, 2011 12:37
> To: mathgroup at
> Subject: [mg116732] Re: Delete elements from list..
> On Feb 24, 3:29 am, "Maarten van der Burgt" <Maarten.VanDerBu...@kla-
>> wrote:
>> Hallo,
>> Thanks everybody who replied to my questions.
>> The real problem I have is just a bit more complex than my
>> simplified example. My list is in fact a numerical 2D list like
>> mylist1 == {{x_0, y_0}, {x_1,y_1},... {x_i, y_i}, ...{x_N, y_N}}.
>> The xi are strictly increasing and the yi should be as well.
>> Due to some measurement errors it can happen that this is not the
>> case. I simply want to delete the {xi, yi} pairs where
>> y_i <== y_i-1. That way I end up with a list, mylist2,
>> where also the y_i are strictly increasing.
>> (that way I can make an Interpolation[Reverse/@mylist2]
>> in order to have a function x_i(y_i)).
>> I have not had the time to study your answers in this view,
>> but from a first look and the variety of the answers it seems
>> that there is definitely something which should help.
>> Thanks for your help.
>> Maarten
> Your rule would you reduce {1, 9, 2, 3, 4, 5, 6, 7, 8} to {1, 9}
> which I don't think you would want to do.
> Wouldn't it make more sense to delete only the 9?
> (If we work from right to left instead of left to right,
> deleting the current y if it's >= min[all previous kept y_i],
> we do delete only the 9.)
> Shouldn't the question be more like "What is the smallest set of
> points that must be deleted to make y monotone increasing in x?"
> Or, considering that all the y_i may contain error, you could find
> the vector z that is closest to y (in some sense that depends on the
> assumed nature of the errors) and is also monotone increasing in x,
> and then do inverse interpolation.

  • Prev by Date: Re: Getting an image with JLink
  • Next by Date: Re: Vector Runge-Kutta ODE solver with compilation?
  • Previous by thread: Re: Delete elements from list..
  • Next by thread: Rational[a,b] vs Rational[1,2]