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

你真的不必读它,如果你好奇的话就go 读:)

首先,我在C++中实现了它(以下是我的解决方案):

#include <iostream>
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 https://stackoverflow.com/a/22225421/5218277)

    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的解决方案

结果是:Time0.18Mem3.3M

但后来我看到一些 comments ,声称他们的执行时间小于0.1.因为我想不出更快的算法,所以我try 在C中实现相同的代码:

#include <stdio.h>

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的解决方案

这次的成绩是:Time 0.02 Mem 2.1米 C execution results

现在代码是almost the same,我按照建议的herestd::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");,以补偿cout << num_of_trailing_zeros << "\n";operator<<的双重调用.

但是我仍然看到C和C++代码中内存使用率低x9 better performance.

为什么?

EDIT

我在C代码中将unsigned long改为unsigned int.它应该是unsigned int,上面显示的结果与新(unsigned int)版本相关.

推荐答案

两个程序做的事情完全相同.它们使用相同的精确算法,并且考虑到其低复杂性,它们的性能主要取决于输入和输出处理的效率.

无论哪种方式,一边扫描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++库中的特定行为:我怀疑当您请求输入时,系统cincout的实现将输出刷新为cout.有些C库也会这样做,但通常只有在读写终端时才会这样做.由www.spoj进行的基准测试.com站点可能会重定向文件的输入和输出.

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

Blastfurnace的另一个测试,将所有输出存储在std::ostringstream,并在最后一次爆破中刷新,这确实提高了C++基本版本的性能.QED.

cincout的交错输入和输出似乎会导致非常低效的I/O处理,从而 destruct 流缓冲方案.将性能降低10倍.

PS:你的算法对于fact_num >= UINT_MAX / 5是不正确的,因为fives *= 5会在变成> fact_num之前溢出并环绕.如果这些类型中的一个大于unsigned int,可以通过将fives设为unsigned longunsigned long long来纠正这一点.也使用%u作为scanf格式.你很幸运www.spoj上的人.com在基准测试方面并不太严格.

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

伊利亚·波波夫为这个问题提供了一个简单的解决方案:除了std::ios_base::sync_with_stdio(false);外,还可以通过施放另一个魔法咒语将cincout解开:

cin.tie(nullptr);

还要注意,当使用std::endl而不是'\n'cout上产生行尾时,也会发生这种强制转储清除.将输出行更改为更多的C++习惯用法和更纯真的cout << num_of_trailing_zeros << endl;看起来也会以同样的方式降低性能.

C++相关问答推荐

为什么我得到更多的256假阳性在PKZIP解密密钥验证?

为什么可以通过指向常量int的指针间接地改变整数的值?

不会停在空格或换行符上的错误

带有sigLongjMP中断I/O的异常处理程序

在我的代码中,我需要在哪里编写输出函数?

是什么让numpy.sum比优化的(自动矢量化的)C循环更快?

平均程序编译,但结果不好

什么是.c.h文件?

在创建动态泛型数组时,通过realloc对故障进行分段

在句子中转换单词的问题

如何在POSIX-UEFI中获得输入?

将回调/基于事件的C API转换为非回调API

从BIOS(8086)中读取刻度需要多少?

为什么我的旧式&q;函数在传递浮点数时会打印2?

赋值两侧的后置增量,字符指针

在C中,为什么这个带有递增整数的main函数从不因溢出而崩溃?

如何在Rust中处理C的longjmp情况?

通过修改c中的合并排序对数组的偶数索引进行排序

uint64_t:四舍五入除法

有没有一种方法可以减少舍入误差?