技术原理

【解题分享】zerojudge上的恶龙题- e307: 请让我留在你的回忆里,c++到底怎样读字串才快

今天做zerojudge练习时,
不小心做到一题看似简单的超可怕题,
题目分享: zerojudge- e307: 请让我留在你的回忆里

程式逻辑非常简单,
输入一行字串,
里面含有可输出的字元和「空白」,
中间的空白如果是偶数个就把它删除,
中间的空白如果是偶数个就保留一个,
例如:

input:□□□□M□□□□y□□□□□□□n□□am□□□□e□i□□s□□□□□□□Sa□□c□□h□□□□i□□. (为了看的比较清楚,空格用□表示)
output: My name is Sachi.

程式逻辑相当简单,但就是非常容易超时。
题目说输入的字串长度极长,大约10^8这幺长,
第一笔测资和第二笔测资完全相同,
第一笔测资的时限是0.2秒,
第二笔测资的时限是5秒,
目的是可以透过第二笔测资来验证自己的答案是否正确,
只是程式执行时间过长

总之就是要解到程式执行时间在0.2秒内才算过关

程式语言解题的选择(c++ or python)?

首先,小马判断python解应该不太可以,
因为python上读测资大概就input()一个函数,
实在想不到有什幺方法可以加速,
本题的精华几乎就是字串长度长,
很容易超时,
故选择速度较快的c++来攻略

首先,我觉得一次把整行字串读进来(比如说用getline)并不可行,
因为字串很长,读进来之后还是要用for迴圈遍历字串,
就会非常耗时

尝试一、单纯用getchar()读字元,用string存结果- 1.3秒 (超时)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string result;
    char c;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    while(1){
        c = getchar();
        if(c==EOF){
            break;
        }
        if(c!=' '){
            if(space){
                result += ' ';
                space = false;
            }
            result += c;
        }
        else{
            space = !space;
        }
    }
    cout << result <<endl;
}

尝试二、getchar()与putchar()- 1.7秒 (超时)

于是小马想说,那不要用string先把结果存起来呢?
每次读一个字元,不是空格的话就直接用putchar()输出,
结果似乎更慢了…

#include <iostream>
#include <string>
using namespace std;

int main() {
    char c;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    while(1){
        c = getchar();
        if(c==EOF){
            break;
        }
        if(c!=' '){
            if(space){
                putchar(' ');
                space = false;
            }
            putchar(c);
        }
        else{
            space = !space;
        }
    }
}

这边查询了一下参考资料,
查到这篇怎幺优化你的程式(C++篇)
讲到相当多c++的程式优化技巧,
其中提到可以用getchar_unlocked()/putchar_unlocked()来取代getchar()与putchar(),
速度上快很多(但不保证安全),
继续尝试过关…

尝试三、getchar_unlocked()读字元,用string存结果- 0.2秒 (刚好超时)

将getchar()换成getchar_unlocked(),发现速度上快很多,但还是刚好超时了

#include <iostream>
#include <string>
using namespace std;

int main() {
    string result;
    char c;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    while(1){
        c = getchar_unlocked();
        if(c==EOF){
            break;
        }
        if(c!=' '){
            if(space){
                result += ' ';
                space = false;
            }
            result += c;
        }
        else{
            space = !space;
        }
    }
    cout << result <<endl;
}

尝试四、getchar_unlocked()与putchar_unlocked()- 0.2秒 (还是刚好超时)

想到还可以尝试用getchar_unlocked()与putchar_unlocked()的组合,
速度上非常快了,但还是会刚好超时

#include <iostream>
#include <string>
using namespace std;

int main() {
    char c;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    while(1){
        c = getchar_unlocked();
        if(c==EOF){
            break;
        }
        if(c!=' '){
            if(space){
                putchar_unlocked(' ');
                space = false;
            }
            putchar_unlocked(c);
        }
        else{
            space = !space;
        }
    }
}

看来这一题真的比想像中的困难非常多,
时间上真的压的非常紧,
那篇文章有说fread()感觉比getchar()快,
实际把fread拿来取代getchar试试:

尝试五、fread_unlocked()与putchar_unlocked()- 0.2秒 (还是刚好超时)

必须说fread()的表现其实也很优秀,但还是过不了关

#include <string>

