mahout-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dmitriy Lyubimov <dlie...@gmail.com>
Subject Re: Top items in a vector
Date Mon, 25 Apr 2011 23:48:13 GMT
On Mon, Apr 25, 2011 at 4:26 PM, Ted Dunning <ted.dunning@gmail.com> 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.

Mime
View raw message