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 subsequenceNB. 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 indexNB. 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 PredecessorsDoBetweenElementsInFold=: ([,(Values I. [ )) ( [ (Values;Indices;AmendPredecessors;1+Index) AmendValues;AmendIndices;Predecessors;Index) ]Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: # Indices);[: {: Indices) [: > ]LongestIncreasingSubsequenceIndices=: [: Reconstruct [: DoBetweenElementsInFold&.:>/ ([: |. PackValues) , ValuesIndicesPredecessorsIndexInitialStateLongestIncreasingSubsequence=: ([: 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 largerNB. than the drawn element. Selects one of the longest of these groups if one exists and prependsNB. 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 startsNB. 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 , GroupOfEmptyGroupInitialStateLongestIncreasingSubsequence=: LongestIncreasingSubsequence f. Full project of tacit version ======================= NB. Find the longest stricty increasing subsequenceNB. 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 indexNB. 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;1ValuesIndicesPredecessorsIndexInitialState=: [: < 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;0DoBetweenElementsInFold=: ([,(Values I. [ )) ( [ (Values;Indices;AmendPredecessors;1+Index) AmendValues;AmendIndices;Predecessors;Index) ]3 DoBetweenElementsInFold 1 2;1 2;0 1 1 2;3Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: # Indices);[: {: Indices) [: > ]Reconstruct < 1 2 3;1 2 3;0 1 1 2;4LongestIncreasingSubsequenceIndices=: [: 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 3Reconstruct < (3 DoBetweenElementsInFold ( 2 DoBetweenElementsInFold ( 1 DoBetweenElementsInFold ( 7 DoBetweenElementsInFold [: > ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3LongestIncreasingSubsequence=: ([: 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
