CODEWITHSUNDEEP
c++
helpermethod
helpermethod

Reputation: 62215

Any ways to improve this implementation (significantly)?

This is a piece of code I've written for a homework. It seems to work but I wonder if I missed something.

The task was to implement a function (here: Countwords) which counts all words in a char *. No library functions should be used.

namespace {

bool IsPrintable(char c) {
  return c >= '!' && c <= '~';
}

void SkipPrintable(const char *&s) {
  do {
    s++;
  } while (IsPrintable(*s));
}

bool IsWhiteSpace(char c) {
  return c == ' ' || c == '\t' || c == '\n';
}

void SkipWhitespace(const char *&s) {
  while (IsWhiteSpace(*s)) {
      s++;
  }
}

} // namespace

int CountWords(const char *s) {
  int count = 0;

  while (*s != '\0') {
    SkipWhitespace(s);

    if (IsPrintable(*s)) {
        count++;
        SkipPrintable(s);
    }
  }

  return count;
}

Upvotes: 0

Views: 130

Answers (4)

maxim1000
maxim1000

Reputation: 6365

In order to simplify algorithm (in terms of readability, not computational complexity), you can count word beginnings (where non-whitespace character either follows whitespace one, or is the first character in the string).

char previousCharacter=' ';
int wordsCount=0;
while(*s)
{
  if(IsWhiteSpace(previousCharacter) && !IsWhiteSpace(*s))
    ++wordsCount;
  previousCharacter=*s;
  ++s;
}

Upvotes: 0

Adam
Adam

Reputation: 171

i agree to all what is said above. your code is good enough, the important thing is that its linear so its efficient the only thing you might consider is maybe simplify it a little bit more like

bool newWord = true;
int count = 0;
while(*s != '\0')
{
    if(!IsWhiteSpace(*s))
    {
        if(newWord)
        {
            newWord = false;
            count++;
        }
    }
    else
    {
        newWord = true;
    }
    s++;
}

but again, i see no problem with your implementation as is

Upvotes: 0

Michael Aaron Safyan
Michael Aaron Safyan

Reputation: 95549

There is no way to significantly improve the algorithm, but you could make it a little bit cleaner by using a class to represent the state of the parser (e.g. current index and the string, itself, so that it does not need to be passed all over). You could also remove some of the redundancy between SkipPrintable and SkipWhitespace by implementing a single SkipWhile function that takes a bool (*ShouldSkip)(char) function pointer, and then passing in &IsWhitespace or &IsPrintable.

Upvotes: 1

Armen Tsirunyan
Armen Tsirunyan

Reputation: 133044

You solve this in linear complexity. One cannot do the same in less complexity. So you cannot significantly improve your algorithm.

Upvotes: 4

Related Questions