-2

(ええと、私の英語はよくありません) :)

私の友人は現在 C++ を学んでいて、私が理由を説明できない問題を見つけました。

最初のコード、それは 2000MS 以上を実行します

#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;
}

3番目のコードは、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;
}

最後のコード、それは 515MS を実行します

#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の場合

ということで、理由は約2番目のforループです。

そして、私の質問は、なぜ「strlen」関数と for ループの出力によってコードが非常に遅くなるのかということです。

4

2 に答える 2

0

関数は、strlenループ内にあるときにループを通過するたびに実行する必要があります。これは余分な関数呼び出しであり、文字列全体を調べてその長さを見つける必要があります。

で長さをキャッシュsizeするということは、ループを通過するたびにその長さをやり直す必要がないことを意味します。

したがって、エラーはありません。これは予想される動作です。

于 2013-01-21T06:24:07.740 に答える
0

strlenループ条件 ( 200 万回の反復によるループ) を記述することで、2 メガバイトの文字列を 200 万回スキャンすることになります。もちろん、それには時間がかかります！

文字列の長さを一度だけ事前に計算すると、その遅延は解消されます。

また、コンソールへの 2MB のテキストのストリーミングは、どのような場合でも著しく「遅い」ことに気付くでしょう。

于 2013-01-21T06:24:40.627 に答える