0

我正在为使用 C++ 的“标准标准输入程序”的比赛编写程序。输入的第一行表示从那时起预计有多少行 (x) 作为输入。这些输入行可以是字符串、整数或两者的某种组合，并且每一行正好包含两个由空格分隔的元素。目前，我以类似于以下的方式一次接收每一行（在请求下一行之前处理信息）：

  string initial;
  getline (cin,initial);
  istringstream stringStream (initial);
  vector<string> parsedString;
  vector<int> data;
  char splitToken = ' ';
  while ( !stringStream.eof() )
  {
    string subString;
    getline( stringStream, subString, splitToken);
    parsedString.push_back( subString );
  }

  for (int i = 0; i <parsedString.size(); i++)
  {
    string temp = parsedString[i];
    int intTemp = atoi(temp.c_str());
    data.push_back(intTemp);
  }
  unsigned int n = data[0];
  unsigned int m = data[1];

在这种特定情况下，我知道传入的数据将是两个整数，但情况并非总是如此。我想知道是否有某种方法可以使我的代码更快，或者通过改变我的方法（也许在知道有多少输入行之后立即获取所有输入行）或者通过使用更好的内置 C++ 函数来拆分传入的行空间到组成它们的两个元素。

谢谢

4

3 回答 3

1

通常，在 C++ 中读取输入的习惯用法更接近于以下方面：

std::ios_base::sync_with_stdio(false); //tell iostreams to be fast
int number_of_lines;
std::cin >> number_of_lines;
if (!std::cin) *ERROR*;

for( ; number_of_lines>0; --number_of_lines) {
    unsigned n, m;
    std::cin >> n >> m;
    if (!std::cin) *ERROR*;
    //process n and m here
}

您说“这些输入行可以是字符串、整数或两者的某种组合”，但您如何知道哪些是哪些？上面的代码假设一切都是一个数字，因为如果你不知道类型，输入是没有用的。

于 2013-01-24T00:10:59.927 回答
1

好的，如果您想谈论其他方法，这里是另一种方法：几乎所有使用字符串繁重的代码的大（性能）问题，即有很多复制操作......一种天真的方法（使用由初学者）是在从字符串或内存缓冲区中查找/解析/提取smth时制作大量临时字符串......

另一种方法（当源缓冲区的生命周期允许时）是从缓冲区中查找、解析或提取数据，而无需复制源字符串的任何特定部分。为此，可以使用boost::range库和boost::iterator_range类（与 boost string_algo 结合使用）。这样可以执行通常的查找/解析任务并避免复制部分字符串。

我的经验中的一个例子：前段时间（用于性能测试）我的同事写了 3 个版本的相同配置解析器（配置文件大约几兆字节）：

  • 使用std::string::find
  • 使用boost::tokenizer
  • 和boost::iterator_range

结果令人惊讶：

  • 使用 -O0 优化std::string::find获胜（基于解析器的大约 3 倍boost::tokenizer和大约 5 倍）iterator_range
  • 但在 -O3 一切都变了：boost::iterator_range绝对是赢家！（大约 12 倍以上std::string::find！）

结果是相当可预测的：高度模板化的代码boost::string_algo和朋友也高度内联......

这就是为什么我个人喜欢用它boost::iterator_range来解析字符串......

所以我建议将所有内容（尽可能多地）读入一个std::string，std::vector<char>（更好的一个，因为它有内存连续性保证，所以你可以read()直接从流到容器中）或std::deque<char>，然后使用boost::string_algo和boost::iterator_range解析它试图避免任何（无用的）从源字符串复制到临时位置......也尝试使用boost::lexical_cast转换数字（或您自己的范围感知数字转换器）

还有一个建议：尽量避免内存（通常）分配——这确实是一个繁重的操作。rserve()当您知道您想要存储的数据的可能大小时，请使用容器成员。最后，尝试使用自定义（棘手的）分配器而不是（通常是愚蠢的）默认分配器。

请注意，在 C++11std::string中，内存连续性保证为std::vector.

于 2013-01-24T00:25:02.903 回答
0

在许多系统上（包括 Linux 上的 GCC），C++ I/O 流非常慢。如果速度是您最关心的问题，请使用<stdio.h>, eg scanf()and (even faster:) getchar()，并手动进行解析，如下面的状态机：

int c;
int state = 0;
while ((c = getchar()) >= 0) {
  switch (c) {
   case ' ': case '\t':
    ...;
    ... if (state == ...) { ...; state = ...; }
    break;
   case '\n':
    ...;
    break;
   default:
    ...;
  }
}

尽可能少地复制数据。（比如问题string temp = ...中做了一个不必要的副本，可以通过引用来消除：string &temp = ....）如果可能的话，用状态找出下一个字符的最终位置c，并把它放在那里，不要将来复制或移动它。

于 2013-01-24T00:11:46.177 回答