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
