On Tue, 12 Feb 2002, Justin Adler wrote:
> This way, every time i traverse this cache list, I do not have to
> trickle deep down into the cache becuase in theory, the most accessed
> rooms are near the entry point.
While there are various other algorithmic solutions than the one I am
about to propose, some of them are more complex than what you really need.
In the spirit of K.I.S.S., here's one simple answer:
You don't want O(N) worst-case performance for the room cache if the idea
is to locate rooms of various frequencies without untoward latency.
Using a priority queue in this case is a bad idea. What you're really
looking for is a frequency table, of sorts. An efficient, simple approach
is to create a hash table indexed by a frequency rating. Collisions
between elements with equal frequency can be handled by hash chaining
(i.e., the hash table is an array of pointers to the head of linked
lists). This looks like:
struct room_hash_data
{
room_rnum room;
struct room_hash_data *next;
};
/* SZ_ROOM_SLICE = size per slice; M_ROOM_SLICES = table size */
#define SZ_ROOM_SLICE 10
#define M_ROOM_SLICES 100
#define M_ROOM_FREQ (M_ROOM_SLICES * SZ_ROOM_SLICE)
#define FREQUENCY_KEY(f) (MAX(0, (M_ROOM_FREQ - (f))) / M_ROOM_SLICES)
struct room_hash_data *roomFrequencyTable[M_ROOM_SLICES+1];
The table is indexed by a hash key which is generated by a hash function
(actually, here, a macro; FREQUENCY_KEY). Each entry in the hash table is
properly called a bin or bucket and represents a range of values. The
zeroeth bin is for the most frequent cases, and the last is for the least
frequent cases. The insertion algorithm looks like:
if room not in frequency table then
store 0 as the room's frequency
store M_ROOM_SLICES as key
insert a new room_hash_data entry into roomFrequencyTable[key]
return
end if
store FREQUENCY_KEY(room's frequency) as old key
increment room's frequency
store FREQUENCY_KEY(room's frequency) as new key
if old key is new key then return # the bin hasn't changed.
remove the room's room_hash_data entry from roomFrequencyTable[old key]
insert the room's room_hash_data entry into roomFrequencyTable[new key]
Note that this is really simple code, being little more than ordinary
singly linked list management. What makes the hash table approach better
than a queue is that the list lengths are minimized and we can jump around
very easily. So even though our code has little complexity, we get good
performance. (Especially if we pick the right number and size of room
slices, so that we have a good range [rather than lots of data in the same
bin and none in others].)
The hash table also lends itself well to drawing a histogram, which would
be quite useful to get a descriptive overview of access frequencies.
-dak
--
+---------------------------------------------------------------+
| FAQ: http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
| Archives: http://post.queensu.ca/listserv/wwwarch/circle.html |
| Newbie List: http://groups.yahoo.com/group/circle-newbies/ |
+---------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 06/25/03 PDT