iT邦幫忙

2

【解題分享】zerojudge上的惡龍題- e307: 請讓我留在你的回憶裡,c++到底怎樣讀字串才快

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裡面只要寫一行就過關了
(呃…那我一整個下午在幹麻 @_@)

總之非常高興又再度克服了一道難題,
解題過程相當發人深省,記錄一下,也分享給大家參考


1 則留言

1
screenleon
iT邦新手 4 級 ‧ 2020-05-21 09:34:32

中間的空白如果是偶數個就把它刪除, 中間的空白如果是偶數個就保留一個,

所以偶數空白要保留還是刪除/images/emoticon/emoticon06.gif

心原一馬 iT邦研究生 5 級 ‧ 2020-05-21 12:29:05 檢舉

抱歉,小馬又筆誤了,應該是
中間的空白如果是偶數個就把它刪除, 中間的空白如果是「奇數個」就保留一個,

我要留言

立即登入留言