Perhaps we are using the same terms to mean different things. (# % >./) 0 2e9 1e_9 (# % >./) 2e9 2e9 1e_9
The way I think of it, 0 2e9 has large range because the difference between the smallest and largest elements is large compared to the length of the list, and 2e9 2e9 has small range because the difference between the smallest and largest elements is small. Yet your discriminant gives the same value for each. ----- Original Message ----- From: Marshall Lochbaum <[email protected]> Date: Monday, September 6, 2010 19:42 Subject: Re: [Jprogramming] Mask from list of indices with multiplicity To: 'Programming forum' <[email protected]> > Did you read my examination of > #/.`(~...@])`(0 $~ >:@(>./)@])}~ (small-range) > Versus > [: <:@(#/.~) i.@>:@(>./) , ] (large-range) > ? > Basically what I got was about the same thing you have for nub: > I used (# % >./), which is just about instantaneous, as a > discriminator and got that you should use small-range when it is > less than 1 and large-range when it is more than 1. > The speed increase is not gigantic here, and so choosing to use > or not to use the two cases is probably not that important. > > I can substantiate my result on Boolean arrays, which is weird. > It is pretty consistently as represented, averaging over 100 trials. > I am using 64-bit windows with a dual-core processor. Would any > part of that make the difference? > > Marshall > > > > -----Original Message----- > From: [email protected] [mailto:programming- > [email protected]] On Behalf Of Roger Hui > Sent: Monday, September 06, 2010 10:09 PM > To: Programming forum > Subject: Re: [Jprogramming] Mask from list of indices with > multiplicity > Candidates for special code are legion. One often has to > exercise judgment, sometimes arbitrary judgment, in whether some > particular special code is worth it. In this particular > case > > - The general expression #/.~ already has special code and is > already pretty fast. > - It is not acceptable to slow down the general case too much in > order to detect a special case, in this case to detect that the > result is going to be boolean. > > I can not reproduce the timings posted in one of your earlier msgs: > > > On the Boolean case, which I would consider the most > important, ([: > > <:@(#/.~) i.@>:@(>./) , ]) is not optimal: > > > > a=.0.1> 100000 ?...@$ 0 > > ia=.I. a > > 6!:2 '([: <:@(#/.~) i.@>:@(>./) , ]) ia' > > 0.00682521 > > 6!:2 '(e.~ i.@>:@(>./)) ia' > > 0.002004 > > 6!:2 '1 ia} (0 $~ >:@(>./)) ia' > > 0.000679754 > > What I got instead is: > > a=.0.1> 100000 ?...@$ 0 > ia=.I. a > 10 timer '([: <:@(#/.~) i.@>:@(>./) , ]) ia' > 0.00639606 > 10 timer '(e.~ i.@>:@(>./)) ia' > 0.00181928 > 10 timer '1 ia} (0 $~ >:@(>./)) ia' > 0.00160842 > > The last two times are what I'd expect, approximately equal, > because the way e. on such integers is implemented is basically > the "amend" method. > > Allow me to pose a interesting problem in this regard. > Several important functions in J (sort, i.) have fast > implementations if the argument are "small range integers". > > x=: 1e6 ?...@$ > 2e9 NB. large range > 10 timer 'i.~x' > 0.106972 > 10 timer '/:~x' > 0.0685986 > > y=: 1e9 + 1e6 ?...@$ 1e5 NB. small range > 10 timer 'i.~y' > 0.0197962 > 10 timer '/:~y' > 0.0209372 > > It is therefore important to be able to detect inexpensively (in > C) when something is small range. > So that is the interesting problem. (It is not a hard problem.) > > For a related puzzle, see: > http://www.jsoftware.com/jwiki/Essays/Index%20in%20Nub > > > > ----- Original Message ----- > From: Marshall Lochbaum <[email protected]> > Date: Monday, September 6, 2010 9:55 > Subject: Re: [Jprogramming] Mask from list of indices with > multiplicityTo: 'Programming forum' <[email protected]> > > > The tolerance thing is a problem... you might be able to solve > it with > > a weird construct like I.!.(tol)^:_1!.(universe) y. > > I think this would be the same as > > > > (universe) (3 :0)"1 y > > ($:~ i.@>:@(>./)) y > > : > > (universe) <:@(#/.!.(tol))@, y > > ) > > > > Where universe and tol are optional. As for the domain problem > with > > I.^:_1, I. has the same problem in that it only works on > numerics, so > > it is properly reflective of the inverse, and > > I.^:_1 I. is always the identity minus trailing zeros (which > can be > > added back with ($ $!.0 I.^:_...@i.). > > > > I agree that #/.~ is fast, but for arrays that were Boolean > before I. > > (ie. now return 1 for (-:~.)) the amend method is about 10 > times > > faster. > > Also, > > #/.`(~...@])`(0 $~ >:@(>./)@])}~ > > Is a candidate that works the same as the original but is > faster for > > more sparse arrays. However, it only works if we assume a > numeric > > universe. That can probably be fixed--I'll get back to it later. > > > > Marshall > > > > -----Original Message----- > > From: [email protected] [mailto:programming- > > [email protected]] On Behalf Of Henry Rich > > Sent: Monday, September 06, 2010 11:35 AM > > To: Programming forum > > Subject: Re: [Jprogramming] Mask from list of indices with > > multiplicity Allowing !. to change the universe is an > interesting > > idea, but wouldn't !. be needed in its usual role of > tolerance, since > > there are implied comparisons in the operation? > > > > > > Also, your Ii works only on numeric operands, while > > > > universe <:@(#/.~)@, y > > > > works on all types (and shapes). > > > > > > Since the key part, #/.~ , is already fast, > I think that nothing > > more is really needed. This is a matter of taste. > > > > Henry Rich > > > > > > > > > > Henry Rich > > > > On 9/6/2010 10:06 AM, Marshall Lochbaum wrote: > > > The only way I. I.^:_1 changes x is that it sorts it, and > > I.^:_1 I. only cuts out the trailing 0s: > > > Ii=. ([:<:@(#/.~) i.@>:@(>./) , ]) > > > (; (;Ii)@I.) 1...@$2 > > > ┌───────────────────┬───────────┬─────────────────┐ > > > │1 1 1 0 0 1 1 0 1 0│0 1 2 5 6 8│1 1 1 0 0 1 1 0 1│ > > >└───────────────────┴───────────┴─────────────────┘ > > > (; (;I.)@Ii) 6...@$10 > > > ┌───────────┬─────────────────┬───────────┐ > > > │0 0 8 6 6 3│2 0 0 1 0 0 2 0 1│0 0 3 6 6 8│ > > >└───────────┴─────────────────┴───────────┘ > > > > > > I think each of these cases is acceptable, especially if you > > allow !. to change the universe (this removes the I.^:_1 I. > problem).> > > > > Marshall > > > > > > > > > -----Original Message----- > > > From: [email protected] > > > [mailto:[email protected]] On Behalf Of > Roger Hui > > > Sent: Monday, September 06, 2010 2:26 AM > > > To: Programming forum > > > Subject: Re: [Jprogramming] Mask from list of indices with > > > multiplicity > > > > > > I.^:_1 seems too far from what<:#/.~universe,x does. > > > Another way to say that is that I. I.^:_1 x can bear scant > > resemblance to x . > > > > > > > > > > > > ----- Original Message ----- > > > From: Zsbán Ambrus<[email protected]> > > > Date: Sunday, September 5, 2010 14:21 > > > Subject: Re: [Jprogramming] Mask from list of indices with > > > multiplicity > > > To: Programming forum<[email protected]> > > > > > >> On Sun, Sep 5, 2010 at 10:57 PM, Roger > > Hui<[email protected]> wrote: > > >>> <: #/.~ (i.7) ,x > > >> > > >> Nice solution. > > >> > > >>> ----- Original Message ----- > > >>> From: Zsbán Ambrus<[email protected]> > > >>>> Would it make > > >>>> sense if I.^:_1 did this? > > >> > > >> ^^^ What's your opinion on this? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
