I’m trying to rewrite lisM in a readable tacit form but hit something I didn’t
understand.
Supplying i.n to ^: works fine, but <n does not work like the dictionary says.
Namely
(_1+i.5){~^:(i.4)4
produces 4 3 2 1, but
(_1+i.5){~^:(<4)4
exhausts all the memory with J804 and J805beta.
The dictionary says
If n is boxed it must be an atom, and u^:(<m)
↔ u^:(i.m) y if m is a non-negative integer
so the above two should be the same. What’s going on here?
> On Sep 5, 2016, at 3:17 AM, 'Mike Day' via Programming
> <[email protected]> wrote:
>
> Thanks Jon
>
> lisM isn't really "my" version - I was just translating the pseudo-code...
> I expect -without checking! - that its advantage over lisl resides in
> avoiding the do-it-yourself binary search by using J's built-in dyadic I. ,
> albeit at the expense of an explicit sorted array, which I called mx . I
> tried limiting the I. search to only the first L items of mx, but with no
> benefit, at least for the sizes I tried.
> The time taken to recover the result is fairly trivial, so I don't suppose
> my use of
> |. x{~(p{~])^:(i.L) L{m
> is particularly interesting, but it avoided that explicit while loop.
>
> Mike
>
> Please reply to [email protected].
> Sent from my iPad
>
>> On 5 Sep 2016, at 08:07, 'Jon Hough' via Programming
>> <[email protected]> wrote:
>>
>> Just out of interest, I compared the various results.
>> I wrote a fully imperative version, which uses in-place modification of the
>> results array.
>>
>> I also wrote a version that avoids any while / for loops (because I wanted
>> to avoid using them), and ended up putting
>> most of the logic in anonymous verbs. Which is probably a big mistake
>> because that gets very slow. Also barely readable.
>>
>> NB.===========================================================================
>>
>> NB. Jon - bizarre version. Uses anonymous verbs for most of the logic.
>> NB. Slow and, uses huge amounts of memory.
>> appendOrInsert=:(3 : 'insert max' [ 3 :
>> '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 : '(lst=:lst,y)[prev=:(_1{lst) y}
>> prev')@.(3 : '(val>({:lst){r)[val=:y{r')
>> insert=:(3 : '(prev=: ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
>> 'mid'`(3 : 'min=: mid+1')@.(3 :
>> '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
>>
>> lisJ =: 3 : 0
>> r=:y NB. array
>> [val=:0[max=:0[mid=:0[min=:0 NB. useful numbers
>> lst=:0 NB. list of indices
>> prev=: (#y)#0 NB. previous indices
>> i=:0 NB. current index
>>
>> appendOrInsert"0 >: i.<: # y NB. append the items, or insert them, into
>> lst (and update prev)
>> res=:''
>> ptr=: _1{lst
>> (ptr&buildEx)^:(#lst) res
>> |. res
>> )
>>
>> buildEx =: 4 : 0
>> res=:y,ptr{r
>> ptr=: ptr{prev
>> res
>> )
>>
>>
>> NB.===========================================================================
>>
>>
>> NB. Imperative version. just for benchmarking
>> lisI =: 3 : 0
>> lst =: 0
>> r=: y
>> parent=: (#y)#0
>> for_i.>:i.<:# r do.
>> if.((i{r) > ({: lst){r ) do.
>> parent=:(_1{lst) i}parent
>> lst =: lst, i
>> else.
>> min=: 0
>> max =: <:#lst
>> while. min < max do.
>> mid =: <. (min + max) % 2
>> if. (i{r) > ((mid { lst{r)) do. min =: mid + 1
>> else. max =: mid end.
>> end.
>> lst=: (i) max} lst
>> parent=: ((max-1){lst)(i}) parent
>> end.
>> end.
>> res=: ''
>> ptr=: _1{lst
>> while. (# res) < # lst do.
>> res=:res,ptr{r
>> ptr=:ptr{parent
>> end.
>> I. res
>> )
>>
>>
>>
>> NB.===========================================================================
>>
>>
>> NB. Mike's version.
>>
>> lisM =: 3 : 0
>> n =. #x =. y
>> if. 2>#x do. x return. end. NB. special case empty or singleton array
>> if. (-:/:~)x do. ~.x return. end. NB. special case sorted arrays
>> if. (-:\:~)x do. {.x return. end.
>> p =. n#0
>> NB. seed m with trailing _1 so that final L (as in wiki algorithm) can be
>> found
>> m =. n 0 } _1#~>:n
>> NB. set up sorted mx, with just the first element of x, so that I. works
>> mx =. ({.x) 1 } (<:<./x), n#>:>./x
>> for_i. i.n do.
>> xi =. i{x
>> lo =. mx I. xi
>> p =. (m{~<:lo) i } p NB. better than appending to short p for larger x
>> m =. i lo } m
>> mx =. xi lo } mx
>> end.
>> |. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
>> )
>>
>> NB.===========================================================================
>>
>> NB. Louis' version.
>> p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
>> e=: }:@>@(#~ (= >./)@:(#&>))@>
>>
>> s=: [: e (<<_) p&.>/@,~ <"0
>> pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
>> lisL =: [: e (<<_) pi&.>/@,~ <"0 NB.
>> <------------- this one.
>>
>> f=: ((] >: (-~ >./)) #&>) # ]
>>
>> P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
>> sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)
>>
>>
>>
>> NB.===========================================================================
>>
>>
>> NB. Xiao's version with Raul's modifications. Renamed verbs to avoid
>> clashing.
>>
>> NB. dyads
>> exr=: (1 + {:@[ < ]) {. [ ; ,
>> hxr=: [: ; exr&.>
>>
>> NB. monads
>> gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
>> cxr=: ({::~ [: (i. >./) #@>)@>@{.
>> dxr=: (<_) ; ]
>> lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr
>>
>> NB.===========================================================================
>>
>> a=: 25 ? 25
>> timespacex 'lisI a'
>> timespacex 'lisJ a'
>> timespacex 'lisM a'
>> timespacex 'lisL a'
>> timespacex 'lisXR a' NB. comment out for larger arrays,a.
>>
>> Playing around with various arrays, it seems lisM is the most efficient in
>> time and space (more than the imperative version).
>> lisM and lisI can handle array larger than 10000. The others struggle or
>> give up with them.
>>
>>
>> --------------------------------------------
>> On Sun, 9/4/16, 'Mike Day' via Programming <[email protected]> wrote:
>>
>> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>> To: [email protected]
>> Date: Sunday, September 4, 2016, 4:30 AM
>>
>> This version of
>> "lis" is a bit more J-like, especially in using
>> dyadic I.
>> instead of the diy binary search,
>> at the expense of a slightly more
>> complicated set-up for the m and mx arrays.
>>
>> lis =: 3 : 0
>> n =. #x =. y
>> if. 2>#x do. x return. end.
>> NB. special case empty or singleton array
>> if. (-:/:~)x do. ~.x return. end. NB. special
>> case sorted arrays
>> if. (-:\:~)x do. {.x
>> return. end.
>> p =. n#0
>> NB. seed m with trailing _1 so that final L (as
>> in wiki algorithm) can
>> be found
>> m =. n 0 } _1#~>:n
>> NB. set up sorted mx, with just the first
>> element of x, so that I. works
>> mx =.
>> ({.x) 1 } (<:<./x), n#>:>./x
>> for_i. i.n do.
>> xi =.
>> i{x
>> lo =. mx I. xi
>> p =. (m{~<:lo) i } p
>> NB. better than appending to short p for
>> larger x
>> m
>> =. i lo } m
>> mx =.
>> xi lo } mx
>> end.
>> |.
>> x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
>> )
>>
>> Mike
>>
>>
>> On 02/09/2016 20:45, 'Mike
>> Day' via Programming wrote:
>>> Well,
>> assuming for now that it does work, here's an attempt
>> at a J
>>> version of
>> the pseudo-code listed at
>>> https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>>
>>>
>>>
>>> lis =: 3 : 0 NB. longest
>> increasing subsequence
>>> m
>> =. 0#~>:n =.
>> #x =. y
>>> L
>> =. #p =. ''
>>> mx =. m{x NB. added this vector
>> for better look-up of x{~mid{m
>>> for_i.
>> i.n do.
>>> 'lo hi' =.
>> 1, L
>>> xi =. i{x
>>> while. lo <: hi do.
>>> mid =. >.@-: lo + hi
>> NB. if. xi > x{~ mid{m do. NB. next
>> line a bit better
>> if. xi > mid{mx do.
>> lo =. >: mid
>> else.
>>> hi =.
>> <: mid
>>> end.
>>> end.
>>> p
>> =. p, m{~<:lo
>>> m
>> =. i lo } m
>>> mx
>> =. xi lo } mx NB. update my additional array
>>> L =. L >. lo
>>> NB. smoutput i; (x{.~ >:i);
>> L{.m NB. diagnostic
>> end.
>>> |. x{~(p{~])^:(i.L) L{m
>>> )
>>>
>>> It's reasonably fast on ?10000#5000 -
>> but possibly wrong!It does
>>> fail on an
>> empty array.
>> Mike
>>>
>>>
>>>> On 02/09/2016 17:30, Raul Miller wrote:
>>>> It seems to me that the
>> "efficient algorithm" documented on the
>>>> wikipedia page would have an analogous
>> flaw. It is performing binary
>> searches on unsorted lists. That said, it does perform
>> correctly for
>>>> this example.
>>>>
>>>> Thanks,
>>>
>>>
>>> ---
>>> 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
>>
>>
>> ---
>> 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
