Re: Arrays and Linked Lists (long)

From: Anil Mahajan (amahajan@PROXICOM.COM)
Date: 04/27/00

There are a few things I forgot to mention, reading over the message.
Speed is a big issue when using lists instead of arrays.  AVL B-trees
help a lot as opposed to regular single linked lists, but there's still
a lot of recursion searching through deep trees.

You need to take this into account when re-doing your structures.  A
good way to lessen the recursive searching burden is to directly
reference data structures.

Example:  Rooms have exits.  Currently we hold index to where these are.
If i want to go east, i grab the VNUM of the room to the east, then
find the room.  To speed up this process in a tree environment, you
should remove this lookup by having a room know what room is next to it.
What you want is for room->dir_option[EAST] to return a room_data.

The same goes for many other things.  ch->in_room should be a room struct
not a reference number.  Anywhere that reference numbers are used in the
code, you should (at startup/object creation) change those numbers into
a pointer.

This does create issues with deleting rooms, but you just need to take this
minor issue into account in extract_room().  The only real danger is one
way room exits.  I don't remember if I properly handled this issue or not
(it's been a while).

I honestly haven't noticed the MUD running any slower.  I've profiled
the mud, and I've run average loop timings as part of my game loop
(calculate usec's used) and I've got plenty of time to spare, though I
haven't compared it to regular array-based circleMUd.

- Anil

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  |

This archive was generated by hypermail 2b30 : 04/10/01 PDT