How about assuming unordered items of the left argument but, as scanning for the match, remembering how far into the right argument the scan goes into the right argument where the items are ordered? Then, for the rest of the items in the left argument, use the ordered logic up to that point and if no match is found, switch to the unordered logic for the rest of the right argument. The end of the ordered part could be extended whenever the search switched to the unordered part.
On Thu, May 21, 2009 at 6:05 AM, Raul Miller <[email protected]> wrote: > On Wed, May 20, 2009 at 11:34 PM, Roger Hui <[email protected]> wrote: > > 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. > > If we go by "anything less than a factor of 2 > is not worth bothering with", does this become > trivial? > > Thanks, > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
