They're about the same speed on my machine. I don't think the
if-then-else is material. They're essentially the same algorithm.
(I'm testing on J8.05 beta, where the long names don't affect performance)
Henry Rich
On 9/9/2016 7:26 PM, 'Mike Day' via Programming wrote:
Thanks.
I'm sure you know the following, but it might be worth pointing out:
longascseq l
6 9 20 21 22 25 26 27
l{~longascseq l
1 2 3 4 5 7 11 19
lisM l
1 2 3 4 5 7 11 19
ie, longascseq returns the indices of the/a subsequence.
Very limited testing suggests that it's a little bit slower,
(on 10000 elements) but saves space compared to the function,
lisM, that I posted earlier. I suppose that's because of the
if-then-else block, though I haven't studied their differences
yet.
Cheers,
Mike
On 09/09/2016 20:09, Henry Rich wrote:
I have created a Wiki page for this, where you can post solutions.
http://code.jsoftware.com/wiki/Essays/Longest_Increasing_Subsequence
I don't think a tacit solution can be efficient, considering how many
in-place operations are needed.
Henry Rich
On 9/9/2016 1:46 PM, Erling Hellenäs wrote:
Hi all !
This one is considerably faster, near lisJ.
ts'LongestIncreasingSubsequence 10000?10000'
2.40974 3.808e6
ts'LongestIncreasingSubsequence ?10000$10000'
2.46657 3.41504e6
It still uses a lot of memory. Handles 100 000 with quite some
struggle.
ts'LongestIncreasingSubsequence ?100000$100000'
81.525 3.30742e7
Cheers,
Erling
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. Append the new group to the previous groups.
NB. Removes groups which are both shorter than the new group and
which starts
NB. with a number which is smaller or equal to the number which
starts the new group.
NB. When all numbers are drawn one of the longest remaining groups
is selected.
GroupOfEmptyGroupInitialState=: [: < a:"_
GroupOfEmptyGroupInitialState ''
PackElements=: <@+
PackElements 6 1 3 4 2 8
SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@>
]) # ]
PrependLeftInGroups=: ([: < [) ,&.> ]
2 PrependLeftInGroups <4 5
AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]
2 AddGroupWithLeftIfNoGroups 0 {. <i.0
2 AddGroupWithLeftIfNoGroups , <1 2
SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = ''
$ [: >./ ]) #@>)) { ]
SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7
StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [
Shorter=: ([: #@> ])<[: {. [
LengthAndFirstElement=: [: (# , {.) [: > ]
SelectNotShorterAndStartsWithSmallerOrEqual=: (([:
LengthAndFirstElement [: {: ]) ( ([: -. Shorter
*.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) , [: {: ]
SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4
5),(< 1 4 5));2 6 7
DoBetweenElementsInFold=: [:
SelectNotShorterAndStartsWithSmallerOrEqual ] ; [
AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [:
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement
2 DoBetweenElementsInFold (<1 2 3),<4 5
LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength
[: > [: DoBetweenElementsInFold&.:>/ PackElements ,
GroupOfEmptyGroupInitialState
LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
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
LongestIncreasingSubsequence 1000?1000
9!:1 [16807
LongestIncreasingSubsequence ?1000$1000
ts=: 6!:2 , 7!:2@] NB. Time and space
ts'LongestIncreasingSubsequence 1000?1000'
ts'LongestIncreasingSubsequence ?1000$1000'
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
---
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
