Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction Footnote from the Author

Author Footnote

Dear Dr. Dobb's,

Dr. Dobb's reader Benjamin Lunt has kindly done some performance comparisons using my algorithm and a recursive algorithm from wildcard text matching code used by a colleague of his. He found the recursive code slightly faster than the version of my code that appears in Dr. Dobb's, in some circumstances. In other circumstances, my code was faster. But that got me thinking about performance.

I realized that my algorithm could benefit from skipping an extra assignment of the w variable, which occurred any time after a wildcard ("*") character had been encountered. Needless assignments can force needless cache memory updates, possibly leading to serious slowdowns on modern CPUs. Then I thought of a way to correct this. The new performance-tuned code is below. It retains the fixes for repeating character patterns and for case sensitivity that I previously provided. I've tested the new version in every way I could think of, and I've sent it out to Ben and some other interested Dr. Dobb's readers who've also shared with me various thoughts about the algorithm. Ben has very helpfully tested the performance, as he did with the original version; his remarks appear after the new code below.

In answer to Ben's comment about nonmatching situations requiring more cycles than matching situations, let me point out the following. Because this is wildcard-based matching, you may have to do a lot of checking to know for certain that you don't have a match. Perhaps there's no way around that sort of performance limitation in wildcard text matching algorithms. At least I haven't thought of a faster approach, and I have yet to see evidence that one exists -- but then again you never know.

Regards,
Kirk

//This function compares text strings, one of which can have wildcards ('*').
//
BOOL GeneralTextCompare(
        char * pTameText,             // A string without wildcards
        char * pWildText,             // A (potentially) corresponding string with wildcards
        BOOL bCaseSensitive = FALSE,  // By default, match on 'X' vs 'x'
        char cAltTerminator = '\0'    // For function names, for example, you can stop at the first '('
)
{
        BOOL bMatch = TRUE;
        char * pAfterLastWild = NULL; // The location after the last '*', if we've encountered one
        char * pAfterLastTame = NULL; // The location in the tame string, from which we started after last wildcard
        char t, w;

        // Walk the text strings one character at a time.
        while (1)
        {
                t = *pTameText;
                w = *pWildText;

                // How do you match a unique text string?
                if (!t || t == cAltTerminator)
                {
                        // Easy: unique up on it!
                        if (!w || w == cAltTerminator)
                        {
                                break;                                   // "x" matches "x"
                        }
                        else if (w == '*')
                        {
                                pWildText++;
                                continue;                           // "x*" matches "x" or "xy"
                        }
                        else if (pAfterLastTame)
                        {
                                if (!(*pAfterLastTame) || *pAfterLastTame == cAltTerminator)
                                {
                                        bMatch = FALSE;
                                        break;
                                }
                                pTameText = pAfterLastTame++;
                                pWildText = pAfterLastWild;
                                continue;
                        }

                        bMatch = FALSE;
                        break;                                           // "x" doesn't match "xy"
                }
                else
                {
                        if (!bCaseSensitive)
                        {
                                // Lowercase the characters to be compared.
                                if (t >= 'A' && t <= 'Z')
                                {
                                        t += ('a' - 'A');
                                }

                                if (w >= 'A' && w <= 'Z')
                                {
                                        w += ('a' - 'A');
                                }
                        }

                        // How do you match a tame text string?
                        if (t != w)
                        {
                                // The tame way: unique up on it!
                                if (w == '*')
                                {
                                        pAfterLastWild = ++pWildText;
                                        pAfterLastTame = pTameText;
                                        w = *pWildText;

                                        if (!w || w == cAltTerminator)
                                        {
                                                break;                           // "*" matches "x"
                                        }
                                        continue;                           // "*y" matches "xy"
                                }
                                else if (pAfterLastWild)
                                {
                                        if (pAfterLastWild != pWildText)
                                        {
                                                pWildText = pAfterLastWild;
                                                w = *pWildText;
                                               
                                                if (!bCaseSensitive && w >= 'A' && w <= 'Z')
                                                {
                                                        w += ('a' - 'A');
                                                }

                                                if (t == w)
                                                {
                                                        pWildText++;
                                                }
                                        }
                                        pTameText++;
                                        continue;                           // "*sip*" matches "mississippi"
                                }
                                else
                                {
                                        bMatch = FALSE;
                                        break;                                   // "x" doesn't match "y"
                                }
                        }
                }

                pTameText++;
                pWildText++;
        }

        return bMatch;
}

From Dr. Dobb's reader Benjamin Lunt...

Hi Kirk,

Yes, much faster. At 10,000,000 iterations,

tame = "mississippi.river";
wild = "*.*";
original code: 57 seconds
new code: 2 seconds
my friends code: 46 seconds

wild = "*ip*";
47, 1, 43 respectively

wild = "m*i*.*r";
77, 3, 66 respectively

wild = "m*x*.*r";
69, 23, 66 respectively

Good job. However, if you will notice, it is extremely faster if it is a match, but quite slow (though still faster than the original) if not a match. I figured it should be the other way around. Once you find the match, you stop looking.

It is finding non matches that should be the faster code.

I didn't look too closely at your code yet, but could it be switched so that it was faster on a non match than on a match?

Anyway, I was surprised in the speed increase from the last code. I thought I did something wrong, but no, it was your code that was just much faster :-)

Thanks,
Ben

Previous Page | 1 Introduction | 2 Footnote from the Author

RELATED ARTICLES Logging In C++ : Part 2 OutSystems Updates Agile Platform SDK, .NET Controls Released for Communications Enabling Web Pages Welcome To the World of Cryptographic Voting recls 100% .NET		TOP 5 ARTICLES No Top Articles.