Re: Ranking
Crouchez wrote:
Basically what I want to do is maintain a constant top 10 list that is
accessed and modified by multiple threads. The list contains objects that
have two values - a name and an access count. Think I might use this?
Collections.sort(List list, Comparator c) like Jacky said but with a
different comparator
Your choice depends on a few things:
If your list has a total of N items, finding the top k in this list is
O(k*N) using a hash table, O(k) for a sorted list, O(k*N) for an
unsorted list, and O(k*lg N) for a priority queue.
Updating the list requires O(1) for a hash table, O(N) for a sorted
list, O(1) for an unsorted list, and O(lg N) for priority queues.
If the ratio of modifications to generations is m (i.e., for every m
modifications, the list is regenerated), then the total time is O(m+k*N)
for hash table, O(N+m*k) for sorted lists, O(k*N+m) for unsorted lists,
and O((k+m)*lg N) for priority queues.
If m is 1, these formulas degenerate into O(k*N), O(N+k), O(k*N), and
O(k*lg N) respectively.
I should note that metrics for the last two imply O(1) access to a
specific element, which means that an auxiliary hash table mapping
objects to indices is needed. For unsorted lists, that means that it is
essentially a hash table. Without that unit, the times go up to O(N) for
access in both cases.
Furthermore, the time for a sorted list implies using a
slightly-modified insertion sort rather than a quick sort. Updating goes
up to an O(N lg N) in that case. I am also assuming that a custom heap
is used for the priority queue case to take advantage of the hash table.
If you want to write as little code as possible, a hash table
(implemented via HashMap and Collections.synchronizedMap()) is fastest.
In high-throughput conditions, a custom-made priority queue works best;
the sorted list is a good middle-of-the-road, assuming you use a
modified insertion sort rather than the default quicksort.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth