C++读取标准输入最快的cin方法是什么？

Question

我已经使用cachegrind在Linux上对一款计算密集型的C++程序进行了性能分析。令人惊讶的是，我的程序瓶颈不在任何排序或计算方法上...而是在读取输入时。

以下是cachegrind的截图，以防我误解性能分析器结果（请参见scanf()）：

我希望我的说法是正确的，scanf() 占用了 80.92% 的运行时间。

我使用 cin >> int_variable_here 来读取输入，就像这样：

std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities;
cin >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];

for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;    

    cin >> cityA;
    //scanf("%d", &cityA);    // scanf() and cin are both too slow
    cin >> cityB;
    //scanf("%d", &cityB);
    cin >> length;
    //scanf("%d", &length);

    Roads[i] = Road(cityA, cityB, length);
}

如果您没有发现这个输入读取代码的任何问题，能否推荐一种更快的读取输入的方法？我正在考虑尝试getline()（在等待响应时进行尝试）。我的猜测是getline()可能会更快，因为它需要做更少的转换并且解析流的总次数较少（只是我的猜测，但最终我也必须将字符串解析为整数）。

我所说的“太慢”是指，这是一个更大的作业任务的一部分，在一定时间后会超时（我认为是90秒）。我非常有信心瓶颈在这里，因为我故意注释掉了程序的其他主要部分，它仍然超时。我不知道教练运行我的程序的测试用例是什么，但它肯定是一个巨大的输入文件。那么，我可以使用什么方法来最快地读取输入？

输入格式很严格：每行3个以空格分隔的整数，有多行：

示例输入：

7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16

我需要在每行整数中制作一条道路。

另请注意，输入被重定向到我的程序的标准输入（myprogram < whatever_test_case.txt）。我没有读取特定的文件。我只是从cin读取。

更新

使用 Slava的方法：

输入读取似乎需要更少的时间，但仍然超时（可能不再是由于输入读取）。Slava的方法已经实现在Road() ctor（从main开始往下数2个）。所以现在它只需要80%的时间。我正在考虑优化SortRoadsComparator()，因为它被调用了26,000,000次。

比较器代码：

// The complexity is sort of required for the whole min() max(), based off assignment instructions
bool SortRoadsComparator(const Road& a, const Road& b)
{
    if (a.Length > b.Length) 
        return false;

    else if (b.Length > a.Length) 
        return true;

    else
    {
        // Non-determinism case
        return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) ||
            (
            (min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB)                                     
            )
            );
    }
}

使用 enhzflep的方法

问题已解决

我认为这个问题已经解决了，因为瓶颈不再是读取输入。对于我来说，Slava的方法是最快的。

- Jason

---

在你的情况下，cin 就是一个文件。如果您想要查看scanf是否真的成为瓶颈，那么您应该从内存中读取（即，事先将整个文件读入内存，并在分析数据时忽略它）。 - vanza

我会尝试这个。我将使用 getline(cin, string, EOF) 的重载版本，它应该一次性读取所有内容。我将首先按 \n 分割以分隔每行，然后按 分割每行以获取每个整数。这听起来高效吗？ - Jason

扫描300万个数字？应该在一秒内完成。如果速度慢，可以使用二进制格式。 - Öö Tiib

我会先尝试逐行读取文件，我敢打赌这样足够快。 - Slava

如果你只是写了一个带有三个 cin 的 for 循环（没有 roads[i] = ... 和程序中的其他内容），那么需要多长时间？ - Shahbaz

Answer 1

流式处理在IT技术中被广泛使用，但其速度较慢并不意外-需要处理本地化、条件等。一种可能的解决方案是通过std::getline(std::cin, str)逐行读取文件，并通过类似以下代码将字符串转换为数字：

std::vector<int> getNumbers( const std::string &str )
{
   std::vector<int> res;
   int value = 0;
   bool gotValue = false;
   for( int i = 0; i < str.length(); ++i ) {
      if( str[i] == ' ' ) {
         if( gotValue ) res.push_back( value );
         value = 0;
         gotValue = false;
         continue;
      }
      value = value * 10 + str[i] - '0';
      gotValue = true;
   }
   if( gotValue ) res.push_back( value );
   return res;
}

我没有测试这段代码，只是为了展示这个想法而写。我假设你不希望输入除了空格和数字之外的任何内容，因此它不会验证输入。

