CODEWITHSUNDEEP
c++performance
user823738
user823738

Reputation: 17521

How to quickly compare string against lots of predefined strings?

I need to quickly compare requested path against predefined constants, like this:

if (path == "/admin")
    ...
else if (path == "/something-else")
    ...
else if (path == "/something-else2")
else
    ...

However, the list is very huge. The problem here is speed. I need to do it very quickly.
How would you go about it ?

Upvotes: 1

Views: 409

Answers (6)

Mike Dunlavey
Mike Dunlavey

Reputation: 40659

This is similar to Raymond's answer, but without using Boost.

Suppose your strings are, as given in advance. AA, AB, BA, BB. You can write a little program to sort the list, and then recursively print out a nested switch statement looking like this, which is a hard-coded trie:

switch(path[0]){
  break; case 'A': switch(path[1]){
    break; case 'A': switch(path[2]){
      break; case '\0':; // "AA" found
      break; default:
        // no match
    }
    break; case 'B': switch(path[2]){
      break; case '\0':; // "AB" found
      break; default:
        // no match
    }
    break; default:
      // no match
  }
  break; case 'B': switch(path[1]){
    break; case 'A': switch(path[2]){
      break; case '\0':; // "BA" found
      break; default:
        // no match
    }
    break; case 'B': switch(path[2]){
      break; case '\0':; // "BB" found
      break; default:
        // no match
    }
    break; default:
      // no match
  }
  break; default:
    // no match
}

Then copy/include that nested switch statement into the main program.

It will be hard to beat that code, for speed.

Upvotes: 2

ColdCat
ColdCat

Reputation: 1232

Another solution is to store all the path to compare in a sorted vector then do a std::lower_bound to find the occurrence.
You can then do a switch on a an index which is less cryptic values than a hash key.

Upvotes: 1

ScottMcP-MVP
ScottMcP-MVP

Reputation: 10415

A very simple approach would be to concatenate all the strings into one string and use one call to std::string::find to see if the input has a match anywhere within.

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 310940

You can store your string literals of path names as std::set and use its method find ti determine whether a given path is present in the set.

Upvotes: 1

Raymond Burkholder
Raymond Burkholder

Reputation: 504

If your predefined strings are all known at runtime, you can try using boost::spirit. It builds the compile time strings into a trie and then uses that to parse. On a successful match, it will perform an associated semantic action. I think the Roman Numeral example may be a close fit for this sort of requirement.

If your predefined strings are not known at runtime, then a runtime built trie could be tried. I did something similar with my example code at my Keyword Matching Blog Entry.

Upvotes: 2

user823738
user823738

Reputation: 17521

Make it an integer comparison. Use a hash function, which makes an integer from your string. Integers are a lot quicker in comparing. Then just use a static lookup table or a switch to pick quickly the desired action.

One very good and fast hash function is MurmurHash2, it also has a low collision rate.
Offline generate values for your pathes, then compare the path against them:

switch (MurmurHash2(path.c_str(), path.size(), MAGIC_SEED_CONSTANT)
{
    case 0xFA01FDF1: /* /admin */
        ...
        break;
    case 0xCC040A12: /* /something-else */
        ...
        break;
    case 0xBDF450A3: /* /something-else2 */
        ...
        break;
    default:
        ...
}

Upvotes: 3

Related Questions