On Mon, 5 Jan 1998, Chris Jacobson wrote:
> The time savings could really add up eventually. With 350 total
> commands, thats about 18.75 strcmp()s avg to parse out any command,
> instead of the otherwise 175 strcmps. Thats nearly 9 times faster to
> parse out commands. Take an average of 4 commands parsed per pulse bineg
> sent on a decent mud, thats a total of 625 strcmp()s saved... for 62500
> strcmp()s per second
With a hash table, the hash function being the first letter of the
function we have 26 hash buckets (ignoring punctuation): assuming that the
commands are somewhat evenly divided and that we find the command halfway,
that's (350/26)/2 = 6 compares. Since they aren't, this will vary a bit.
The social table should be separated from the command table anyway: (they
have no code attached, they can be easily made online editable and it
never made sense to me that "k" was "kiss", not "kill") that would reduce
the search for commands even further.
Oh, and with the binary tree you won't have the possibility to specify
that one command should come before another. Also, a hashtable is quite
simpler to implement.
In all of the 170k lines of code of AR, trees are used only for expression
parsing (math in mobprogs and a command which allows complicated command
parsing like: pdb find email=*.dk and ( level>20 or class=mage))
Everything else is hash tables and linked lists.
In this case, the hash function has a low range since partial matching
must be done: if you only have to full names fully, you can achieve much
better spread of the hash function, if you pick a hash function like
perl's, and can typically increase peformance linearly by by increasing
the size of the hash table.
=============================================================================
Erwin Andreasen Herlev, Denmark <erwin@pip.dknet.dk> UNIX System Programmer
<URL:http://www.abandoned.org/drylock/> <*> (not speaking for) DDE
=============================================================================
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST