Any improvement in the implementation for e. would likely benefit the whole i. family, as there already is a single implementation for that family.
The complication in exploiting a sorted target array (the left argument of i., the right argument of e., etc.) is knowing when to use which algorithm. As the benchmarks in a previous msg shows, for some arguments x i. y is (O #x)+(O #y) . If x is sorted, then it can be O (#y)*2^.#x if you use I. (binary search). Between these two orders there is a crossover point, and it is not trivial to know when to switch. ----- Original Message ----- From: Henry Rich <[email protected]> Date: Wednesday, May 20, 2009 18:51 Subject: Re: [Jprogramming] Membership using interval index To: Programming forum <[email protected]> > It would be reasonable to use fit to specify test-for-ordered: > > e.!.0 1 > > would say, 'exact, y is probably sorted' > > You would need a way to indicate tolerant comparison. Maybe > > e.!.__ 1 > > would say 'tolerant, default tolerance, y is probably sorted'. > > Better: any negative tolerance could call for default tolerance. > > > You would want something the whole i. family could benefit from. > > Henry Rich > > Roger Hui wrote: > > e signals error if the left argument has an > > item larger than the largest item in the right: > > > > 1e9 2e9 e P > > |index error: e > > | 1000000000 2000000000 e P > > > > I wonder if the interpreter should look for > > sorted y in x e. y as a special case. > > > > > > > > ----- Original Message ----- > > From: John Randall <[email protected]> > > Date: Wednesday, May 20, 2009 13:56 > > Subject: [Jprogramming] Membership using interval index > > To: Programming forum <[email protected]> > > > >> I have been trying to write a version of e. for sorted > arrays, using > >> I. , since it appears to offer performance benefits. My > >> attempt is > >> the verb e below: > >> > >> e=:[ = ] {~ I.~ > >> > >> time=:6!:2 > >> P=:i.&.(p:^:_1) 1e6 > >> > >> 10 time '(i.1000) e P' > >> 0.0001042 > >> 10 time '(i.1000) e. P' > >> 0.0069257 > >> > >> Is this a sensible approach, or are there better ways to do it? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
