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
