Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have a string that must be splitted into an array of strings so using strtok makes perfect sense but before that I want to allocate the array of strings and thus I count how many words in it.

static inline int countWords(char *str)
{
        int count = 0;
        char *buf = str;

        if(isgraph(*buf) > 0)//checking for the first word
                count++;
        while(*buf != '\0')
        {
                if(isblank(*buf) > 0){//reached a blank
                        while(*buf == ' ' || *buf == '\t')//keep ignoring them
                                buf++;
                        if(*buf == '\0')//return if string is over
                                return count;
                        count++;//no more blank and string didn't end=new word
                }
                buf++;
        }
        return count;
}

Am I doing this right? I've tested all weird cases that can come to my mind and it seems to work; but is there a faster way to do this? I am mainly concerned about the performance of the above code.

share|improve this question

4 Answers 4

up vote 6 down vote accepted

Code comments:

  • The parameter to the function should be const - "const correctness".
  • Don't use the variable name "buf" for a variable that is not a memory buffer of some sort.
  • You have 3 different ways of checking for spaces in your code, you need to check for them in a consistent manner. Either use !isgraph which is the same as checking for ' '. Or isblank, which is the same as checking for ' ' and '\t'. Or possibly isspace, which checks for any form of white space character. I'll use isblank in my suggestion, since I don't know the nature of the string input.
  • Your code is a bit hard to follow, with several nested loops and if statements.

When I spontaneously rewrite your code to improve readability, I end up with this:

#include <ctype.h>

static int countWords (const char* str)
{
  int count = 0;

  while (*str != '\0')
  {
    while (*str != '\0' && isblank(*str)) // remove all spaces between words
    {
      str++;
    }
    if(*str != '\0')
    {
      count++;
    }

    while (*str != '\0' && !isblank(*str)) // loop past the found word
    {
      str++;
    }
  }

  return count;
}

This code is very easy to understand. However, you asked for optimization and my code doesn't look all that effective; it is possibly slower than the original. Particularly, we have multiple checks for '\0' all over the place.

Note that any truly meaningful optimization requires that 1) we have actually encountered and measured a real performance problem, 2) we have noticed that the compiler is doing a poor job at optimizing that particular problematic code, and 3) we have fairly good knowledge of the target CPU and hardware. It a bad idea to manually optimize code if those 3 above conditions are not met.

Still, I'll attempt a manual optimization of this, since it was requested. It may or may not be more effective. Branch prediction may be a more serious concern than the number of comparisons executed, for example. For what it is worth, here you go:

#include <ctype.h>
#include <stdbool.h>

static inline int countWords (const char* str)
{
  int count = 0;
  bool look_for_data = true;

  while (*str != '\0')
  {
    if( (look_for_data ^ isblank(*str)) != 0) // is it a character of interest?
    {
      count += (int)look_for_data; // increase count if we are looking for data
      look_for_data = !look_for_data;
    }
    str++;
  }

  return count;
}

With this optimization we have managed to reduce the number of instructions and the number of branches both. But as you can tell, the code now turned quite obscure.

Explanation: The fundament of this code is that one lap in the loop corresponds to one character in the input string. The bool variable keeps track of whether the code is currently looking for spaces or non-spaces.

We are only interested in the places in the string where we go from looking for spaces to looking for data, or vice versa. When that happens, we should start looking for data if we were looking for spaces, and the other way around. Also, in the case where we go from spaces to data, we should increase the word counter.

The boolean logic truth table is:

look_for_data  isblank  of interest  comment
false          false    false        we are at symbols and found another symbol
false          true     true         we are at symbols and found a space
true           true     false        we are at spaces and found another space
true           false    true         we are at spaces and found a symbol

We can see that this happens to be the truth table for logical XOR.

share|improve this answer

Here are some impressions:

    if(isgraph(*buf) > 0)

Why > 0? Why not just if (isgraph(*buf))?

    while(*buf != '\0')

You don't have to write '\0'. You can just write 0. Or you can just write while (*buf). This is a style thing though, different people make different choices.

            if(isblank(*buf) > 0){//reached a blank
                    while(*buf == ' ' || *buf == '\t')//keep ignoring them
                            buf++;

It's weird that you do isblank(*buf) in the if statement, but *buf == ' ' || *buf == '\t' in the loop. I would do isblank in both places. (Seems also like you could fold the if into the while entirely...)

                    if(*buf == '\0')//return if string is over
                            return count;

Why do you need this? Your loop termination condition is already while (*buf), so the check almost seems redundant... Now, it does seem like the upcoming count++ and buf++ will create problems omitting this, but I would rather re-arrange those than make this loop look overly complicated. Just my opinion. YMMV.

share|improve this answer
3  
"You don't have to write '\0'" Why not? It makes it clear to the reader that the code is checking for a string null termination and not something else. This is how you make the code self-documenting. To replace '\0' with 0 is just plain bad advice. –  Lundin Dec 20 '12 at 7:41
1  
@Lundin - I personally think that '\0' is weird and verbose. 3 chars you don't need to type. And if you're working in Win32 you'll end up with L'\0' which is just madness. But I'm one of those people who would rather write while (*buf). –  asveikau Dec 20 '12 at 16:23
2  
'\0' is not "style", it is a necessity, so that the reader won't confuse it with integer 0, or NULL, or a boolean. '\0' means that you are dealing with a string null termination and nothing else. Furthermore, my own arrogant opinion is that programmers who obfuscate their programs because they are too lazy to type a few more letters, should find another career. –  Lundin Dec 20 '12 at 16:46
1  
@Lundin - If it is necessity why does the compiler accept it the other way? :-) I don't consider it obfuscation, if it appears in while or if it's clearly a boolean - and if there is ambiguity (there hardly ever is due to context, consistent naming patterns, and if need be, comments) then the reader can just glance over at the type. –  asveikau Dec 20 '12 at 20:10
1  
Because character literals are int in C, not char as in C++. C allows countless of really bad things. To assume that the C standard is rational is a grave mistake: when the C language was created, nobody knew what was good programming style. What I meant with boolean is the intended type. if(x==0) is a boolean expression, so is if(my_bool). But not if(my_int), that is bad style. For example, the MISRA-C committee even considered such code to be a safety hazard, since the MISRA-C standard requires all control expressions to be "effectively boolean". –  Lundin Dec 21 '12 at 7:17

Adel, why are you so concerned about the performance of your code? Readability is more important, unless there is a strong need to optimise (for example, if you have to count the number of words in strings all the time in you application).

You code fails in readability for me but others have indicated where the problems lie.

For what it is worth, here is my version of word counting. It is probably not efficient but I think it is clear once you know what strspn and strcspn do (count the length of sequences containing/not-containing the defined char-set)

static int
count_words(const char *s)
{
    const char *cset = " \t\n\r\v\f";
    size_t len;
    int word = 0;

    s += strspn(s, cset);

    while ((len = strcspn(s, cset)) > 0) {
        ++word;
        s += len;
        s += strspn(s, cset);
    }
    return word;
}
share|improve this answer

Taking a different approach, I'll question why you need to count the number of words at all. The performance and readability of code you don't have to write is not an issue! Unless you are very short of memory, why not not just allocate enough elements in your array to handle the most words that strtok could possibly find?

Since strtok will skip over repeated separator characters, the most words that it can find is (strlen(str)+1)/2 which happens in the worst case where there are alternating space and non-space characters. The +1 is to handle the worst case of an odd length string which starts and ends in a non-space character (for example x x has length 3 and 2 words). You will need an extra element if you are using a null pointer to delimiter the array itself.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.