[Jprogramming] Membership using interval index

[Roger Hui]

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 <HenryHRich at nc.rr.com>
Date: Wednesday, May 20, 2009 18:51
Subject: Re: [Jprogramming] Membership using interval index
To: Programming forum <programming at jsoftware.com>

> 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 <randall at andromeda.rutgers.edu>
> > Date: Wednesday, May 20, 2009 13:56
> > Subject: [Jprogramming] Membership using interval index
> > To: Programming forum <programming at jsoftware.com>
> > 
> >> 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?