On Mon, Apr 25, 2011 at 4:48 PM, Dmitriy Lyubimov <[email protected]> wrote:
> On Mon, Apr 25, 2011 at 4:26 PM, Ted Dunning <[email protected]> > wrote: > > > > BUT > > > > As Jake says, this is all really just O(n) and is so fast that none of > this > > matters to the user. > > > > Unless you have 1ms alotted for this... in which case you really have > no choice but to stop early and and hope to get really best, perhaps > using some clever heuristical structures that may help to improve > results such as inverted indices... > Yes, in the real search case, you hopefully have a static prior which allows your list to be "semi-sorted" so that you can early-terminate, otherwise eve linear isn't really scalable for the live query use case (even with parallelism thrown into the mix). -jake
