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 <programm...@jsoftware.com> wrote:

 Subject: Re: [Jprogramming] Greatest Increasing Subsequence
 To: programm...@jsoftware.com
 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

Reply via email to