Thread: Better Way?

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    6

    Better Way?

    This function takes a char and compares it against a list of chars for a match. Is there a more efficient way of accomplishing this compared to this code: (see text file).

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    There most likely is a more efficient way of doing it, however it depends on a few factors:
    1. How many 'acceptableCharacters' there are in the string.
    2. How many times charMatch is called with the same 'acceptableChars' string.

    One option is for the constructor and changeAcceptableCharacterList to sort the list of chars. Then the charMatch function can do a binary search to hunt for the validatee in the string. That will be faster or slower depending on the items listed above. The bigger the numbers in the answers to 1 and 2 above, the more efficient the technique I just mentioned will be.

    If the answer 2 is large enough then building a hashed table, or even a complete table of acceptable chars will be faster as you can then do O(1) lookups.
    Last edited by iMalc; 10-03-2008 at 12:45 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Another option might be to have a look-up table, an array of bools/chars [256] where you can look up the acceptable characters directly (O(1): is_acceptable[input[0]]).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    6
    The acceptableCharacters list can range anywhere from one to all the characters on the keyboard at once.

    ~1234567890-=~!@#$%^&*()_+[]\;',./|:"<>?qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJK LZXCVBNM

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    'Range' is a vague word. It could be one char 99&#37; of the time and then all chars 1% of the time.
    You also given no hint as to how often charMatch is called on the same instance of the class.
    To give us an idea of how it is used you'd actually have to tell us what if it is used for, or post code. For example if the acceptableCharacters string is always from a hard-coded string then you could simply make that hard-coded string already sorted, saving a sort at runtime.
    It's also entirely possible that depending on your usage patterns the function you've provided is already optimal.
    Until you can provide some more information, there's nothing more we can tell you. If you don't have any idea how you use it because you aren't actually using it at all, then you're wasting our time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed