我已经写了一个程序来计算一个由8个字符组成的字符串 "sharjeel" 的排列。
#include <iostream>
#include <time.h>
char string[] = "sharjeel";
int len = 8;
int count = 0;
void swap(char& a, char& b){
char t = a;
a = b;
b = t;
}
void permute(int pos) {
if(pos==len-1){
std::cout << ++count << "\t" << string << std::endl;
return;
}
else {
for (int i = pos; i < len;i++)
{
swap(string[i], string[pos]);
permute(pos + 1);
swap(string[i], string[pos]);
}
}
}
int main(){
clock_t start = clock();
permute(0);
std::cout << "Permutations: " << count << std::endl;
std::cout << "Time taken: " << (double)(clock() - start) / (double)CLOCKS_PER_SEC << std::endl;
return 1;
}
如果我在打印每个排列的同时,执行完成需要约9.8秒。
40314 lshaerej
40315 lshareej
40316 lshareje
40317 lshareej
40318 lshareje
40319 lsharjee
40320 lsharjee
Permutations: 40320
Time taken: 9.815
现在,如果我替换掉这行代码:
std::cout << ++count << "\t" << string << std::endl;
使用这个:
++count;
重新编译后,输出为:
Permutations: 40320
Time taken: 0.001
再次运行:
Permutations: 40320
Time taken: 0.002
使用g++编译并使用-O3参数进行优化。
为什么std::cout的耗时相对较长?有没有更快的打印方式?
编辑:制作了一个C#版本的程序。
/*
* Permutations
* in c#
* much faster than the c++ version
*/
using System;
using System.Diagnostics;
namespace Permutation_C
{
class MainClass
{
private static uint len;
private static char[] input;
private static int count = 0;
public static void Main (string[] args)
{
Console.Write ("Enter a string to permute: ");
input = Console.ReadLine ().ToCharArray();
len = Convert.ToUInt32(input.Length);
Stopwatch clock = Stopwatch.StartNew();
permute (0u);
Console.WriteLine("Time Taken: {0} seconds", clock.ElapsedMilliseconds/1000.0);
}
static void permute(uint pos)
{
if (pos == len - 1u) {
Console.WriteLine ("{0}.\t{1}",++count, new string(input));
return;
} else {
for (uint i = pos; i < len; i++) {
swap (Convert.ToInt32(i),Convert.ToInt32(pos));
permute (pos + 1);
swap (Convert.ToInt32(i),Convert.ToInt32(pos));
}
}
}
static void swap(int a, int b) {
char t = input[a];
input[a] = input[b];
input[b] = t;
}
}
}
输出:
40313. lshaerje
40314. lshaerej
40315. lshareej
40316. lshareje
40317. lshareej
40318. lshareje
40319. lsharjee
40320. lsharjee
Time Taken: 4.628 seconds
Press any key to continue . . .
从这里来看,与std::cout的结果相比,Console.WriteLine()似乎快了将近一倍。是什么在拖慢std::cout的速度?
'\n'
而不是std::endl
。尽管如答案所述,仍会变慢,但您可能会观察到加速。 - juanchopanzastd::ios_base::sync_with_stdio
禁用printf
和std::cout
之间的同步。 - François Andrieuxstd::endl
- 使用\n
代替即可。 - Jesper Juhl