Question 1
LongestAscendingSequence
was an undocumented in symbol in M10.1 and earlier, and has been removed as of M10.2+. In M10.2 the symbol LongestOrderedSequence
was added, but it's functionality is slightly different. So, I thought it might be helpful to provide an answer to part 1 of this question that works in M10.2+.
The main difference between the two functions is that LongestAscendingSequence
returned a strictly ascending sequence, while LongestOrderedSequence
returns a non-descending sequence. In other words, LongestOrderedSequence
includes duplicates, while LongestAscendingSequence
did not. One possibility is to define a new LongestAscendingSequence
using LongestCommonSequence
:
LongestAscendingSequenceSlow[list_] := LongestCommonSequence[list, Union[list]]
However, this is rather slow:
list = RandomInteger[10^6, 10^6];
LongestAscendingSequenceSlow[list]; //AbsoluteTiming
{1.39408, Null}
On the other hand, it is possible to use LongestOrderedSequence
to produce a much faster version:
LongestAscendingSequence[list_] := Which[
Developer`PackedArrayQ[list, Real],
LongestOrderedSequence[Transpose[{list, -1. Range @ Length @ list}]][[All, 1]],
True,
LongestOrderedSequence[Transpose[{list, - Range @ Length @ list}]][[All, 1]]
]
And here is a speed comparison:
r1 = LongestAscendingSequenceSlow[list]; //AbsoluteTiming
r2 = LongestAscendingSequence[list]; //AbsoluteTiming
Length @ r1 === Length @ r2
{1.40971, Null}
{0.098286, Null}
True
Question 2
Now, it is also possible to speed up the second question as follows:
longestAscendingSubsequence[list_] := With[
{diff=SparseArray[Differences[-list]//UnitStep]},
{nzp=Flatten @ diff["NonzeroPositions"]},
{runs=Differences[nzp]},
{ord=1+Length[runs]-First@Ordering[Reverse@runs,-1]},
Take[list, nzp[[ord]] + {1, runs[[ord]]}]
]
(I used the new form of With above, although its syntax coloring is completely wrong). A comparison with longest1
and longest2
(I didn't compare @JacobAkkerboom's function because it is designed to work for integers):
SeedRandom[0];
list = RandomReal[NormalDistribution[], 1000000];
longest1[list] //AbsoluteTiming
longest2[list] //AbsoluteTiming
longestAscendingSubsequence[list] //AbsoluteTiming
{0.504056, {-2.34409, -1.21854, -0.951283, -0.873138, -0.744772, -0.157809,
0.380566, 1.36488, 1.65743}}
{0.096426, {-2.34409, -1.21854, -0.951283, -0.873138, -0.744772, -0.157809,
0.380566, 1.36488, 1.65743}}
{0.035699, {-2.34409, -1.21854, -0.951283, -0.873138, -0.744772, -0.157809,
0.380566, 1.36488, 1.65743}}
Finally, note that longest2
doesn't work correctly if there are duplicate points:
longest1[{1., 1., 1., 1., 2., 2., 2.}]
longest2[{1., 1., 1., 1., 2., 2., 2.}]
longestAscendingSubsequence[{1., 1., 1., 1., 2., 2., 2.}]
{1., 2.}
{1., 1., 1., 1., 2., 2., 2.}
{1., 2.}