C和C++中几乎完全相同的代码之间的执行时间差异很大(x9)

我试图从www.spoj.com解决这个练习:FCTRL - Factorial

你真的不必阅读它,只要你好奇就去做:)

首先我用C++实现它(这是我的解决方案):

#include 
using namespace std;

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from /sf/ask/17360801/)

    cin >> num_of_inputs;

    while (num_of_inputs--)
    {
        cin >> fact_num;

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        cout << num_of_trailing_zeros << "\n";
    }

    return 0;
}

我上传它作为g ++ 5.1的解决方案

结果是:时间 0.18 Mem 3.3M

但后来我看到一些评论声称他们的时间执行不到0.1.由于我无法考虑更快的算法,我试图在C中实现相同的代码:

#include 

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    scanf("%d", &num_of_inputs);

    while (num_of_inputs--)
    {
        scanf("%d", &fact_num);

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        printf("%d", num_of_trailing_zeros);
        printf("%s","\n");
    }

    return 0;
}

我上传它作为gcc 5.1的解决方案

这次的结果是:时间 0.02 Mem 2.1M

现在代码几乎相同,我添加std::ios_base::sync_with_stdio(false);到C++代码中,这里建议关闭与C库的stdio缓冲区的同步.我也拆printf("%d\n", num_of_trailing_zeros);到printf("%d", num_of_trailing_zeros); printf("%s","\n");以补偿的双呼叫operator<<在cout << num_of_trailing_zeros << "\n";.

但我仍然看到在C与C++代码中x9性能更好,内存使用率更低.

这是为什么？

编辑

我固定unsigned long到unsigned int在C代码.它应该是,unsigned int并且上面显示的结果与new(unsigned int)版本有关.

1> chqrlie..：

---

两个程序完全相同.它们使用相同的精确算法,并且由于其低复杂性,它们的性能主要与输入和输出处理的效率有关.

无论如何,scanf("%d", &fact_num);在一侧和另一侧扫描输入cin >> fact_num;似乎并不昂贵.事实上,它在C++中的成本应该更低,因为转换类型在编译时是已知的,并且正确的解析器可以由C++编译器直接调用.输出也是如此.你甚至为单独的调用写了一点printf("%s","\n");,但C编译器足以将其编译为调用putchar('\n');.

因此,考虑到I/O和计算的复杂性,C++版本应该比C版本更快.

完全禁用缓冲stdout会将C实现减慢到比C++版本更慢的速度.AlexLop fflush(stdout);在最后一次测试后的另一项测试printf产生与C++版本类似的性能.它没有完全禁用缓冲那么慢,因为输出以小块而不是一次一个字节写入系统.

这似乎指向C++库中的特定行为:我怀疑系统的实现cin和cout刷新输出到cout请求输入时cin.一些C库也这样做,但通常只在读/写终端时才这样做.www.spoj.com网站完成的基准测试可能会重定向文件的输入和输出.

AlexLop做了另一个测试:在向量中一次读取所有输入,然后计算和编写所有输出有助于理解为什么C++版本要慢得多.它将性能提升到C版本的性能,这证明了我的观点并消除了对C++格式代码的怀疑.

Blastfurnace的另一项测试,将所有输出存储在一个std::ostringstream并在最后一次冲洗中,确实将C++性能提高到基本C版本的性能.QED.

隔行扫描输入cin和输出cout似乎导致非常低效的I/O处理,从而破坏了流缓冲方案.将性能降低10倍.

PS:你的算法不正确,fact_num >= UINT_MAX / 5因为它fives *= 5会溢出并在它变成之前回绕> fact_num.您可以通过纠正此fives一unsigned long或unsigned long long如果这些类型之一大于unsigned int.也%u用作scanf格式.你很幸运www.spoj.com的人在他们的基准测试中并不是太严格.

