[Jprogramming] Greatest Increasing Subsequence

Sat Sep 10 13:27:39 UTC 2016

(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