On Sun, 21 Apr 2002, Daniel Byer wrote:
I'm implementing tracking code to my ROM2.4b6 MUD, from scratch (not
installing someone else's). What I am going to be doing is having a
TRACK_DATA struct to keep track of the age of the tracks, the direction
tracks go to/come from, and 2 other fields, depending on what ends up
being most efficient. Anyway, my question IS about efficiency. Would it
be better to hold a TRACK_DATA struct in each CHAR_DATA, in each
EXIT_DATA (my original plan), or in each ROOM_INDEX_DATA? If I did it
in
the EXIT_DATA, there'd be an awful lot of memory usage. Would it be
best
to have each individual player store his/her own tracks?
You'll have to be more specific with your question. The term
"efficiency" means nothing. There are many different (often mutually
exclusive) types of efficiency. The two most commonly referred to
are time efficiency (how long it takes to run) and space efficiency
(how much space, or RAM in this case, it takes to run).
The first question I'd like to get out of the way is the data type
you'll be using to keep track of the tracking information. You already
stated that you will have a TRACK_DATA struct, but did not say anything
about the higher level structures. What data type will you use to hold
the
TRACK_DATA structures? Such as arrays, linked lists, hash tables, etc.
Some of the tradeoffs of several different data structures:
Arrays: If you use an array in each place you store the tracking data,
you will be limited to a constant maximum number of tracks in
each place, and will waste a LOT of room. In other words,
VERY space inefficient. (Not too bad on time efficiency though.
Searching, inserting, and deleting will take O(N) time where N is
the number of tracks stored in that location.
Hash tables: Using one big hash table might be the most space
efficient way to do it. It wouldn't waste as much space in
rooms that have never been entered. And the searching, inserting,
and deleting isn't too bad in time efficiency. Not quite as good
as an array, but still not bad.
Linked lists: Using linked lists would be the way I would do it.
It's not as space efficient as a hash table would be, but not
nearly as space inefficient as arrays. The time efficiency for
linked lists would be pretty good. O(N) for searching, O(1) for
inserting, and O(N) for deleting. You are wasting the size of
a pointer for each list and for each node in the list (4 bytes
on an intel-type machine) that you wouldn't be in an array, but
you also don't have lots of space wasted if you have no tracks.
I would do it with a linked list, and the way you stated the question
it sounded like you were planning on using either arrays or linked
lists (I can't tell which you were implying), so I am going to assume
the use of linked lists for the rest of this email. The rest of this
email doesn't necessarily hold when different data structures are used;
it would just give some notes to compare the other data structures to.
Now we can get on to the question of where to put the data:
global, char data, PC data, exit data, or room data.
Global: Best space efficiency for a linked list. But the time
efficiency
just plain sucks. O(N) where N is the number of tracks mud-wide.
Char data: Space efficiency isn't terrible. One pointer for each
character in addition to the actual data. Depending on how you
implemented the code, this could be a bad place or a terrible place
for time-efficiency. If you "track Bob", searching is O(N) where
N is the number of tracks belonging to Bob. If you just "track"
and get all the tracks in the room, you're back to O(N + M) where N
is the number of tracks mud-wide and M is the number of mobs & PCs
mud-wide, which is even worse than the global approach.
PC data: Better time efficiency than char_data, and very good space
efficiency. Time efficiency would be O(N + M) still, but M would
only be the number of PCs. A possible drawback is that this would
not
work with mobs while any of the others would (something to
consider).
Exit data: I can't see a good argument in favor of this one since
the way I understand it, tracking is a room-wide thing. You'd
just have to go through every exit in a room to get the data.
Might as well just stick it in the room_data.
Room data: Better space efficiency than exit data, worse than global.
Whether it's more or less space-efficient than in char_data
depends on whether you have more rooms or mobs. Time efficiency
is the best out of these choices. O(N) for the number of tracks in
the room for searching and deleting, and O(1) for inserting.
To sum up what turned out to be a very long email:
Efficiency isn't a "best/worst" thing. It's a trade-off. You have to
find a balance that works best for you.
I suggest linked lists in the room data. You're using one pointer
per room (not really that much when you think about it), and the
time efficiency is the best as long as my assumption about track
listing all tracks present is true (and might even be if my assumption
isn't true). Putting it in the exit_data makes no sense unless you
have to specify a specific direction to track. Putting it in char data
isn't as time efficient and could use MORE memory than in room data.
And putting it in PC data isn't as time efficient.
Now you know my opinion, and a little bit about how I chose it.
Dennis
