6

我已经使用 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

我需要Road从每一行中的整数中取出一个。

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

更新

使用Slava 的方法：

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

在此处输入图像描述

考虑解决

我将考虑解决这个问题，因为瓶颈不再是读取输入。Slava 的方法对我来说是最快的。

4

3 回答 3

4

流很清楚很慢。不过这并不令人意外——他们需要处理本地化、条件等。一种可能的解决方案是逐行读取文件 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();
}

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

于 2013-02-23T04:07:46.673 回答
3

正如 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 个条目 + 前 2 个“控制”行）给我们以下结果：

  1. 使用没有方向的cin与 stdio 8291、8501、8720、8918、7164（平均 8318.3）不同步

  2. 使用 cin的方向与 stdio 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 同步的情况下比 cin快 5 倍。

于 2013-02-23T05:30:43.870 回答
1 
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;
}

您可以将此功能用于任何类型的数字输入，只需更改参数类型。这将比 std scanf 运行得更快。

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

于 2013-02-23T04:29:04.343 回答