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... i remember scanning a 50-million memory mapped inverted index some years ago and i remember i couldn't get more than 500k results looked thru in that scan in less than 40 ms... Which was kind of more than i had... with this very heap-accumulating technique (and i did not even use PriorityQueue cause it really did not have -- or i haven't found -- the operation of replacing the heap+sift thru instead of removing+inserting... which did manage to make a small dent in efficiency.
