Re: [CODE] Priority Queues :: HowTo?

From: Karl Buchner (zerker@juno.com)
Date: 02/13/02


>    I'm trying to store a cache of rooms in some sort of linked list.
> This
> is COMPLETLY INDEPENDANT to the current 'world list' that exists.  I
> still
> wish to use that.  This cache of rooms will be a priority list of
> rooms. By
> this i mean, the most common / accessed rooms will be at the ENTRY
> POINT of
> the list - I assume this is the head of the list. 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.
of course, lets say your mud has 2000 rooms
on average, (assuming there are a lot of common rooms
on your mud) you might have to go through 50 checks,
but on a normal mud, i would say average 700 checks,
and in worst case 1000-1200 checks average each time
you use the list.

With an AVL tree, this would be reduced to a little under
11.  This is a big big speed increase.  A decimal tree
indexed by rightmost digit (what i use, though its not as
good as a AVL tree) yields the room 3 steps down on average.

Basically, unless you are making this list solely for the purpose
of seeing what the most popular room is, you should use
a tree or hash of some sort....otherwise you will be using
a whole lot of unneccesary processing power.  There is a
AVL tree system on the FTP site, I believe. If not, you can
probably find one anywhere.

^Blaize^
________________________________________________________________
GET INTERNET ACCESS FROM JUNO!
Juno offers FREE or PREMIUM Internet access for less!
Join Juno today!  For your FREE software, visit:
http://dl.www.juno.com/get/web/.

--
   +---------------------------------------------------------------+
   | 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