Re: Delete elements from list..

• To: mathgroup at smc.vnet.net
• Subject: [mg116622] Re: Delete elements from list..
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Tue, 22 Feb 2011 04:41:38 -0500 (EST)

Hi Maarten,

here is one way:

In[207]:= tst = {1, 2, 3, 4, 5, 6, 4, 5, 7, 8, 9}

Out[207]= {1, 2, 3, 4, 5, 6, 4, 5, 7, 8, 9}

In[208]:= Union[Rest[FoldList[Max, -Infinity, tst]]]

Out[208]= {1, 2, 3, 4, 5, 6, 7, 8, 9}

On my machine, for the list sizes you mention, this works in under a second:

In[209]:= largeTest = RandomInteger[{1, 1000}, {1000, 1000}];

In[210]:=
Map[Union[Rest[FoldList[Max, -Infinity, #]]] &, largeTest]; // Timing

Out[210]= {0.782, Null}

If you are ultimately for speed, and have a multi-core machine with a C
compiler installed, then the following is much faster than the above code,
although it won't win the beauty contest:

fn = Compile[{{lst, _Integer, 1}},
Module[{i, temp, len = Length[lst], reslist, solctr},
For[reslist = Table[0, {len}]; temp = 0; i = solctr = 1, i <= len,
i++,
If[temp < lst[[i]], reslist[[solctr++]] = temp = lst[[i]]];];
Drop[reslist, -(len - solctr + 1)]], CompilationTarget -> "C",
RuntimeAttributes -> Listable]

For example:

In[223]:= largeTest1 = RandomInteger[{1, 1000}, {10000, 1000}];

In[226]:= fn[largeTest1]; // AbsoluteTiming

Out[226]= {0.0419922, Null}

So, it is about 200 time faster (I have 6-core desktop, YMMV), than the
shorter functional
solution - this is pretty much the same speed you'd have for hand-written
I guess.

HTH.

Regards,
Leonid

On Tue, Feb 22, 2011 at 3:30 AM, Maarten van der Burgt <
Maarten.VanDerBurgt at kla-tencor.com> wrote:

> Hallo,
>
> I have a list like:
>
> mylist = {1, 2, 3, 4, 5, 6, 4, 5, 7, 8, 9}
>
> I want to delete any element which is not strictly larger than the
> previous element, until my new list has only increasing values.
>
> This means in mylist above I want to delete the 4 and the 5 at position
> 7 and 8.
>
> Any elegant and fast way for doing this?
>
> In practice I want to do this for a large amount (1000) of very large
> lists (1000). So speed is important.
>