The boxing is a measurable performance issue, since you wind up doing a lot
of boxed operations.

The reversing is not a measurable performance issue, since it only happens
twice and because the overall algorithm is does so much more work.

Both of these are "conciseness" issues, however. But if conciseness were
the overriding goal then at some point you would be considering explicit
code.

-- 
Raul


On Fri, Sep 16, 2016 at 3:23 AM, Erling Hellenäs <erl...@erlinghellenas.se>
wrote:

> Other things we can note about creating a tacit version of this algorithm:
>
> -To use Insert to process the input array,  the items of this array has to
> be boxed, since the initial state can not be an integer. This adds a lot of
> Box and Open operations.
>
> -There is also only one Insert. There is no reverse Insert. This means
> either the algorithm has to be changed to work backwards, or the input
> array has to be reversed.
>
> As we can see here, in F# there is a Fold and a FoldBack and there is a
> separate initial state.
>
> https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual
> /array.fold%5B't,'state%5D-function-%5Bfsharp%5D
>
> Cheers,
>
> Erling
>
>
>
> On 2016-09-15 14:12, Henry Rich wrote:
>
>> Tacitly appending to an array requires a copy; so does tacit amending.
>> Thus, any tacit version is going to have quadratic performance.
>>
>> But I am working on making (x , y) and (x m} y) operate in-place even in
>> tacit forms.  It will be a couple of months before that gets into a beta.
>>
>> Henry Rich
>>
>> On 9/15/2016 7:50 AM, 'Mike Day' via Programming wrote:
>>
>>> Interesting!  That wikipedia reference to Fredman is misleading,  to
>>> say the least.  It misled me, anyway.   I'll have a look at whether it's
>>> ok if one works with indices rather than values,  as in longascseq.
>>>
>>> The tacit closure was nice, though...
>>>
>>> Thanks,
>>> Mike
>>>
>>> On 15/09/2016 11:05, Erling Hellenäs wrote:
>>>
>>>> lisf =: 3 : 0
>>>>
>>>> x =. y
>>>>
>>>> if. 2>#x do. x return. end.
>>>>
>>>> T =. {.x
>>>>
>>>> for_xj. }.x do.
>>>>
>>>> if. xj > {:T do.
>>>>
>>>> T =. T, xj
>>>>
>>>> else.
>>>>
>>>> m =. T I. xj
>>>>
>>>> NB. if. xj < m { T do. Slight impairment with this test
>>>>
>>>> T =. xj m } T
>>>>
>>>> NB. end.
>>>>
>>>> end.
>>>>
>>>> end.
>>>>
>>>> T
>>>>
>>>> )
>>>>
>>>> lisf 6 1 3 4 2 8
>>>>
>>>> 1 2 4 8
>>>>
>>>>
>>>> As we can see the result is not correct. The length is correct and that
>>>> is what the Fredman/Knuth algorithm calculates I think.
>>>>
>>>> I also tried the algorithm. Many results are correct, I was lucky to
>>>> have this test to show that it was wrong. Then I examined the Fredman paper
>>>> a bit more.
>>>>
>>>>
>>>> /Erling
>>>>
>>>>
>>>> On 2016-09-15 11:52, Erling Hellenäs wrote:
>>>>
>>>>> The Fredman paper is about calculation of the length L of the longest
>>>>> increasing subsequence, not the calculation of the longest increasing
>>>>> subsequence as such. The algorithm only computes "valueofminendvalue" I
>>>>> think. /Erling
>>>>>
>>>>>
>>>>> On 2016-09-14 23:27, 'Mike Day' via Programming wrote:
>>>>>
>>>>>> I suspect it's pretty near optimal. The wikipedia article points at
>>>>>> Fredman's paper:
>>>>>> http://www.sciencedirect.com/science/article/pii/0012365X7590103X
>>>>>> analysing an algorithm of Knuth's.  He shows that it performs better
>>>>>> than
>>>>>>    n log2(n) - n log2 log2 (n) + O(n)
>>>>>> rather than the O(n logn) cited for the function we've been looking
>>>>>> at.
>>>>>>
>>>>>> I might have a play at tacit for the algorithm already discussed.
>>>>>>
>>>>>> Mike
>>>>>>
>>>>>> On 14/09/2016 14:57, Erling Hellenäs wrote:
>>>>>>
>>>>>>> Any ideas about how you could make a substantially faster tacit
>>>>>>> solution to this problem or how you could make this solution 
>>>>>>> substantially
>>>>>>> faster? /Erling
>>>>>>>
>>>>>>>
>>>>>>> On 2016-09-13 18: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/forum
>>>>>>>> s.htm
>>>>>>>>
>>>>>>>
>>>>>>> ----------------------------------------------------------------------
>>>>>>>
>>>>>>> For information about J forums see http://www.jsoftware.com/forum
>>>>>>> s.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/forum
>>>>>> s.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
>>>
>>
>> ----------------------------------------------------------------------
>> 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

Reply via email to