Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm