What amazes me most is the influence (of your Moral: Always append to the end
of arrays) on the performance.
ts' d 1 _1 2 _2 {~ 10000 ?.@# 4'
0.0032329 528576
ts' d 1 _1 2 _2 {~ 100000 ?.@# 4'
0.0313838 4198080
ts' s 1 _1 2 _2 {~ 10000 ?.@# 4'
0.0178007 855744
ts' s 1 _1 2 _2 {~ 100000 ?.@# 4'
1.8969506 6819520
Made your 'Moral into a '' Memo to self'.
The specs were (as specs tend to be) not complete, only non-zeroes should be
considered.
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: Programming <[email protected]>
> Namens Louis de Forcrand
> Verzonden: zaterdag 7 december 2019 13:41
> Aan: [email protected]
> Onderwerp: Re: [Jprogramming] Removing annihilating pairs
>
> First some bad news:
>
> s=: ,`(}.@])@.(= -@{:)/
> s 1 _1 0
> 1 _1 0
> s=: ,`(}.@])@.(= -@{.)/
> s 1 _1 0
> 0
> s 0 1 _1
>
>
> So our solutions don't work if the accumulator array goes empty before the
> end. Fortunately this can be fixed (see below).
> Now some good news:
>
> s=: ,`(}.@])@.(0:`(= -@{.)@.(*@#@]))/
> s=: , `(}.@])@.(0:`(= -@{.)@.(*@#@]))/
> d=: ,~`(}:@])@.(0:`(= -@{:)@.(*@#@]))/@|.
> k=: 1 _1 2 _2 {~ 100 ?.@# 4
>
> s 1 _1 0
> 0
> s 0 1 _1
> 0
> s k
> 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 _2
> _1 _2 _1
> _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
> d k
> 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 _2
> _1 _2 _1
> _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
>
> K1=: 1 _1 2 _2 {~ 10000 ?.@# 4
> K2=: 1 _1 2 _2 {~ 100000 ?.@# 4
> timespacex 'd K1'
> 0.006343 233024
> timespacex 'd K2'
> 0.055919 1.83866e6
>
> Linear as it should be.
> Moral: Always append to the end of arrays.
> Or: We aren't using linked lists!
>
> Cheers,
> Louis
>
> ----Original Message----
> From : [email protected]
> Date : 07/12/2019 - 12:33 (CEST)
> To : [email protected]
> Subject : Re: [Jprogramming] Removing annihilating pairs
>
> Forcrand's solution is more or less the version I came up with, unfortunately,
> it's far from linear (what is not compensated by its elegance).
> foo=: ,`(}.@])@.(0=(+{.))/
> ts'foo 1 _1 2 _2{~10000?.@#4'
> 0.0166915 854720
> ts'foo 1 _1 2 _2{~100000?.@#4'
> 1.9109807 6818496
>
> Miller's solution is better in that respect (and much faster)
> ts'an2 1 _1 2 _2{~10000?.@#4'
> 0.0024111 722816
> ts'an2 1 _1 2 _2{~100000?.@#4'
> 0.0281419 6293376
>
> ddup from Rich also seems to be linear but is a factor 10 slower than an2
> ts'ddup 1 _1 2 _2{~10000?.@#4'
> 0.0219618 395264
> ts'ddup 1 _1 2 _2{~100000?.@#4'
> 0.2124874 3147776
>
> Jasmin's solution is far too slow
> ts'(delitemG~ 2, 0 i.~ 2&(+/\))(^:_) 1 _1 2 _2{~10000?.@#4'
> 1.2363434 1585408
>
> Thanks for all the contributions
>
>
> R.E. Boss
>
>
> > -----Oorspronkelijk bericht-----
> > Van: Programming <[email protected]>
> > Namens Louis de Forcrand
> > Verzonden: zaterdag 7 december 2019 00:26
> > Aan: [email protected]
> > Onderwerp: Re: [Jprogramming] Removing annihilating pairs
> >
> > Not particularly J-ish, but (array-shuffling aside) linear solution:
> >
> > s=: ,`(1}.])@.(= -@{.)/
> > s 1 _1 2 _2{~100?.@#4
> > 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2
> > _2 _2 _1 _2 _1
> > _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
> >
> > Since the reduced form of the input list is unique, we are free to
> > perform reductions in any order we please; in particular, we can start
> > simplifying from the back, which is what s does.
> > Might do strange stuff on an empty input list.
> >
> > Cheers,
> > Louis
> >
> > ----Original Message----
> > From : [email protected]
> > Date : 06/12/2019 - 23:51 (CEST)
> > To : [email protected]
> > Subject : Re: [Jprogramming] Removing annihilating pairs
> >
> > If the answer to Jimmy's question is no, then the uniqueness of the
> > resulting array has to do (surprisingly) with free groups
> > (https://en.wikipedia.org/wiki/Free_group).
> > Indeed we can view a vector of numbers as a word over the alphabet
> > [0,∞) of positive real numbers (where negative numbers / zero are
> > inverses of letters in our alphabet). The fact that all maximal
> > reductions (reductions which contain no adjacent inverses) of a given
> > word are equal means exactly that our reduced list is unique.
> > For a proof see:
> > https://math.stackexchange.com/a/2425147
> >
> > I'll look into this problem, it's interesting!
> > Cheers,
> > Louis
> >
> > ----Original Message----
> > From : [email protected]
> > Date : 06/12/2019 - 23:36 (CEST)
> > To : [email protected]
> > Subject : Re: [Jprogramming] Removing annihilating pairs
> >
> > Hi,
> >
> > is the expected output of transforming 1 3 _3 3 5 to be 1 3 5 or 1 5 ?
> >
> > On Fri, Dec 6, 2019 at 7:15 AM R.E. Boss <[email protected]> wrote:
> >
> > > Given an array with zero or more annihilating pairs, i.e., two
> > > subsequent numbers which add up to zero, the question is to clean up
> > > the array by deleting all annihilating pairs such that no such pairs are
> > > left.
> > > I do have a solution that is both elegant and efficient (I believe),
> > > but I am curious about other thoughts.
> > >
> > > foo 2 1 1 _1 2 _2 _1
> > > 2
> > >
> > > foo 1 _1 2 _2{~100?.@#4 NB. Notice (?.)
> > > 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2
> > > _2
> > > _2
> > > _2 _1 _2 _1 _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
> > >
> > >
> > > R.E. Boss
> > > --------------------------------------------------------------------
> > > --
> > > 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