int main() {
    char c;
    bool space = false;
    int length;
    while(1){
        length = fread_unlocked(&c, 1 ,1,stdin); //一次读一个字
        if(length==0){
            break; //读不到时跳出迴圈
        }
        if(c!=' '){
            if(space){
                putchar_unlocked(' ');
                space = 0;
            }
            putchar_unlocked(c);
        }
        else{
            space = !space;
        }
    }
}

尝试六、华丽写法,组合cin和字串存结果- 2.8秒 (超时)

由「尝试一」到「尝试二」速度变慢发现,
会不会是一个个读字元和一个个输出字元速度在慢?
cin >> 字串的效果是有碰到空白的时候停下来,
如果平时用cin一次读很多字,
碰到空格再一个个慢慢读,速度会不会快一些呢,
小马又做了这样的尝试:

呃…并没有比较快,反而慢非常多,
getchar_unlocked(), putchar_unlocked()几乎是所能想到最快的方法了
真心觉得这题比leetcode还刁钻…

#include <iostream>
#include <string>
using namespace std;

int main() {
    string temp;
    string result;
    char c;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    while(cin >> temp){
        result += temp;
        while((c = getchar_unlocked())!=EOF){
            if(c!=' '){
                if(space){
                    result += ' ';
                    space = false;
                }
                result += c;
                break;
            }
            else{
                space = !space;
            }
        }
    }
    cout << result;
}

而且其实这个解法有点风险,如果测资在进入while((c = getchar_unlocked())!=EOF)之后,
读到不是空白的字元,跳出迴圈,
接着又马上碰到空白,
cin >> temp读测资,这样就会错掉

终于屠龙成功,尝试七- 一次性读进字串,处理完再一次输出- 0.1秒(AC)

经过了几乎一整天的奋斗,终于击败这一题了,
只能说这一题实在太恐怖,
还是google查了一下有没有别人解题成功的想法,
才知道原来别人是用fread_unlocked一口气把字串读进来,
处理完字串后再一口气输出字串,
一个一个读写的getchar_unlocked()putchar_unlocked()还是慢了一点点

另外,但是用fread_unlocked需要开字元阵列,
字元长度有10的8次方这幺大耶,
小马也很纳闷阵列真的可以开这幺大吗?
如果在main()里面写char result[100000000]是会报错的,
经研究,好像在函数内没办法开太大的阵列,
但是在全域变数的话就比较没关係

终于成功的程式码:

#include <stdio.h>
char s[100000000];
char result[100000000];

int main() {
    
    fread_unlocked(s,1,100000000,stdin);
    char *pc = result;
    bool space = false; //用来判断目前是偶数还是奇数个字元了
    for(int i=0;i<100000000;++i){
        if(s[i]!=' '){
            if(space){
                space = false;
                *pc++ = ' ';
            }
            *pc++ = s[i];
        }
        else{
            space = !space;
        }   
    }
    *pc = '\0'; //结束字元
    printf("%s", result);
}

python到底有没有机会过呢?

虽说终于屠龙成功了,
还是忍不住研究了一下python程式过不过的了

小马其实一开始没有想到好方法,
只觉得必须用for迴圈遍历字串,
那这样一定超时,
譬如说:

s = input()
name = ""
space = False
for c in s:
    if c!=' ':
        if space:
            name += ' '
            space = False
        name = name + c
    else:
        space = not space   
print(name)

因为python天生比较慢,c++的时限是

  • 第一笔测资0.2秒
  • 第二笔测资5秒

python放宽了三倍,时限是

  • 第一笔测资0.6秒
  • 第二笔测资15秒

小马用上述的解法,连15秒的时限都过不了,
所以原先是觉得python解应该是没救了,
后来查了一下,python的字串有好用的replace()函数

python解法- 0.5s (AC)

print(input().replace('  ', ''))

真的非常不可思议,在python里面只要写一行就过关了
(呃…那我一整个下午在干麻 @_@)

总之非常高兴又再度克服了一道难题,
解题过程相当发人深省,记录一下,也分享给大家参考

你也可能喜欢

发表评论

您的电子邮件地址不会被公开。 必填项已用 * 标注

提示:点击验证后方可评论!

插入图片
郑州人工智能编程培训 投稿者
我还没有学会写个人说明!
最近文章
  • * 没有更多文章了
  • 热门搜索

    分类目录