c++ 有没有比一次遍历一个字符更快的方法来查找“\n”字符?

wqsoz72f  于 2022-11-19  发布在  其他
关注(0)|答案(4)|浏览(150)

在计算行数时查看sample implementation of wc.c,它循环遍历文件,一次一个字符,并累计'\n'以计算换行符的数量:

#define COUNT(c)       \
      ccount++;        \
      if ((c) == '\n') \
        lcount++;
  • 有没有办法只在文件中查找“\n”,然后继续跳到换行符并进行计数?
  • 寻找'\n'是否与每次阅读一个字符,直到我们看到'\n'并对其进行计数相同?
ctrmrzij

ctrmrzij1#

当然,除了一个字符之外,并不是所有的字符都是'\n'。无分支算法可能会更快。
你试过std::count吗?

#include <string>
#include <algorithm>

int main() {
  const auto s = std::string("Hello, World!\nfoo\nbar\nbaz");
  const auto lines_in_s = std::count(s.cbegin(), s.cend(), '\n');
  return lines_in_s;
}

Compiler Explorer
或者用文件:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>

int main() {
    if (std::ifstream is("filename.txt"); is) {
        const auto lines_in_file =
            std::count(std::istreambuf_iterator<char>(is),
                       std::istreambuf_iterator<char>{}, '\n');

        std::cout << lines_in_file << '\n';
    }
}

Compiler Explorer

aij0ehis

aij0ehis2#

如果你有关于你正在看的字符串的领域知识,那么你可以跳过看每个字符的唯一方法是:
如果你“知道”你要处理的是一个至少有50个单词的连续段落,你可以在每一个'\n'之后前进100或200个字符,这样可以节省一些时间。当然,你需要测试和优化跳转长度,但这样你就不需要检查每一个字符了。
对于一个通用的计数函数,你必须查看每一个可能的字符。

jmp7cifd

jmp7cifd3#

问:有没有比一次阅读一个字符更快的方法来计算文件中的行数?
答:答案是否定的,但可以并行化计数,这可能会缩短运行时间,但程序仍然必须运行一次每个字节。这样的程序可能受IO限制,因此在这种情况下,并行化的有用程度取决于所涉及的硬件。
问:有没有一种方法可以从一个换行符跳到下一个换行符,而不必通读中间的所有字节?
答:快速的答案是否定的,但是如果你有一个非常大的文本文件,你可以做的是制作一个偏移量的“索引”文件。你仍然需要对文件进行一次遍历以生成这样的文件,但是一旦它被制作好,可以通过阅读索引中的第n个偏移然后“搜索”到它来找到第n行。如果使用固定宽度的偏移量,则可以通过一些简单的算法直接查找所需的偏移量,读取偏移量的索引,然后查找文件中的正确位置。可以在生成索引的同时获得行计数。一旦生成了索引,如果必须再次计算行计数,则可以根据索引文件的大小快速确定行计数。
可能应该提到的是,由于多字节字符编码,文本文件中的行数可能不是从'\n'字节数得出的。要计算行数,需要逐个字符扫描文件,而不仅仅是逐个字节扫描,为此,需要知道使用的是什么字符编码方案。

jmo0nnb3

jmo0nnb34#

您可以使用strchr函数来“跳转”到字符串中的下一个'\n',并且在某些平台上会更快,因为strchr通常是用汇编语言实现的,并且使用处理器指令,这些指令可以更快地扫描内存(如果这些指令可用的话)。如下所示:

#include <string.h>

unsigned int count_newlines(const char *str) {
   unsigned result = 0;
   const char s = str;
   while ((s = strchr(s, '\n')) != NULL) {
      ++result; // found one '\n'
      ++s; // and start searching again from the next character
   }
   return result;
}

相关问题