Re: A more efficient way
From: Eric Sosman (Eric.Sosman_at_sun.com)
Date: 02/04/04
- Next message: John Bode: "Re: increment doubt"
- Previous message: Richard Heathfield: "Re: Style question"
- In reply to: Eirik WS: "A more efficient way"
- Next in thread: Derk Gwen: "Re: A more efficient way"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 04 Feb 2004 15:23:20 -0500
Eirik WS wrote:
>
> 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[i].name) == 0) {
peikar_til_glas_struktur->farge = color[i].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).
-- Eric.Sosman@sun.com
- Next message: John Bode: "Re: increment doubt"
- Previous message: Richard Heathfield: "Re: Style question"
- In reply to: Eirik WS: "A more efficient way"
- Next in thread: Derk Gwen: "Re: A more efficient way"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
