<!-- MHonArc v2.4.4 -->
<!--X-Subject: [MUD-Dev] Re: Question on c++ switch optimization, and parsers in general. -->
<!--X-From-R13: "F. Oyrknaqre Bbcvry" <cbcvryNfahtuneobe.pbz> -->
<!--X-Date: Mon, 8 Feb 1999 20:41:52 -0800 -->
<!--X-Message-Id: 199902090441.UAA04714#cashew,snugharbor.com.snugharbor.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 199902090353.UAA00877@ami-cg.GraySage.Edmonton.AB.CA -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, [MUD-Dev] Re: Question on c++ switch optimization, and parsers</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:popiel#snugharbor,com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00369.html">Previous</a>
| <a href="msg00371.html">Next</a>
]
Thread:
[ <a href="msg00368.html">Previous</a>
| <a href="msg00355.html">Next</a>
]
Index:
[ <A HREF="author.html#00370">Author</A>
| <A HREF="#00370">Date</A>
| <A HREF="thread.html#00370">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: [MUD-Dev] Re: Question on c++ switch optimization, and parsers in general. </LI>
<LI><em>From</em>: "T. Alexander Popiel" <<A HREF="mailto:popiel#snugharbor,com">popiel#snugharbor,com</A>></LI>
<LI><em>Date</em>: Mon, 08 Feb 1999 20:41:29 -0800</LI>
<LI><em>cc</em>: <A HREF="mailto:popiel#snugharbor,com">popiel#snugharbor,com</A></LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
In message: <<A HREF="msg00368.html">199902090353.UAA00877#ami-cg,GraySage.Edmonton.AB.CA</A>>
Chris Gray <cg#ami-cg,GraySage.Edmonton.AB.CA> writes:
>
>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).
Better yet, just store your commands in a compressed radix tree.
(Treat the command string as a bit string, going left or right
based on 0 or 1 in a given position; when building the tree,
omit levels where there is no branch. Internal tree nodes tell
which bit to test, commands are in leaves. You can optimize
by testing more than 1 bit at a time and having a larger branching
factor.) Just walk the tree until you reach the end of input
or hit a leaf. If you run out of input before reaching a leaf,
then the input was ambiguous. If you reach a leaf, check the
input against the command you found, to see if they typed garbage
which just looked somewhat like a command (weird things can happen
with the tree compression). If you're using a higher branching
factor and walk off the tree, then they entered a bogus command.
Search is at most O(length of input command) (and is frequently
less), typos tend to fail early instead of testing every possible
prefix, and you don't have to reprobe a hash table or figure out
minimum non-ambiguity. The tree-insert code is a bit of a pain,
though.
- Alex
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00368" HREF="msg00368.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></STRONG>
<UL><LI><EM>From:</EM> Chris Gray <cg#ami-cg,GraySage.Edmonton.AB.CA></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00369.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00371.html">[MUD-Dev] code profiling</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00368.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00355.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers i</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00370"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00370"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><strong><A NAME="00366" HREF="msg00366.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Tue 09 Feb 1999, 03:31 GMT
<UL>
<LI><strong><A NAME="00369" HREF="msg00369.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></strong>,
Adam J. Thornton <a href="mailto:adam#phoenix,Princeton.EDU">adam#phoenix,Princeton.EDU</a>, Tue 09 Feb 1999, 04:34 GMT
<UL>
<LI><strong><A NAME="00372" HREF="msg00372.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></strong>,
Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Tue 09 Feb 1999, 06:01 GMT
</LI>
</UL>
</LI>
</UL>
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00368" HREF="msg00368.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Tue 09 Feb 1999, 03:54 GMT
<UL>
<LI><strong><A NAME="00370" HREF="msg00370.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.</A></strong>,
T. Alexander Popiel <a href="mailto:popiel#snugharbor,com">popiel#snugharbor,com</a>, Tue 09 Feb 1999, 04:41 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="00355" HREF="msg00355.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers i</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Mon 08 Feb 1999, 06:11 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00367" HREF="msg00367.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers i</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Tue 09 Feb 1999, 03:45 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00353" HREF="msg00353.html">[MUD-Dev] Question on c++ switch optimization, and parsers in general.</A></strong>,
Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Mon 08 Feb 1999, 05:32 GMT
<UL>
<LI><strong><A NAME="00354" HREF="msg00354.html">[MUD-Dev] Re: Question on c++ switch optimization, and parsers i</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Mon 08 Feb 1999, 05:56 GMT
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>