(x I. y) does use binary search, and requires that y be either
nonincreasing or nondecreasing.
Length of names has a tiny effect on performance, as the interpreter has
to compare the name against a stored name. It is barely noticeable;
slightly more noticeable when J8.05 added a fast path for singleton
operations; disappears for local names now that J8.05 prehashes names
assigned by local assignment. Not worth mentioning, except that the
difference between the two programs was so small.
Henry Rich
On 9/10/2016 3:58 AM, 'Mike Day' via Programming wrote:
Yes. It clearly saves space to have "valueofminendvalue", my "mx",
grow
as it needs, rather than to start with maximal length. I hadn't
spotted how
to avoid indexed assignment when your "j", my "lo", increases. No need
for those clunky _1s in the index array!
So then I'm surprised that my space-hungry version doesn't suffer a hit
on the performance of dyadic I. on the maximal length mx . Does it
use binary
search?
Also, has length of variable names affected performance in early J
versions?
I'm just lazy and all thumbs, so have avoided long names!
Thanks,
Mike
On 10/09/2016 00:39, Henry Rich wrote:
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
---
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
