It depends on whether the sequence will converge.
try
(1 2 3 4 5 6){~^:(5&>)^:(0) 1
(1 2 3 4 5 6){~^:(5&>)^:(1) 1
(1 2 3 4 5 6){~^:(5&>)^:(2) 1
(1 2 3 4 5 6){~^:(5&>)^:(3) 1
etc.
Ср, 07 сен 2016, jprogramming написал(а):
> This also runs out of memory:
>
> (1 2 3 4 5 6){~^:(5&>)^:(_) 1
> |out of memory
> | (1 2 3 4 5 6) {~^:(5&>)^:(_)1
>
> whereas this doesn't
> {&(1 2 3 4 5 6)^:(5&>)^:(_)1
>
>
> Wouldn't this imply the bug (if there is a bug) is not in the boxed integer?
>
> System details:
>
> Engine: j804/j64/windows
> Release: commercial/2015-12-21 16:18:48
> Library: 8.04.15
> Qt IDE: 1.4.10/5.4.2
> Platform: Win 64
> Installer: J804 install
>
>
> --------------------------------------------
> On Wed, 9/7/16, 'Jon Hough' via Programming <[email protected]> wrote:
>
> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
> To: [email protected]
> Date: Wednesday, September 7, 2016, 6:30 PM
>
> " 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 <[email protected]>
> wrote:
>
> Subject: Re: [Jprogramming] Greatest Increasing
> Subsequence
> To: [email protected]
> 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 <[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
>
> ----------------------------------------------------------------------
> 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
--
regards,
====================================================
GPG key 1024D/4434BAB3 2008-08-24
gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3
gpg --keyserver subkeys.pgp.net --armor --export 4434BAB3
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
