读取标准输入的 C++ 最快的 cin？

Question

我在 Linux 上使用 cachegrind 分析了一个计算量大的 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

我需要制作一个 Road每行中的整数。

另外请不要将输入重定向到我的程序到标准输入(myprogram < whatever_test_case.txt)。我不是在阅读特定文件。我刚从 cin 读到.

更新

使用 Slava's方法:

输入读取似乎花费更少的时间，但它仍然超时(可能不再是由于输入读取)。 Slava 的方法在 Road() ctor 中实现(从 main 向下 2 个)。所以现在它需要 22% 的时间而不是 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's方法

考虑解决

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

Answer 1

众所周知，流非常慢。不过，这并不奇怪——他们需要处理本地化、条件等。一种可能的解决方案是通过 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();
}

如果我了解您当前的比较器如何正常工作。