[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.

Chris Gray cg at ami-cg.GraySage.Edmonton.AB.CA
Mon Feb 8 20:53:19 New Zealand Daylight Time 1999


[Ben Greear:]

 >I'd do that, but I want the user to be able to abbreviate any command.
 >I couldn't figure out a way to hash and still get that feature.

I recommend against allowing any unambiguous abbreviation for any
command. The problem here is that when you add a command, you can break
what was previously an unambiguous abbreviation. Now you either have to
make a special-case exception, or you have just removed an abbreviation
that users have gotten used to. I think its better to select one or
two abbreviations for each command (if any are really needed), and
hardcode them along with the commands. That way you can have n,s,e,w,u,p
mean what people expect them to mean without special casing them.

However if you insist on minimal unambiguous abbreviations, and don't
want a linear search, how about this:

At startup time, scan your table of commands, and build some auxilliary
data structures. Have the code determine the minimum unambiguous form
of all commands. Enter all of those into a hash table (could even try
a mostly minimal one). Include in your data structures the full name
of the commands. Then, lookup consists of looking up longer and longer
portions of the input command until you find a match, or you have tried
the full command. Search is O(length of input command) rather than
O(number of commands).

--
Don't design inefficiency in - it'll happen in the implementation. - me

Chris Gray     cg at ami-cg.GraySage.Edmonton.AB.CA
               http://www.GraySage.Edmonton.AB.CA/cg/




More information about the MUD-Dev mailing list