要优化排序，首先应该检查是否真的需要对整个序列进行排序。对于比较器，我会编写getMin() getMax()方法，并将这些值存储在对象中（不必每次都计算）：

bool SortRoadsComparator(const Road& a, const Road& b)
{
    if( a.Length != b.Length ) return a.Length < b.length;
    if( a.getMin() != b.getMin() ) return a.getMin() < b.getMin();
    return a.getMax() < b.getMax();
}

如果我正确理解了您当前比较器的工作原理。

- Slava

---

@Jason：也许可以使用strtol，但绝对不要使用atoi，因为后者使得错误检查变得太容易被忽略，而实现起来又太困难。 - John Zwinck

使用atoi需要将字符串分割为数字，这是扫描的过程。而且atoi也不是世界上最快的函数。但在你的情况下，我认为你无法检测到差异，你可以使用atoi或strtol如果更容易一些。 - Slava

你确定需要对整个序列进行排序吗？ - Slava

在SortRoadsComparator()中，你看到的a.CityA，我使用它作为min(a.CityA, b.CityB)等等，CityA和CityB实际上是int类型，所以所有的min和max应该都是O（1）（只是很多比较）。 - Jason

你能试试我的变体，看看它是否会影响到任何东西吗？ - Slava

Answer 2

正如Slava所说，流（即cin）在性能（和可执行文件大小）方面非常低效。

考虑以下两个方法：

start = clock();
std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];
for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;
    cin >> cityA >> cityB >> length;
    Roads[i] = Road(cityA, cityB, length);
}
stop = clock();
printf ("time: %d\n", stop-start);

并且

start = clock();
fp = stdin;
fscanf(fp, "%d\n%d\n", &NumberOfCities, &NumberOfOldRoads);
Roads = new Road[NumberOfOldRoads];
for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;
    fscanf(fp, "%d %d %d\n", &cityA, &cityB, &length);
    Roads[i] = Road(cityA, cityB, length);
}
stop = clock();
printf ("time: %d\n", stop-start);

运行每种方式5次(使用包含1,000,000个条目和前两个'控制'行的输入文件)会给我们以下结果：

1. 使用没有与stdio同步的方向的cin: 8291、8501、8720、8918、7164 (平均8318.3)

2. 使用有与stdio同步的方向的cin: 4875、4674、4921、4782、5171 (平均4884.6)

3. 使用fscanf: 1681、1676、1536、1644、1675 (平均1642.4)

因此，可以明显地看到，sync_with_stdio(false)方向确实有所帮助。可以看到，fscanf比使用cin的任何方法都要快。事实上，fscanf的方法几乎比cin的最佳方法快3倍，比没有告知避免与stdio同步时要快5倍。

- enhzflep

---

嗯，看起来速度变慢了？相对于 Slava 的方法的 22%，程序总运行时间的 42% 被花费了。 - Jason

@Jason - 嗯。我没有尝试过Slava的代码 - 只是坚持我熟悉的东西。看来我有新的东西要熟悉了。谢谢反馈！ :) - enhzflep

非常感谢您写下这篇文章。我测试的方式与您发布的几乎完全一样。我确认它确实有效，只是在我的应用程序中似乎不太快。这可能意味着在大多数情况下您的代码更快，而我的情况则比较奇怪（或者说方法有些奇怪）。您的基准测试比我的特殊图表更有说服力。再次感谢！ - Jason

当然我的代码应该更快。但这并不意味着它更好。一方面，iostream、sscanf、strtol等更通用的解决方案，另一方面，它们必须检查其输入。正如我所提到的，如果您确定输入正确且仅包含正整数，则我的函数将更快地工作，因为它高度专门化于此特定情况，并且不验证输入。 - Slava

Answer 3

inline void S( int x ) {
x=0;
while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF) ch=getchar_unlocked();
if (ch=='-')
sign=-1 , ch=getchar_unlocked();
    else
sign=1;
do
x = (x<<3) + (x<<1) + ch-'0';
while((ch=getchar_unlocked())>='0' && ch<='9');
x*=sign;
}

你可以使用此函数来处理任何类型的数字输入，只需更改参数类型。 这将比标准scanf运行得更快。

如果你想节省更多时间，最好使用fread()和fwrite()，但在这种情况下，你必须自己操作输入。 为了节省时间，你应该使用fread()一次从标准输入流中读取大块数据。这将减少I/O调用的数量，因此你将看到时间上的大差异。

- Aditya Kumar