Lots of string compares

[Bas Nedermeijer]

Hello,

what is a efficient solution to compare a string against a lot of
possiblities?

Currently i am having a lot of

if (strcmp(checkme, "option1", strlen(checkme))) {
value = OPTION1;
}

is there an other option? Or can i (ab)use a map or something for this?
Only then i would have the problem of filling the map first on every
call (or use a global).

I am using the current setup to gather input from keyboard / remote and
network. So i can handle the commands on a central place.

Suggestions welcome

gr. Bas

 

[Steve Pope]

Hello,

what is a efficient solution to compare a string against a lot of
possiblities?

Currently i am having a lot of

if (strcmp(checkme, "option1", strlen(checkme))) {
value = OPTION1;

is there an other option?

(I think there are at least two problems in the above line
of code, but...)

How do you know this is not efficient enough?

Yes, you could use a std::map, however if you don't otherwise
need the map data structure, strcmp() or similar works just fine.

Steve

 

[Daniel T.]

what is a efficient solution to compare a string against a lot of
possiblities?

Currently i am having a lot of

if (strcmp(checkme, "option1", strlen(checkme))) {
value = OPTION1;
}

is there an other option? Or can i (ab)use a map or something for this?
Only then i would have the problem of filling the map first on every
call (or use a global).

I am using the current setup to gather input from keyboard / remote and
network. So i can handle the commands on a central place.

Suggestions welcome

Time to have FUN WITH FUNCTORS that fabulous game show in which you can
amaze your programmer friends with your esoteric knowledge.

const char* opt[] = { "opt1", "opt2", "opt3" }; // continue as needed
enum options { opt1, opt2, opt3, numOpts };

// ignore what's behind the curtain, just enjoy how easy
// this is to use in the "find_option_for" function

struct c_str_equal_to :
unary_negate<binder1st<pointer_to_binary_function<const char*,
const char*, int> > >
{
c_str_equal_to( const char* value ) :
unary_negate<binder1st<pointer_to_binary_function<const char*,
const char*, int> > >( bind1st( ptr_fun( &strcmp ), value ) )
{ }
};

// in debug, we first make sure there are no programming mistakes
// returns the correct option for the string passed in

options find_option_for( const char* value ) {
assert( find_if( opt, opt + numOpts, c_str_equal_to( value ) ) !=
opt + numOpts );
return (options)distance( opt, find_if( opt, opt + numOpts,
c_str_equal_to( value ) ) );
}

int main() {
options value = find_option_for( "opt3" );
assert( value == opt3 );

char checkme [4];
strcpy( checkme, "opt2" );
value = find_option_for( checkme );
assert( value == opt2 );
}

Seriously though, maybe you should just put the "checkme" value into a
std::string and use it directly instead of converting it to an enum (or
whatever type 'value' is.)

 

[Roland Pibinger]

what is a efficient solution to compare a string against a lot of
possiblities?

More details would be helpful.

Currently i am having a lot of

if (strcmp(checkme, "option1", strlen(checkme))) {

you probably mean strncmp here

value = OPTION1;
}
is there an other option?

In general strcmp (and in you example also strncmp) is slower than the
comparison with a string class that stores the actual length of the
string. operator== of such a string class might be implemented as
(buf is the internal character buffer):

friend inline
bool operator== (const string& left, const string& right) {
return left.length() == right.length()
&& *(left.buf) == *(right.buf)
&& strcmp (left.buf, right.buf) == 0;
}

When the actual length is stored in the string class then
string::length() is fast and not-equal strings are detected without a
call to strcmp(). It depends on the string implementation.

Best wishes,
Roland Pibinger

 

[Greg Comeau]

More details would be helpful.


you probably mean strncmp here


In general strcmp (and in you example also strncmp) is slower than the
comparison with a string class that stores the actual length of the
string. operator== of such a string class might be implemented as
(buf is the internal character buffer):

friend inline
bool operator== (const string& left, const string& right) {
return left.length() == right.length()
&& *(left.buf) == *(right.buf)
&& strcmp (left.buf, right.buf) == 0;
}

When the actual length is stored in the string class then
string::length() is fast and not-equal strings are detected without a
call to strcmp(). It depends on the string implementation.

For arbitrary strings this is probably so.
When not arbitrary, may not be so.

 

[Frederick Gotham]

Bas Nedermeijer posted:

what is a efficient solution to compare a string against a lot of
possiblities?

Depends if you know for sure that it must match one of the strings exactly.
If it must match, then all you need do is pick out a character index that's
unique in every string. For instance, if it must match one of the
following:

ardvard
arduous
ancestry
armadillo

, then we can single out the 4th character becauses it's unique to each
one:

switch(str[3])
{
case 'v': ...

case 'u': ...

case 'e': ...

case 'a': ...
}


(There might be the slight problem of reading past the end of a string such
as "a").

If you're not sure whether they'll match, then one possible solution would
be strcmp, although I'm not sure how efficent that will be if executed
multiple times. Perhaps you should code it yourself:

for( ; *p; ++p)
{
if ('a' == *p) CheckForArdvark();
if ('b' == *p) CheckForBaracuda();
}

 

[Frank Puck]

Hello,

what is a efficient solution to compare a string against a lot of
possiblities?

create a code generator which compares single characters via a switch
statement.
I call this a string tree -- it can be done dynamically or via generated
code.
e.g. if I have to fixed strings "aa" bb" to compare against the generated
code would look like:

switch (p[0])
{ default:
return ~0;
case 'a':
switch (p[1])
{ default:
return ~0;
case 'a':
return eID_AA;
}
break;
case 'b':
switch (p[1])
{ default:
return ~0;
case 'b':
return eID_BB;
}
}


This is very fast.
Finding a string depends only on the lenght of the string -- not of the
number of strings available for comparision.

 

[Frederick Gotham]

Frank Puck posted:

return ~0;

What's the ~0 for?

On Two's complement, it will yield -1.

On One's complement, it will yield negative zero.

On Sign-magnitude, it will yield INT_MIN.

So what exactly do you what it to mean... ?

 

[Yannick Tremblay]

Hello,

what is a efficient solution to compare a string against a lot of
possiblities?

Currently i am having a lot of

if (strcmp(checkme, "option1", strlen(checkme))) {
value = OPTION1;
}

is there an other option? Or can i (ab)use a map or something for this?
Only then i would have the problem of filling the map first on every
call (or use a global).

A C++ answer: Yes, use a map.

From what you hint, you have a number of known possible options:
"option1", "option2", ... "optionN"
You want to check the input against the list of known option to do something:

So:

First set up your map at start up. Once and only once:

std::map<std::string, value_type> theOptionMap;
map[std::string("option1")] = OPTION1;
map[std::string("option2")] = OPTION2;
....
map[std::string("optionN")] = OPTIONN;

// do whatever else initialisation you want to do.

// main loop:

std::string checkme = getInput();

// If checkme is always in the map, you can use:
value = theOptionMap[checkme];

// if not try:

std::map<std::string, value_type>::const_iterator iter = theOptionMap.find(checkme);
if( iter != theOptionMap.end() )
{
value = *iter;
}
else
{
// do whatever for an illegal option

}

The quality of this solution:

1- Easy to read, maintain, implement, expand, debug

2- Fast:
This is fast because the std::map keep the keys in sorted
order. Finding an option runs in logarithmic time. so instead of
comparing in average N/2 strings before finding the right one, you
only need to compare log(N). This is a huge gain if N is large.

Hope this helps


Yan