[Jprogramming] Greatest Increasing Subsequence
Erling Hellenäs
erling at erlinghellenas.se
Wed Sep 14 08:30:13 UTC 2016
I can't verify that. For some values it is faster, yes, but it seems
measurements with 1 000 000 items shows your original assumption was
correct. See below. /Erling
NB. Find the longest ascending subsequence in y
NB. y is a list of numbers
NB. Result is indexes of the values that form the largest ascending
sequence in y
longascseq1 =: 3 : 0"1
NB. Initialize the arrays
valueofminendvalue =. indexofminendvalue =. 0$0
predecessor =. (#y)$2
NB. process the input
for_v. y do.
NB. j{indexofminendvalue is the index in the original input of the smallest
NB. input value that ends a sequence of length j+1. valueofminendvalue is
NB. the corresponding value.
NB. When a new value v comes in, we see how many previous values are
smaller;
NB. calling that value j, we see that the new value becomes the smallest
value
NB. that ends a subsequence of length j+1
if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
NB. New highest value (and therefore new greatest length): extend the arrays
valueofminendvalue =. valueofminendvalue , v
indexofminendvalue =. indexofminendvalue , v_index
else.
NB. New low value for an existing length: update for that length
valueofminendvalue =. v j} valueofminendvalue
indexofminendvalue =. v_index j} indexofminendvalue
end.
NB. Get a snapshot of the predecessor to the added point at the time it was
NB. added. This predecessor is given by the end of the next-shorter
subsequence.
predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB.
wraps if j=0, but who cares?
end.
NB. Reconstruct the chain of predecessors from the end
predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue
)
NB. Find the longest ascending subsequence in y
NB. y is a list of numbers
NB. Result is indexes of the values that form the largest ascending
sequence in y
longascseq2 =: 3 : 0"1
NB. Initialize the arrays
valueofminendvalue =. indexofminendvalue =. 0$0
predecessor =. (#y)$2
NB. process the input
for_v. y do.
NB. j{indexofminendvalue is the index in the original input of the smallest
NB. input value that ends a sequence of length j+1. valueofminendvalue is
NB. the corresponding value.
NB. When a new value v comes in, we see how many previous values are
smaller;
NB. calling that value j, we see that the new value becomes the smallest
value
NB. that ends a subsequence of length j+1
NB. if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.
NB. valueofminendvalue =. valueofminendvalue , v
indexofminendvalue =. indexofminendvalue , v_index
else.
NB. valueofminendvalue =. v j} valueofminendvalue
indexofminendvalue =. v_index j} indexofminendvalue
end.
NB. Get a snapshot of the predecessor to the added point at the time it was
NB. added. This predecessor is given by the end of the next-shorter
subsequence.
predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB.
wraps if j=0, but who cares?
end.
NB. Reconstruct the chain of predecessors from the end
predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue
)
l
7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
(longascseq1 { ])l
1 2 3 4 5 7 11 19
(longascseq2 { ])l
1 2 3 4 5 7 11 19
a=:10000?10000
(([: longascseq1 ]) *./ . = [: longascseq2 ])a
1
ts'(longascseq1 { ]) 10000?10000'
0.0439489 830592
ts'(longascseq2 { ]) 10000?10000'
0.0415926 830720
ts'(longascseq1 { ]) ?10000$10000'
0.044282 439424
ts'(longascseq2 { ]) ?10000$10000'
0.0410495 435840
ts'(longascseq1 { ]) 100000?100000'
0.446059 6.42803e6
ts'(longascseq2 { ]) 100000?100000'
0.468622 6.41946e6
ts'(longascseq1 { ]) ?100000$100000'
0.447244 3.28205e6
ts'(longascseq2 { ]) ?100000$100000'
0.458428 3.27373e6
ts'(longascseq1 { ]) 1000000?1000000'
4.55264 5.07078e7
ts'(longascseq2 { ]) 1000000?1000000'
5.98209 5.06932e7
ts'(longascseq1 { ]) ?1000000$1000000'
4.42172 2.55429e7
ts'(longascseq2 { ]) ?1000000$1000000'
5.83236 2.55252e7
On 2016-09-13 20:38, 'Mike Day' via Programming wrote:
> Actually, the hit on run time gets more significant as the length of the
> sequence and/or the optimal subsequence increase, so it's not negligible
> for, say, ?1000000#500000, but fine for ?10000#5000, and not too bad
> for ?100000#50000
>
> Mike
>
> On 13/09/2016 19:22, 'Mike Day' via Programming wrote:
>> Thanks.
>>
>> It might help to point out that the main loop in Henry Rich's version,
>> as shown in the wiki page, can be simplified slightly with negligible
>> effect on run time, some savings in space, and doing without the
>> "sorted value" array.
>>
>> I'm rather surprised - I'd introduced the array which I'd called mx,
>> more helpfully called valeofminendvalue by Henry, to avoid repeated
>> indirect look-up into the raw input.
>>
>> Here's a copy of the relevant part of the loop with the removed or
>> former code commented out:
>>
>> NB. if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
>> if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.
>> NB. valueofminendvalue =. valueofminendvalue , v
>> indexofminendvalue =. indexofminendvalue , v_index
>> else.
>> NB. valueofminendvalue =. v j} valueofminendvalue
>> indexofminendvalue =. v_index j} indexofminendvalue
>> end.
>>
>> I won't venture to suggest changes in your code, below!
>>
>> Mike
>>
>> On 13/09/2016 17:17, Erling Hellenäs wrote:
>>> Hi all !
>>>
>>> My first idea only took me down to 1 second for 10 000 numbers, 25
>>> times longer than longscseq. I then made a tacit version of
>>> longascseq. It still takes about 4 times longer than longascseq.
>>>
>>> See these two versions below.
>>>
>>> I included the full project of the tacit version.
>>>
>>> Cheers,
>>>
>>> Erling
>>>
>>> NB. Find the longest stricty increasing subsequence
>>>
>>> NB. Values are the lowest last values yet found for each subsequence
>>> length.
>>>
>>> NB. Indices are the indices of these values in the original sequence.
>>>
>>> NB. Predecessors are indices to the end of the next lower subsequence
>>>
>>> NB. for each value in the original sequence.
>>>
>>> NB. The longest sequence is found by index lookup in predecessors
>>> from the index
>>>
>>> NB. of the highest found value.
>>>
>>>
>>> Amend=:([:>[:{.[)`([:>[:{:[)`] }
>>>
>>> PickPower=: {~^:([`([:>[:{.])`([:>[:{:]))
>>>
>>> ValuesIndicesPredecessorsIndexInitialState=: [: < a:"_ , a:"_ , (([:
>>> # ]) $2:) ;0:
>>>
>>> PackValues=: <@+
>>>
>>> Values=: [: > 0 { ]
>>>
>>> Indices=: [: > 1 { ]
>>>
>>> Predecessors=: [: > 2 { ]
>>>
>>> Index=: [: > 3 { ]
>>>
>>> AdjustLength=: ((1 + [) >. [: # ]) {. ]
>>>
>>> AmendValues=: (([: {. [) ; [: {: [) Amend ([: {: [) AdjustLength Values
>>>
>>> AmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLength Indices
>>>
>>> AmendPredecessors=: ((([: <: [: {: [){Indices);Index ) Amend
>>> Predecessors
>>>
>>> DoBetweenElementsInFold=: ([,(Values I. [ )) ( [
>>> (Values;Indices;AmendPredecessors;1+Index)
>>> AmendValues;AmendIndices;Predecessors;Index) ]
>>>
>>> Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: #
>>> Indices);[: {: Indices) [: > ]
>>>
>>> LongestIncreasingSubsequenceIndices=: [: Reconstruct [:
>>> DoBetweenElementsInFold&.:>/ ([: |. PackValues) ,
>>> ValuesIndicesPredecessorsIndexInitialState
>>>
>>> LongestIncreasingSubsequence=: ([:
>>> LongestIncreasingSubsequenceIndices ]){ ]
>>>
>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>
>>> NB. This is a solution to the problem of finding the longest
>>> strictly increasing subsequence.
>>>
>>> NB. Draws numbers from the end of the sequence. Selects groups with
>>> its first element larger
>>>
>>> NB. than the drawn element. Selects one of the longest of these
>>> groups if one exists and prepends
>>>
>>> NB. the drawn number. If no such group exists create a new group
>>> containing the drawn number.
>>>
>>> NB. Removes groups which are both shorter than the new group or of
>>> equal length and which starts
>>>
>>> NB. with a number which is smaller or equal to the number which
>>> starts the new group.
>>>
>>> NB. Append the new group to the remaining groups.
>>>
>>> NB. When all numbers are drawn one of the longest remaining groups
>>> is selected.
>>>
>>>
>>> GroupOfEmptyGroupInitialState=: [: < a:"_
>>>
>>> PackElements=: <@+
>>>
>>> StartsWithLonger=: ([: {.@> [) < [: {.@> ]
>>>
>>> Longer=:([: #@> [) < [: #@> ]
>>>
>>> SelectLongerOrStartsWithLonger=: (Longer +. StartsWithLonger ) # ]
>>>
>>> SelectGroupsWithLeftLessThanFirstElement=: ([ < [: {.@> ]) # ]
>>>
>>> SelectFirstGroupOfMaxLength=: ((1 <. [: # ]) {. [: I. [: (] = [: >./
>>> ]) #@>) { ]
>>>
>>> PrependLeftInGroups=: ([: < [) ,&.> ]
>>>
>>> AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]
>>>
>>> DoBetweenElementsInFold=: ([: {. [ AddGroupWithLeftIfNoGroups [
>>> PrependLeftInGroups [: SelectFirstGroupOfMaxLength
>>> SelectGroupsWithLeftLessThanFirstElement ) ([ ,
>>> SelectLongerOrStartsWithLonger) ]
>>>
>>> LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength
>>> [: > [: DoBetweenElementsInFold&.:>/ PackElements ,
>>> GroupOfEmptyGroupInitialState
>>>
>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>
>>>
>>> Full project of tacit version
>>>
>>> =======================
>>>
>>>
>>> NB. Find the longest stricty increasing subsequence
>>>
>>> NB. Values are the lowest last values yet found for each subsequence
>>> length.
>>>
>>> NB. Indices are the indices of these values in the original sequence.
>>>
>>> NB. Predecessors are indices to the end of the next lower subsequence
>>>
>>> NB. for each value in the original sequence.
>>>
>>> NB. The longest sequence is found by index lookup in predecessors
>>> from the index
>>>
>>> NB. of the highest found value.
>>>
>>>
>>> ts=: 6!:2 , 7!:2@] NB. Time and space
>>>
>>> Amend=:([:>[:{.[)`([:>[:{:[)`] }
>>>
>>> (1;0) Amend 3 4 5
>>>
>>> PickPower=: {~^:([`([:>[:{.])`([:>[:{:]))
>>>
>>> 2 3 4 PickPower 1;1
>>>
>>> ValuesIndicesPredecessorsIndexInitialState=: [: < a:"_ , a:"_ , (([:
>>> # ]) $2:) ;0:
>>>
>>> ValuesIndicesPredecessorsIndexInitialState 7 1 2 3
>>>
>>> PackValues=: <@+
>>>
>>> PackValues 7 1 2 3
>>>
>>> Values=: [: > 0 { ]
>>>
>>> Values 1 2 3;0 1 2;2 2 2;0
>>>
>>> Indices=: [: > 1 { ]
>>>
>>> Indices 1 2 3;0 1 2;2 2 2;0
>>>
>>> Predecessors=: [: > 2 { ]
>>>
>>> Predecessors 1 2 3;0 1 2;2 2 2;0
>>>
>>> Index=: [: > 3 { ]
>>>
>>> Index 1 2 3;0 1 2;2 2 2;0
>>>
>>> AdjustLength=: ((1 + [) >. [: # ]) {. ]
>>>
>>> 3 AdjustLength 1 2 3
>>>
>>> 2 AdjustLength 1 2 3
>>>
>>> AmendValues=: (([: {. [) ; [: {: [) Amend ([: {: [) AdjustLength Values
>>>
>>> (7,3) AmendValues 1 2 3;0 1 2;2 2 2;0
>>>
>>> AmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLength Indices
>>>
>>> (7,3) AmendIndices 1 2 3;0 1 2;2 2 2;0
>>>
>>> AmendPredecessors=: ((([: <: [: {: [){Indices);Index ) Amend
>>> Predecessors
>>>
>>> (7,3) AmendPredecessors 1 2 3;0 1 2;2 2 2;0
>>>
>>> DoBetweenElementsInFold=: ([,(Values I. [ )) ( [
>>> (Values;Indices;AmendPredecessors;1+Index)
>>> AmendValues;AmendIndices;Predecessors;Index) ]
>>>
>>> 3 DoBetweenElementsInFold 1 2;1 2;0 1 1 2;3
>>>
>>> Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: #
>>> Indices);[: {: Indices) [: > ]
>>>
>>> Reconstruct < 1 2 3;1 2 3;0 1 1 2;4
>>>
>>> LongestIncreasingSubsequenceIndices=: [: Reconstruct [:
>>> DoBetweenElementsInFold&.:>/ ([: |. PackValues) ,
>>> ValuesIndicesPredecessorsIndexInitialState
>>>
>>> ( 7 DoBetweenElementsInFold [: >
>>> ValuesIndicesPredecessorsIndexInitialState)7 1 2 3
>>>
>>> ( 1 DoBetweenElementsInFold (7 DoBetweenElementsInFold [: >
>>> ValuesIndicesPredecessorsIndexInitialState))7 1 2 3
>>>
>>> ( 2 DoBetweenElementsInFold (1 DoBetweenElementsInFold (7
>>> DoBetweenElementsInFold [: >
>>> ValuesIndicesPredecessorsIndexInitialState)))7 1 2 3
>>>
>>> ( 3 DoBetweenElementsInFold (2 DoBetweenElementsInFold (1
>>> DoBetweenElementsInFold (7 DoBetweenElementsInFold [: >
>>> ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3
>>>
>>> Reconstruct < (3 DoBetweenElementsInFold ( 2 DoBetweenElementsInFold
>>> ( 1 DoBetweenElementsInFold ( 7 DoBetweenElementsInFold [: >
>>> ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3
>>>
>>> LongestIncreasingSubsequence=: ([:
>>> LongestIncreasingSubsequenceIndices ]){ ]
>>>
>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>
>>> LongestIncreasingSubsequence 7 1 2 3
>>>
>>> LongestIncreasingSubsequence i.0
>>>
>>> LongestIncreasingSubsequence 6 1 3 4 2 8
>>>
>>> l =: 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
>>>
>>> LongestIncreasingSubsequence l
>>>
>>> 9!:1 [16807
>>>
>>> [a=:LongestIncreasingSubsequence 1000?1000
>>>
>>> #a
>>>
>>> 9!:1 [16807
>>>
>>> [a=:LongestIncreasingSubsequence ?1000$1000
>>>
>>> #a
>>>
>>> ts=: 6!:2 , 7!:2@] NB. Time and space
>>>
>>> ts'LongestIncreasingSubsequence 10000?10000'
>>>
>>> ts'LongestIncreasingSubsequence ?10000$10000'
>>>
>>>
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
More information about the Programming
mailing list