A more efficient way

[Eirik WS]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

I was wondering if maybe I could use the switch statement,
but I have to compare each colour to the string, and I can't do
that in a switch statement, can I?

Thanks for any help.
I hope this isn't off-topic.

 

[Ed Morton]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;

if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Well, there's the obvious: use "else"s between the "if"s so you can stop
at the first match rather than going theoguh every comparison even after
finding the right one! You should also order the tests so the most
likely get evaluated first (if applicable).

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

I was wondering if maybe I could use the switch statement,

No. See the FAQ: http://www.eskimo.com/~scs/C-faq/q20.17.html

but I have to compare each colour to the string, and I can't do
that in a switch statement, can I?

Thanks for any help.
I hope this isn't off-topic.

No, though you could've read the FAQ first.

Ed.

 

[Malcolm]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;

What you can do is this.

struct word
{
char *str;
int id;
};

/* table must be alphabetical */
struct word table[100] = { "aa", AA, "ab", AB ... "zyggle", ZYGGLE };

Then you perform a binary search for the word you want, and extract the id.
This will cut down the number of comparisons you have to make to a
considerable degree.

If you are adding and subtracting words from the dictionary then things
become a bit more complicated - time to go over to comp.programming.

 

[Eric Sosman]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

Efficiency can be defined and measured in more than one
way, and the different definitions can lead to different
answers to your question.

For "code efficiency" I'd suggest an array of simple
struct objects, searched with a loop:

struct {
const char *name;
int /* or whatever */ code;
} color[] = {
{ "kvit", KVIT },
{ "raud", RAUD },
...
{ "lilla", LILLA },
};
#define COLORS (sizeof color / sizeof color[0])
...
for (i = 0; i < COLORS; ++i) {
if (strcmp(farge, color.name) == 0) {
peikar_til_glas_struktur->farge = color.code;
break;
}
}
if (i >= COLORS) {
error(); /* not recognized */
}

If speed is the "efficiency" measure, you might start with
an array as above, but sorted on the `name' elements to permit
a binary search. You might do even better if you know how often
each color appears (see Knuth, "The Art of Computer Programming,
Volume III: Sorting and Searching" section 6.2.2). Or you might
use a trie (ibid, section 6.3); a one-level trie followed by a
sequential search might look like

switch (farge[0]) {
case 'k':
if (strcmp(farge, "kvit") == 0)
... = KVIT;
else
error();
break;
case 'g':
if (strcmp(farge, "gul") == 0)
... = GUL;
else if (strcmp(farge, "grøn") == 0)
... = GROEN;
else
error();
break;
...
default:
error();
break;
}

That is, you could use the first letter of `farge' to select
which small subset of possible names to search. This technique
could also be adapted to the array scheme.

I was wondering if maybe I could use the switch statement,
but I have to compare each colour to the string, and I can't do
that in a switch statement, can I?

