On Fri, 26 Sep 2003 15:37:50 +0200 Xavier Nodet <[EMAIL PROTECTED]> wrote:
XN> As I like algorithms, and I don't like bad performances, I started to
XN> look at the performances of the address book searches.
Thanks a lot! I keep thinking about it myself but didn't even have time to
profile it so far...
XN> All of those case share the same properties: we repeatedly look for the
XN> same fixed pattern in a huge set of strings. The complications come from
XN> the fact that we (sometimes) allow wildcards in the pattern, and we want
XN> to be able to do case-insensitive searches.
Actually by far the most often use of wildcards is to allow for "foo*"
(90%) and "*foo*" (5%), so I agree that we could drop them [in other cases].
XN> Currently, the simplest case (no wildcard, case-sensitive) is handled
XN> using string.Matches("*pattern*"). This is a pity in the case where the
XN> pattern does not have wildcards inside, as some more efficient
XN> algorithms could be used.
Right...
XN> But the most time-consuming task seems to be to convert *all* the
XN> searched strings to lower case so that the search is actually
XN> case-insensitive. Would it be possible to cache the lower-case version
XN> of the strings used in the address-book?
Yes, AdbEntry could do this. Or, rather, Matches() could do it (it would
just cache the values on the first call). This seems like a pretty simple
thing to do, so if this is really the bottleneck, we're saved!
XN> With respect to the search algorithm itself, I implemented a very simple
XN> one given (among tons of others) in
XN>
XN> http://www-igm.univ-mlv.fr/~lecroq/string/node19.html#SECTION00190
XN>
XN> The code pretty simple and quite effective. As for regexps, it requires
XN> that the pattern is 'compiled' before starting any search.
This shouldn't be a problem... as search takes literally seconds the
compilation time must be trivial.
I do wonder about something else: surely there are some algorithms which
could benefit from compiling the search space. For ADB it would make sense
to compile it on (or soon after) startup if it were not *too* time
consuming (although even then we could do it in a separate thread...) and
if it is possibly to efficiently update the compiled object when just one
string is changed/added/deleted. Do you know about anything like this?
XN> Of course, it does not handle wildcards, so either we remove this
XN> feature or we switch depending on the fact that the given pattern has a
XN> wildcard or not. Note that address auto-collection never uses wildcard,
XN> so would always benefit from the new algorithm.
For me the worst delay is in the composer because it is interactive: you
press Tab and wait...
Thanks again for teking time to look at this!
VZ
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
Mahogany-Developers mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/mahogany-developers
