" It appears that <n is being interpreted
as <_ regardless of n."
I'm not sure this is the case, for any left hand verb.
]^:(<4) 4
works fine.
--------------------------------------------
On Wed, 9/7/16, Henry Rich <henryhr...@gmail.com> wrote:
Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: programm...@jsoftware.com
Date: Wednesday, September 7, 2016, 6:05 PM
I noticed this the other
day. It appears that <n is being interpreted
as <_ regardless of n. I'll look into
it.
Henry Rich
On 9/6/2016 11:53 PM,
Xiao-Yong Jin wrote:
> 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 <programm...@jsoftware.com>
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 mike_liz....@tiscali.co.uk.
>> Sent from my iPad
>>
>>> On 5 Sep
2016, at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
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 <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
>>
----------------------------------------------------------------------
>> 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
