One thing I keep meaning to do, when i see stuff like this, is verify
that the various versions are giving the same results for the same
test arguments. (In the past, I have seen timing examples where we
were comparing timings on code that gave different results.)
I haven't done that here, yet, but I can recommend an approach. Something like:
assert 1=#~.(lisI; lisJ; lisM; lisL; lisEH) a
Thanks,
--
Raul
On Fri, Sep 9, 2016 at 9:39 AM, Erling Hellenäs
<erl...@erlinghellenas.se> wrote:
> Hi all !
>
> I made a new version. The code is below. This is the present scoreboard:
>
> a=: 25 ? 25
>
> timespacex 'lisI a'
>
> 0.000296778 3584
>
> timespacex 'lisJ a'
>
> 0.000545234 3712
>
> timespacex 'lisM a'
>
> 0.000131711 10752
>
> timespacex 'lisL a'
>
> 0.000174047 11776
>
> timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> 0.0101456 247424
>
> timespacex 'lisEH a'
>
> 0.000304476 14208
>
>
> a=: 1000 ? 1000
>
> timespacex 'lisI a'
>
> 0.0226869 538880
>
> timespacex 'lisJ a'
>
> 0.0577798 1.13357e6
>
> timespacex 'lisM a'
>
> 0.0046749 45952
>
> timespacex 'lisL a'
>
> 0.161294 594176
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
> 0.236193 718720
>
>
> a=: 10000 ? 10000
>
> timespacex 'lisI a'
>
> 0.311934 1.69006e7
>
> timespacex 'lisJ a'
>
> 1.45356 2.31916e7
>
> timespacex 'lisM a'
>
> 0.04604 548736
>
> timespacex 'lisL a'
>
> 17.0889 1.31657e7
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
> 26.5314 1.44383e7
>
>
> It is hard to create a good tacit solution?
>
>
> Cheers,
>
> Erling
>
>
>
> 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.===========================================================================
>
>
> NB. Erling's version
>
>
> GroupOfEmptyGroupInitialState=: [: < a:"_
>
> PackElements=: <@+
>
> SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) # ]
>
> PrependLeftInGroups=: ([: < [) ,&.> ]
>
> AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]
>
> SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ [: >./
> ]) #@>)) { ]
>
> DoBetweenElementsInFold=: ] , [ AddGroupWithLeftIfNoGroups [
> PrependLeftInGroups [: SelectFirstGroupOfMaxLength
> SelectGroupsWithLeftLessThanFirstElement
>
> LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: > [:
> DoBetweenElementsInFold&.:>/ PackElements , GroupOfEmptyGroupInitialState
>
> lisEH=: LongestIncreasingSubsequence f.
>
>
> 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.
>
> timespacex 'lisEH a'
>
>
> a=: 1000 ? 1000
>
> timespacex 'lisI a'
>
> timespacex 'lisJ a'
>
> timespacex 'lisM a'
>
> timespacex 'lisL a'
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
>
> a=: 10000 ? 10000
>
> timespacex 'lisI a'
>
> timespacex 'lisJ a'
>
> timespacex 'lisM a'
>
> timespacex 'lisL a'
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