No; the `case' values must be integer constants. However,
see Question 20.17 in the comp.lang.c Frequently Asked Questions
(FAQ) list

http://www.eskimo.com/~scs/C-faq/top.html

for a suggestion of yet another way to conduct the search. "In
the limit," 20.17's suggestion leads to hashing schemes which
you might also find attractive (but don't forget to consider the
computational cost of the hashing function itself).

 

[Ed Morton]

Eirik WS wrote:


No. See the FAQ: http://www.eskimo.com/~scs/C-faq/q20.17.html

Hmm, although what I just said is true, you COULD do this:

switch(farge[0]) {
case 'k':
if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
break;
case 'r':
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
break;
case 'b':
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
break;
case 'g':
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
else if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
break;
case 'r':
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
break;
case 's':
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
break;
case 'm':
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
break;
case 'i':
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
break;
case 'l':
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;
break;
default:
/* whatever */
break;
}

It might save you some cycles - try it and see.

Ed.

 

[Jan Engelhardt]

Is there a more efficient way of comparing a string to different words?

I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;

[...]

My 2 cents:

#define CMP(__str, __var) \
if(strcmp(farge, (__str)) == 0) { peikar = (__var); }

CMP("kvit", KVIT)
else CMP("indigo", INDIGO)
else CMP("lilla", LILLA)

It is not a real solution, but spares some of the typing.
In conjunction with a Btree this might become better (from the speed side),
or probably worse (from the typing side).




Jan Engelhardt
--

 

[Thomas Stegen CES2000]

Hmm, although what I just said is true, you COULD do this:

switch(farge[0]) {
case 'k':
if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
break;
case 'r': [snip]
It might save you some cycles - try it and see.

I was about to suggest a hashtable. What you are doing above seems
to be somewhere on the road to a hashtable. A hashtable would be
easier to maintain if the number of entries gets larger. With a
suitable hash function it will be quite fast as well, just look at
the first and maybe the second character.

In what the OP is trying to do there might not be /a lot/ of options
(since he is comparing for colours), but in general I would go for
some sort of hashtable or tree. The tree would have 26 children
(or in the case of norwegian 29), one for each letter and you just
go down the tree until a leaf is found. This last approach guarantees
that each letter is only looked at once. If it will be faster than a
hashtable... Well, that depends

 

[Derk Gwen]

# Is there a more efficient way of comparing a string to different words?
# I'm doing it this way:

Create a perfect hash table. Hash the string and probe the table.
If it's a hit, you got a match, otherwise the string differs from
all other strings.

 

[Martin Dickopp]

# Is there a more efficient way of comparing a string to different words?
# I'm doing it this way:

Create a perfect hash table. Hash the string and probe the table.
If it's a hit, you got a match, otherwise the string differs from
all other strings.

<OT>
There is tool that helps creating a perfect hash table:
http://www.gnu.org/software/gperf/gperf.html
</OT>

Martin

 

[Jared Dykstra]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

I was wondering if maybe I could use the switch statement,
but I have to compare each colour to the string, and I can't do
that in a switch statement, can I?

Thanks for any help.
I hope this isn't off-topic.

If this list is this small, another implementation probably isn't
worth the added complexity.

The obvious optimization is to put your search terms into a list and
sort them. You could then use a binary search algorithm to find your
match. A binary search O(log(n)) versus a linear compare O(n) isn't
going to offer much optimization on such a small dataset, however.

There are other things which could be done that are much dirtier
hacks. For example, on a 32 bit architecture, you could cast the
first 4 bytes of variable 'farge' to a UINT32 and use a switch()
statement--providing each first 4 bytes were unique and a random value
of 'farge' was never encountered. However, if I saw this when
reviewing your code, I would *NOT* be impressed.

 

[CBFalconer]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

I was wondering if maybe I could use the switch statement,
but I have to compare each colour to the string, and I can't do
that in a switch statement, can I?

Don't know about more efficient, but it can certainly be more
easily modifiable:

enum colors {WHITE, RED, BROWN, BLACK, UNKNOWN};
static char *colornames = {"white", "red", "brown", "black"};

/* -------------- */

enum colors getcolor(const char *desciption)
{
enum colors c;

for (c = WHITE; c < UNKNOWN; c++)
if (0 == strcmp(description, colornames[c])) break;
return c;
} /* getcolor */

 

[Jack Klein]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;

[...]

My 2 cents:

#define CMP(__str, __var) \

^^^^^ ^^^^^

What reason do you have for making your code illegal by defining
identifiers violating the namespace by the C standard for the
implementation in all contexts?

 

[Rob Thorpe]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;
if(strcmp(farge, "raud") == 0)
peikar_til_glas_struktur->farge = RAUD;
if(strcmp(farge, "blå") == 0)
peikar_til_glas_struktur->farge = BLAA;
if(strcmp(farge, "gul") == 0)
peikar_til_glas_struktur->farge = GUL;
if(strcmp(farge, "grøn") == 0)
peikar_til_glas_struktur->farge = GROEN;
if(strcmp(farge, "rosa") == 0)
peikar_til_glas_struktur->farge = ROSA;
if(strcmp(farge, "svart") == 0)
peikar_til_glas_struktur->farge = SVART;
if(strcmp(farge, "med mønster") == 0)
peikar_til_glas_struktur->farge = MED_MOENSTER;
if(strcmp(farge, "indigo") == 0)
peikar_til_glas_struktur->farge = INDIGO;
if(strcmp(farge, "lilla") == 0)
peikar_til_glas_struktur->farge = LILLA;

Don't worry if you don't understand the variable names. It's
irrelevant. You get the point anyway.

Don't worry about this code. It's probably fine, I've written entire
tons of code that looks exactly like it.

* If your just interested in how to do it more efficiently:

1. prepend everything with "else"
2. Don't use strcmp straight away, first compare the first character
of the word. Only if they match do you use strcmp.

* If you really, really need it to go fast:

Take parsing out of your main loop!

 

[Eric Sosman]

Is there a more efficient way of comparing a string to different words?
I'm doing it this way:

if(strcmp(farge, "kvit") == 0)
peikar_til_glas_struktur->farge = KVIT;

[...]

My 2 cents:

#define CMP(__str, __var) \

^^^^^ ^^^^^

What reason do you have for making your code illegal by defining
identifiers violating the namespace by the C standard for the
implementation in all contexts?

This particular usage is legitimate, as far as I can tell,
however ill-advised.

#include <stdio.h>
#define MACRO(__FILE__,__LINE__,__STDC__) \
__FILE__ __LINE__ __STDC__
MACRO(int,main,(void)) {
MACRO((void),puts,("Hello, world!"));
MACRO(return,0,
}

.... appears to be a conforming program. (If someone can show
otherwise, I'd be glad to learn of it.)

 

[Christian Bau]

Don't worry about this code. It's probably fine, I've written entire
tons of code that looks exactly like it.

* If your just interested in how to do it more efficiently:

1. prepend everything with "else"
2. Don't use strcmp straight away, first compare the first character
of the word. Only if they match do you use strcmp.

Also depends what you mean with "efficiently": It might not mean "what
is the fastest possible code to achieve this", it might mean "what is
the fastest way to write this code down and keep it maintainable".

 

[Rob Thorpe]

Also depends what you mean with "efficiently": It might not mean "what
is the fastest possible code to achieve this", it might mean "what is
the fastest way to write this code down and keep it maintainable".

That's true, if someone does something like this it certainly requires
a comment saying *why* it's done this way.
The same goes for any speed improving technique.

And when comparing speed improvement techniques it's important to
compare the amount of commentary that's necessary to explain them!

 

[Nick Landsberg]

That's true, if someone does something like this it certainly requires
a comment saying *why* it's done this way.
The same goes for any speed improving technique.

And when comparing speed improvement techniques it's important to
compare the amount of commentary that's necessary to explain them!

Speed improvements MAY be necessary if the code is going to
be used hundreds or thousands of times a second, in which case
I agree that the rationale for any speed improvements needs to
be documented (both in the documentation and with appropriate
comments in the code).

However, the original code posted, is, IMHO, not easily
maintainable since it requires a recompilation of the module
every time a new "option" is added. (I know, this is OT in c.l.c)

 

[CBFalconer]

.... snip ...

However, the original code posted, is, IMHO, not easily
maintainable since it requires a recompilation of the module
every time a new "option" is added. (I know, this is OT in c.l.c)

You're wrong. Rephrasing the code to be portable AND efficient
AND modifiable is very much on topic. Somewhere back there I
suggested a table driven method.

 

[Rob Thorpe]

Speed improvements MAY be necessary if the code is going to
be used hundreds or thousands of times a second, in which case
I agree that the rationale for any speed improvements needs to
be documented (both in the documentation and with appropriate
comments in the code).

Yes, somewhere further up this long thread I also said that if parsing
is speed critical the application should be redesigned to make it less
important.

However, the original code posted, is, IMHO, not easily
maintainable since it requires a recompilation of the module
every time a new "option" is added. (I know, this is OT in c.l.c)

Yes, but sometimes that's OK, it all depends on what this bit of code
is for, which we don't really know.