我试图从www.spoj.com解决这个练习:FCTRL - Factorial
你真的不必阅读它,只要你好奇就去做:)
首先我用C++实现它(这是我的解决方案):
#includeusing 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中实现相同的代码:
#includeint 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
)版本有关.
两个程序完全相同.它们使用相同的精确算法,并且由于其低复杂性,它们的性能主要与输入和输出处理的效率有关.
无论如何,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;
会以相同的方式降低性能.
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++输入数字的方法,这对于在线评委很有用,但是只有俄语,对不起.但是,代码示例和最终表应该是可以理解的.
问题是,引用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的调用.