1

我正在解决一个需要非常快速的输入/输出的问题。更准确地说，输入数据文件最大为 15MB。是否有一种快速、读取/打印整数值的方法。

注意：我不知道它是否有帮助，但输入文件具有以下形式：

  • 第 1 行：一个数字 n
  • 第 2..n+1 行：三个数字 a、b、c；
  • 第 n+2 行：一个数字 r
  • 第 n+3..n+4+r 行：四个数字 a,b,c,d

注 2：输入文件将为stdin.

编辑：像下面这样的东西还不够快：

void fast_scan(int &n) {
  char buffer[10];
  gets(buffer);
  n=atoi(buffer);
}

void fast_scan_three(int &a,int &b,int &c) {
  char buffval[3][20],buffer[60];
  gets(buffer);
  int n=strlen(buffer);
  int buffindex=0, curindex=0;
  for(int i=0; i<n; ++i) {
    if(!isdigit(buffer[i]) && !isspace(buffer[i]))break;
    if(isspace(buffer[i])) {
      buffindex++;
      curindex=0;
    } else {
      buffval[buffindex][curindex++]=buffer[i];
    }
  }
  a=atoi(buffval[0]);
  b=atoi(buffval[1]);
  c=atoi(buffval[2]);
}
4

5 回答 5

3

一般输入/输出优化原则是执行尽可能少的 I/O 操作，读/写尽可能多的数据。

所以性能感知解决方案通常如下所示：

  1. 将设备中的所有数据读入某个缓冲区（使用上面提到的原理）
  2. 将生成结果数据的数据处理到某个缓冲区（就地或另一个）
  3. 将结果从缓冲区输出到设备（使用上面提到的原理）

例如，您可以使用std::basic_istream::read大块输入数据，而不是逐行输入。与输出类似的想法 - 生成单个字符串作为结果手动添加换行符并立即输出。

于 2012-10-25T17:43:02.783 回答
1

如果您想最小化物理 I/O 操作开销，请通过一种称为内存映射文件的技术将整个文件加载到内存中。我怀疑你会得到显着的性能提升。解析很可能会更昂贵。

于 2012-10-25T18:05:18.557 回答
0

将几个输入行放在一个缓冲区中，将它们拆分，然后在不同的线程中同时解析它们。

于 2012-10-25T18:01:47.780 回答
0

考虑使用线程。线程对很多事情都很有用，但这正是促使线程发明的问题。

其基本思想是将输入、处理和输出分开，因此这些不同的操作可以并行运行。做对了，你会看到显着的加速。

让一个线程接近纯输入。它将行读入行缓冲区。让第二个线程进行快速预解析并将原始输入组织成块。您有两件事需要解析，包含包含三元组的行数的行和包含包含四元组的行数的行。该线程将原始输入形成仍然主要是文本的块。第三个线程解析三元组和四元组，将输入重新形成完全解析的结构。由于数据现在被组织成独立的块，您可以拥有第三个操作的多个实例，以便更好地利用计算机上的多个处理器。最后，其他线程将对这些完全解析的结构进行操作。注意：结合其中一些操作可能会更好，

于 2012-10-25T18:05:28.117 回答
0

它只有 15MB。我只是将整个东西吞入内存缓冲区，然后解析它。解析看起来像这样，大约：

#define DIGIT(c)((c) >= '0' && (c) <= '9')
while(*p == ' ') p++;
if (DIGIT(*p)){
    a = 0;
    while(DIGIT(*p){
        a *= 10; a += (*p++ - '0');
    }
}
// and so on...

您应该能够在睡梦中编写这种代码。

我不知道这是否比 快atoi，但它并没有大惊小怪地弄清楚数字的开始和结束位置。我会远离，scanf因为它要经过九码才能确定其格式字符串。

如果您在循环中运行整个事情 1000 次并获取一些堆栈样本，您应该会看到它花费了将近 100% 的时间来读取文件并生成输出（您没有提到）。你就是打不过那个。如果您确实看到在实际解析中花费了大量时间，则可能会进行重叠 I/O，但机器必须非常慢，或者 I/O 非常快（例如来自固态驱动器）在那之前是有道理的。

于 2012-10-25T19:44:49.180 回答