[Jprogramming] Greatest Increasing Subsequence
'Mike Day' via Programming
programming at jsoftware.com
Wed Sep 14 09:24:22 UTC 2016
It depends on both m and n in ?m#n
Also, note that it's better to move definition of the input outside the
time
(and space) test.
Using ?. to fix the samples, and 1 ts to save waiting on longer arguments:
ts each '#longascseq1 q';'#longascseq2 q'[q =: ?.~100000NB. set outside
+------------------+------------------+
|0.475994 1.18106e6|0.675194 1.17299e6|
+------------------+------------------+
ts each '#longascseq1 ?.~100000';'#longascseq2 ?.~100000' NB. set inside
+------------------+------------------+
|0.493492 6.42419e6|0.629799 6.41613e6|
+------------------+------------------+
1 ts each '#longascseq1 q';'#longascseq2 q'[q =: ?.~1000000
+-----------------+-----------------+
|3.38978 8.74317e6|7.69395 8.72691e6|
+-----------------+-----------------+
1 ts each '#longascseq1 ?.~1000000';'#longascseq2 ?.~1000000'
+-----------------+----------------+
|3.71289 5.06865e7|8.4527 5.06702e7|
+-----------------+----------------+
It appears that the estimate of space used is more strongly influenced
than time, here.
I'm wondering why you tested equality in this way:
(([: longascseq1 ]) *./ . = [: longascseq2 ])a
Isn't it sufficient to test
(longascseq1 -: longascseq2 )l
1 ?
Thanks,
Mike
On 14/09/2016 09:30, Erling Hellenäs wrote:
> 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
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
More information about the Programming
mailing list