-2

（嗯，我的英语不好）:)

我的朋友现在正在学习 C++，他发现了一个我无法解释原因的问题。

第一个代码，运行时间超过 2000 毫秒

#include <cstdlib>
#include <cstdio> 
#include <cstring>

using namespace std;

int ans[2000000];
char a[2000000];

int main()
{
    scanf("%s\n",a);
    int l=1,r=strlen(a);
    for (int i=0;i<strlen(a);i++) 
        if (a[i]=='l')
            ans[r--] = i+1;
        else
            ans[l++] = i+1;
    for (int i=1;i<=strlen(a);i++)
        printf("%d\n",ans[i]);
    return 0;
}

第二个代码，它运行465MS

#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int ans[2000000];
char a[2000000];
int size;

int main()
{
    scanf("%s",a);
    int l=1,r=strlen(a);
    size = r;
    for (int i=0;i<strlen(a);i++) 
        if (a[i]=='l') ans[r--]=i+1;else ans[l++]=i+1;
    for (int i=1;i<=size;i++)
        printf("%d\n",ans[i]);
    return 0;
}

第三个代码，运行时间超过2000MS

#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int ans[2000000];
char a[2000000];
int size;

int main()
{
    scanf("%s",a);
    int l=1,r=strlen(a);
    size = r;
    for (int i=0;i<size;i++) 
        if (a[i]=='l') ans[r--]=i+1;else ans[l++]=i+1;
    for (int i=1;i<=strlen(a);i++)
        printf("%d\n",ans[i]);
    return 0;
}

最后的代码，它运行 515 毫秒

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;

int ans[2000000];
string a;

int main()
{
cin >>a;
    int l=1,r=a.size();
    for (int i=0;i<a.size();i++) 
        if (a[i]=='l') ans[r--]=i+1;else ans[l++]=i+1;
    for (int i=1;i<=a.size();i++)
        printf("%d\n",ans[i]);
    return 0;
}

当输入字符串大小为 10^5 时

所以，原因是关于第二个 for 循环。

我的问题是为什么“strlen”函数和for循环中的打印会使代码这么慢？

4

2 回答 2

0

当您在循环中使用该strlen函数时，每次都必须通过循环执行该函数。这是一个额外的函数调用，它必须遍历整个字符串才能找到它的长度。

将长度缓存在size, 意味着每次循环都不必重做。

所以，没有错误。这是预期的行为。

于 2013-01-21T06:24:07.740 回答
0

strlen通过在循环条件中写入——一个有200 万次迭代的循环——你正在扫描一个 2MB 的字符串 200 万次。当然，这需要一些时间！

当您只预先计算一次字符串长度时，这种延迟就会消失。

此外，您可能会发现在任何情况下将 2MB 的文本流式传输到控制台都会明显“慢”。

于 2013-01-21T06:24:40.627 回答