计算字符串单词的最快方法

Question

我怎样才能使这个算法更快并缩短这段计算给定字符串单词的代码？

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;
}

Answer 1

你的代码很好，speed-wise。但是如果你想让你的代码更短，你可以使用 find_first_not_of() and find_first_of 标准函数，就像我在下面的代码中所做的那样来解决你的任务。

我假设您的所有单词仅由 space 分隔。如果需要其他分隔符，您可以在我的代码的两行中传递类似 " \r\n\t" 而不是 ' ' 的内容。

可以在您的代码中进行的一个小优化是当您注意到在第一个 while-loop 之后我们位于 non-space 字符处，因此我们可以添加 ++i; 行在第二个循环之前免费。同样，在第二个 while-loop 之后，我们位于 space 字符处，因此我们可以在第二个 while 循环之后再添加一个 ++i; 行。这将提供一点点速度增益，以避免在 while 循环中进行额外的两次检查。

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;
}

输出：

计算字符串单词的最快方法

Fastest way to count words of string

c++

string

algorithm