Fastest way to count words of string

Question

How could I make this algorithm faster and shorten this code which counts word of given string?

int number_of_words(std::string &s) {
  int count = 0;
  for (int i = 0; i < s.length(); i++) {
    // skip spaces
    while (s[i] == ' ' && i < s.length())
      i++;
    if (i == s.length())
      break;
    // word found
    count++;
    // inside word
    while (s[i] != ' ' && i < s.length())
      i++;
  }
  return count;
}

You don't need to copy the string on each call, pass it as const reference instead. — Quimby, May 01 '22 at 13:15
you can make it faster, but the **fastest** code is definitely not shorter because they'll be extremely complex with SIMD, multithreading, loop unrolling... And fastest is also relative because some code might be fast on a system but slower on another system — phuclv, May 01 '22 at 13:21
What's wrong with the current length? The complexity makes sense. O(n) is the fastest you could do this. — JohnFilleau, May 01 '22 at 13:41
std::regex rx("\\w+"); int count = std::distance(std::sregex_iterator(text.begin(), text.end(), rx), std::sregex_iterator()); — QuentinUK, May 01 '22 at 13:44
@RocketProcd Why it needs to be shortened? You could do away with only one `for` loop testing a single character and tracking `bool inside_word` and having `if`s changing it. — Quimby, May 01 '22 at 13:47
@RocketProcd `std::istringstream strm(s); std::string w; int count = 0; while(strm >> w) ++count;` You should have piggybacked off of the solution to your [other question here](https://stackoverflow.com/questions/72069293/reverse-string-with-one-space/72077249#72077249) — PaulMcKenzie, May 01 '22 at 13:52
@RocketProcd code *may* be better if it has fewer lines of code. Length and clarity are related, but not equivalent. "Better" can also mean different things (faster, more maintainable, more debuggable, more readable, etc.) — JohnFilleau, May 01 '22 at 13:56
@PaulMcKenzie thanks, I didn't understand true meaning of `istringstream` now I get it — Rocket Procd, May 01 '22 at 14:02
`code is better if it has less lines of code` this isn't quite true. Look at libraries (for example the C++ STL) you'll see that they're very very long. Short, fast, maintainable, scalale and readable are almost never in the same sentence — phuclv, May 01 '22 at 14:37
@PaulMcKenzie I have one question, is this `if (i == s.length())break;` unnecessary? Today it came up to my mind... — Rocket Procd, May 07 '22 at 15:34

Arty · Accepted Answer · 2022-05-01T14:18:26.590

Your code is quite alright, speed-wise. But if you want to make your code shorter, you may use find_first_not_of() and find_first_of standard functions, like I did in following code that solves your task.

I made an assumption that all your words are separated by only spaces. If other separators are needed you may pass something like " \r\n\t" instead of ' ' in both lines of my code.

One small optimization that can be made in your code is when you notice that after first while-loop we're located on non-space character, so we can add ++i; line for free before second loop. Similarly after second while-loop we're located on space character so we may add one more ++i; line after second while loop. This will give a tiny bit of speed gain to avoid extra two checks inside while loop.

Try it online

#include <iostream>
#include <string>

int number_of_words(std::string const & s) {
    ptrdiff_t cnt = 0, pos = -1;
    while (true) {
        if ((pos = s.find_first_not_of(' ', pos + 1)) == s.npos) break;
        ++cnt;
        if ((pos = s.find_first_of(' ', pos + 1)) == s.npos) break;
    }
    return cnt;
}

int main() {
    std::cout << number_of_words("  abc  def ghi  ") << std::endl;
}

Output:

Fastest way to count words of string

1 Answers1