编辑:正如后来由vitaux解释的那样,这种行为确实是由C++标准强制执行的. 默认cin绑定cout.cin输入缓冲区需要重新填充的输入操作将导致cout刷新挂起的输出.在OP的实现中,cin似乎cout系统地冲洗,这有点矫枉过正,效率明显低下.

伊利亚·波波夫为此提供了一个简单的解决方案:除了以下之外,cin还可以cout通过施放另一个魔法咒语来解开std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

另请注意,在使用std::endl而不是'\n'生成行尾时,也会发生强制刷新cout.将输出行更改为更多C++惯用和无辜的外观cout << num_of_trailing_zeros << endl;会以相同的方式降低性能.

---

你可能对流冲洗是正确的.在`std :: ostringstream`中收集输出并在结束时输出一次将时间缩短到与C版本相同.

---

@DavidC.Rankin:我冒了一个猜想(cout在阅读cin时脸红了),设计了一种证明它的方法,AlexLop实现了它并且确实提供了令人信服的证据,但是Blastfurnace提出了一种不同的方式来证明我的观点和他的测试给出同样令人信服的证据.我把它作为证据,但当然这不是一个完全正式的证明,看看C++源代码可以.

---

我尝试使用`ostringstream`作为输出,它给了*Time*0.02 QED :).关于`fact_num> = UINT_MAX/5`,GOOD点!

---

一个更简单的修复即使`sizeof(int)== sizeof(long long)`也是这样的:在`num_of_trailing_zeros + = fact_num/fives;`​​之后在循环体中添加一个测试来检查是否已达到`fives`最大值:`if(fives> UINT_MAX/5)break;`

2> Ilya Popov..：

---

iostream当你使用两者cin并且cout要打电话时,另一个让你更快的技巧

cin.tie(nullptr);

默认情况下,当您输入任何内容时cin,它会刷新cout.如果进行交错输入和输出,则会严重损害性能.这是为命令行界面使用完成的,在那里显示一些提示然后等待数据:

std::string name;
cout << "Enter your name:";
cin >> name;

在这种情况下,您需要确保在开始等待输入之前实际显示提示.通过上面的一行你可以打破这种关系,cin并cout变得独立.

从C++ 11开始,使用iostream实现更好性能的另一种方法是与之std::getline一起使用std::stoi,如下所示:

std::string line;
for (int i = 0; i < n && std::getline(std::cin, line); ++i)
{
    int x = std::stoi(line);
}

这种方式可以接近C风格的性能,甚至超越scanf.使用getchar并特别是getchar_unlocked与手写解析一起使用仍可提供更好的性能.

PS.我写了一篇文章,比较了几种用C++输入数字的方法,这对于在线评委很有用,但是只有俄语,对不起.但是,代码示例和最终表应该是可以理解的.

3> vitaut..：

---

问题是,引用cppreference:

来自std :: cin的任何输入,输出到std :: cerr,或程序终止强制调用std :: cout.flush()

这很容易测试:如果你更换

cin >> fact_num;

同

scanf("%d", &fact_num);

同样cin >> num_of_inputs但是cout你会在C++版本(或者说IOStream版本)中获得与C一样的相同性能:

如果你保持cin但更换也会发生同样的情况

cout << num_of_trailing_zeros << "\n";

同

printf("%d", num_of_trailing_zeros);
printf("%s","\n");

一个简单的解决方案是解开cout并且cin如Ilya Popov所提到的:

cin.tie(nullptr);

在某些情况下,允许标准库实现省略对flush的调用,但并非总是如此.这是C++ 14 27.7.2.1.3的引用(感谢chqrlie):

class basic_istream :: sentry:首先,如果is.tie()不是空指针,则函数调用is.tie() - > flush()以使输出序列与任何关联的外部C流同步.除非is.tie()的put区域为空,否则可以抑制此调用.此外,允许实现将调用推迟到刷新,直到发生is.rdbuf() - > underflow()的调用.如果在销毁哨兵对象之前没有发生此类调用,则可以完全取消对flush的调用.