laxiflora的小天地

前進軟體工程師的練功之路

0%

在一個美好的coding日,你希望可以從stdin中讀取一個數字以及一個字元,於是你寫了下面這段code:

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <stdlib.h>

int main(void){
int a=0;
char c='-';
scanf("%d%c",&a,&c);
printf("|%d %c|", a, c);
return 0;
}

並輸入了32\nX做為測試(‘\n’代指換行),卻發現他的輸出不是|32 X|,而是|32 \n|

發生了甚麼事

因為scanf(“%c”)在執行期間會「無條件」吃下下一個字元並返回,而scanf(“%d”)也不會將使他中斷讀取的字元移出stream,造成scanf(“%c”)吃到原本要讓%d中斷的字(也就是’\n’)

幾種可行的解決方法

  1. 告訴scanf省略掉下一個垃圾字元再做%c:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <stdio.h>
    #include <stdlib.h>

    int main(void){
    int a=0;
    char c='-';
    scanf("%d %c",&a,&c);
    printf("|%d %c|", a, c);
    return 0;
    }
  2. 用一個空的scanf(“%c”)吸收掉垃圾字元:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <stdio.h>
    #include <stdlib.h>

    int main(void){
    int a=0;
    char c='-';
    scanf("%d",&a);
    scanf("%c", &c);
    scanf("%c", &c);
    printf("|%d %c|", a, c);
    return 0;
    }
  3. 用一個空的其他function吸收掉垃圾字元:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <stdio.h>
    #include <stdlib.h>

    int main(void){
    int a=0;
    char c='-';
    scanf("%d",&a);
    fgetc(stdin);
    scanf("%c", &c);
    printf("|%d %c|", a, c);
    return 0;
    }

scanf的行為

scanf在看到不同的conversion format,會有不同的反應,而正是這些處理方法的不同導致了奇怪的結果產生。下面分別討論scanf %d跟%c的反應:

scanf(“%d”)

  • 在看到%d時,scanf會略過所有的換行/空白字元,直至碰到第一個非換行/空白字元才開始讀取,並讀取直到碰到下一個非數字字元、換行/空白字元並結束,並留下使他結束讀取的那個字元在stream;

  • 如果碰到的第一個非換行/空白字元不是數字(範例2),scanf函數**會整個結束掉(包括後續的讀取)**,且不會設置errno(perror出來是Success)

  • 範例1 :現在input stream裡面有"\n\n 32X \n",則scanf(“%d”)以後他會讀取到32這個數字,input stream剩下"X \n" (前面的”\n\n”被無視且吃掉了)

  • 範例2 :現在input stream裡面有"\n XD\n \n",則scanf(“%d%c”)以後他會在讀到’X’的時候發生錯誤,直接結束整行的scanf(%c也會因此讀不到東西),此時的input stream剩下"XD\n \n"

scanf(“%c”)

  • 在看到%c時,scanf會「無條件」吃下下一個位元並返回(不管是’ ‘還是’\n’或是’\r\n’)

  • 常常是吃到垃圾字的受害者

小測試

  • 如果我們輸入”32X\n”,在一開始的程式碼也會成功喔!

在C++傳遞二維VLA的難題

在寫某題leetcode時,碰到了需要宣告2維陣列,且陣列大小是變數的狀況。因為自己本身習慣使用VLA(variable-length arrays),所以理所當然的宣告了二維陣列,並將他丟入函式處理,格式如下

1
2
3
4
5
6
void foo(int y_axis, bool map[][y_axis]){
...
}

bool map[x_axis][y_axis];
foo(y_axis, map)

值得注意的是,如果把argument map放在y_axis前面的話,會造成編譯器先看到map然後無法解讀y_axis (未宣告的變數)

這個方法在C中行得通,然而在C++會跳出錯誤訊息:

1
2
error: use of parameter outside function body before ‘]’ token
3 | void foo(int n, int array[][n]){

若是把map改成bool**作為參數,則會:

1
2
3
4
void foo(int y_axis, bool** map){

error: cannot convert ‘int (*)[n]’ to ‘int**’
11 | foo(n, array);

但如果陣列的大小是常數,卻可以編譯通過

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

void foo(int n, int (*array)[3]){
return;
}

int main(void){
int m, n;
std::cin>>m>>n;
int array[2][3];
foo(n, array);


}

看來問題出在C++中,多維陣列的local宣告不可用變數作為參數(VLA)

嗯? 你說你在C++可以用int array[m][n];宣告成功並使用,只是不能丟入函數? 這其實只是編譯器給你行方便而已,GPT給出了回答:

1
2
3
4
5
C++ does not support variable-length arrays (VLA) as a language feature, unlike C99 which introduced VLAs as a standard feature. However, some C++ compilers may offer support for VLAs as an extension, allowing you to declare and use them in your code.

The ability to declare a VLA 2D array like int array[m][n] in C++ may be possible because some C++ compilers may allow it as an extension to the language. However, the behavior of such extensions can vary between different compilers, and they may not be portable across different platforms or architectures.

It's important to note that relying on such extensions may not be the best approach for writing portable and maintainable C++ code. Instead, it's recommended to use alternative approaches for dynamically allocating memory, such as using the std::vector container or dynamic memory allocation with the new and delete operators. These approaches provide more portable and flexible solutions for dynamically allocating memory in C++.

解決方法

C++相對於把動態變換大小的資料存放在stack,更鼓勵將資料放在heap中,方法是透過vector STL或是new pointer:

C++中vector元素的存放位置是heap,push_back元素時實際上new了一個新object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 用new的
int** a = new int*[x_axis];
for(int i = 0; i < x_axis; ++i)
a[i] = new int[y_axis];


// 用vector,因為vector是動態延展大小,所以這裡包含了輸入
vector< vector<int> > a;
for(int i=0;i<x_axis;i++){
vector<int> newRow;
for(int j=0;j<y_axis;j++){
int input;
cin>>input;
newRow.push_back(input);
}
a.push_back(newRow);
}

為什麼會這樣

這裡給出了解釋,大致是說如果直接宣告的話,第一可能有stack overflow的風險(將stack allocation交由輸入者決定是危險的),第二則是對於編譯器實作會有額外的負擔,必須在run time才能知道stack要被allocate多少大小

當然,這也有一定的trade-off,如果我們將資料放在heap中,相比於記憶體地址連續的stack,或多或少會傷害到cache performance(當然還是要看CPU的實作),且要allocate in stack只要延伸sp指的位置就好,不像new還要跟記憶體互動

不過,傳統的C99是允許VLA的,現今常見的編譯器(gcc, clang等)都有支援基本的VLA,但要注意的是這不是C++的standard,而是來自於編譯器的extention,將C++的宣告方法轉成C風格、支援VLA的格式

結論

如果要用C++寫程式,就善用STL容器吧。

C++與C對於相同的概念,有不同的實作方式:C++希望設計師使用他們提供的解方(STL)來解決問題;C則更相信程式設計師知道自己在幹嘛(有stack overflow的風險),但提供自由與看似方便的宣告方法的背後,就是程式莫名崩潰的風險。

別被C允許VLA的開發方式慣壞了,為了讓程式更安全並兼顧速度,根據使用狀況判斷使用heap還是stack來存放資料是好習慣

這篇文主要想要強調的就是,char*作為一個指標,紀錄的是記憶體位址,若指向的記憶體地址沒有被分配,是不可以直接用strcpy的

char[]其實就是一個數組,雖然看似跟char*一樣,但兩者的邏輯不同

char[]

char a[] = "KKK" 其實等同於char a[] = {'K','K','K','\0'}
如果用vs code滑上去看,會發現它其實就是char a[4]

這類型的變數在宣告時就必須給定字元,且後續長度不可修改。

即,不能用char a[] = "KKK"; a = "KKKKK";

這時候它的操作等同於char[n],要改變其中任意「字元」都是可行的(此變數已經作為array被分配在stack中)
但當然如果把最後的’\0’換成其他字元,printf("%s")會印出奇怪的東西

至於char* argv[],同理其實只是等同於char* argv[n] = {'string1','string2',...}而已

要注意的是不可以直接把整個array改成其他字串,在C語言規範中arrays並非modifiable l-values

如果要修改這類的char陣列,須使用strcpy (用malloc/new出來的char array同理)

這類char陣列的size是根據字元數變動的

char*

顧名思義,他其實是字元指標,指向某個字串常數的指標。

C/C++的常數字串儲存方法是為這些字串開一個空間存放他們,當宣告

1
char* A = "hey";

時,其實就是為hey這個字串分配一個空的記憶體位置,並且將A指向這個地址。

也就是說,如果哪天”hey”的值變動了,A的內容也會跟著變動! 同時char*可以指向任意大小的char[],但只要char[]內容更動,char*也會受到影響

因為這個特性,char*不同於char[],他是可以在後天改值的,只要改變他指的地址即可。

  • char*就是浮萍,不像char[]、malloc()出來的char*一樣攜家帶眷

不過,也因為他是單單一個指向記憶體的指標,我們不能透過strcpy等函數塞整個char array給他,他的空間尚未被初始化,如果直接用strcpy很可能導致SEG Falut

而且因為類別正確(strcpy的確是接受char*作為參數),所以編譯器並不會警告,新手在看文件時也會看到輸入參數是char*就傻傻地把char*丟進去了

最後,char*如果沒有被初始化(指向某個常數字串)而直接印出,也會SEG fault

  • 這類char指標的size是根據作業系統的位元數變動的

char *[]

根據C/C++宣告閱讀法,以下面的變數為範例

1
char* hard[3];

我們可以得到他是「hard is size-3 array of pointers to char 」,也就是3個char*。因此我們我們可以套用char*的作法,hard這個變數是不能被strcpy的(不會有任何警告但會SAG fault)

額外補充

另一個常見的SEG fault的原因就是生命週期

考慮以下code

1
2
3
4
5
6
7
8
9
10
void foo(char* in){
char ans[] = "laugh";
in = ans;
printf("\nin funct, aram = %s\n",in);
}

int main(int argc, char* argv[]){
char* aram;
foo(aram);
printf("\nout funct, aram = %s\n",aram);

我們應該會期望得到輸出

1
2
in funct, aram = laugh
out funct, aram = laugh

但結果卻是SEG fault

因為ans作為foo函數的區域變數,在退出函數時就已經消滅了,當aram變數還指向他的時候,其實會出現未定義行為

所以如果想要讓aram保存ans的結果,最好的做法就是用malloc的,如下code

1
2
3
4
5
6
7
8
9
10
11
12
void foo(char* in){
char ans[] = "laugh";
   strcpy(in,ans); //注意要改成strcpy!
  // in = ans;
printf("\nin funct, aram = %s\n",in);
}

int main(int argc, char* argv[]){
char* aram;
   aram = (char*) malloc(sizeof(char)*16); //讓aram變成malloc變數,可以「攜家帶眷」
   foo(aram);
printf("\nout funct, aram = %s\n",aram);

Note: 如果aram在丟入foo以後才malloc,仍會因為命名問題消滅造成SEG fault!!

如果想要在函數內進行malloc,則需要傳入aram的地址,如下code

1
2
3
4
5
6
7
8
9
10
11
void foo(char** in){
char ans[] = "laugh";
*in = (char*) malloc(sizeof(char)*16);
strcpy(*in,ans);
printf("\nin funct, aram = %s\n",*in);
}

int main(int argc, char* argv[]){
char* aram;
   foo(&aram); //改這裡
   printf("\nout funct, aram = %s\n",aram);

本篇主要講述C++中pipe()函數的相關行為

因為pipe的buffer大小並非無限大,如果輸入流資料量過大,很有可能會碰到buffer塞滿而輸入還沒結束的問題
寫了以下的code來測試pipe buffer如果塞爆了會發生甚麼事情

實驗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <string>
#include <vector>
#include <sstream>
#include <cstring>
using namespace std;
int main(int argc, char* argv[]){
// 創造pipe
int my_pipe[2];
if(pipe(my_pipe) == -1){
fprintf(stderr, "Error creating pipe\n");
}
//-------------------------
pid_t child_id;
child_id = fork();
if(child_id == -1){
fprintf(stderr, "Fork error\n");
}
// 創造一個子process,將buffer塞爆
if(child_id == 0)
{
close(my_pipe[0]);
dup2(my_pipe[1], 1);

string some = "something";
for(int i=0;i<1000000000000000;i++){
cout<<some;
}
cout<<"Chind,finished";
exit(0);
}
//---------------------------------
else
{
int aaa = fork();
// 再創造一個子process,讓他先sleep 4秒以後再嘗試在已經被塞爆的buffer寫入
if(aaa == 0){
sleep(4);
close(my_pipe[0]);
for(int i=0;i<1999;i++){

cout<<"Child2 round "<<i+1<<"\n";
write(my_pipe[1],"NP",sizeof("NP")); // is stuck because of the fullness of pipe
}
exit(0);
}
//----------------------------

// 原本的父process,先sleep 10秒讓我們觀察child process被塞爆的現象再read一些東西來疏通pipe,但這樣的量不足以讀完所有的input
else{

close(my_pipe[1]); // parent doesn't write

char reading_buf[1000]={'\0'};
sleep(10);
for(int i=0;i<10000;i++){
read(my_pipe[0], reading_buf, 100);
}
}
}
//等待第一次fork出來的子process
wait(&child_id);

//這行永遠不會印出來,因為子process永遠不會輸出完成而結束
cout<<my_pipe[0]<<my_pipe[1]; //3,4
return 0;
}

實際編譯執行後,出現以下結果
upload successful
Child2卡在第1897次輸出就寫不下去了,當然第一個process也是卡住的狀態(見Ps)

Pipe特性

從這個小實驗可以知道一些事情

  • pipe的buffer有限,是會被塞爆的

  • 原生的pipe如果被寫滿,會讓想繼續寫入的所有process被卡住不能繼續執行,直到pipe被讀取

    • 不可以wait process完整寫入發signal以後才fork另一個process再讀取,這樣很可能導致整個程式卡死
         - 如果卡住的process太多,可能會讓父process再也fork不出東西來讓本該讀取的process去接,造成整個程式卡死
  • 要注意針對大資料的處理,pipe應該要有個”抒發管道”,不能期待他真的裝下全世界

補充

我另外做了一個反向實驗:
讓輸入資料的process延遲輸入,而讀取的process開始讀空的pipe,得到以下心得

  • 讀取端會等read(fd,char* buffer,int size)裡面的size被填滿才會執行接下來的動作
    • 想到以前上課老師說的,只要還有process 對pipe的輸入端還未關閉,讀取端就會一直認為有東西要進來,而呆呆地等 -> 關不用的stream很重要!

P.S
測試這個東西的時候還有用背景執行,創造了不少卡著的process

其中相連的pid可以看出來是同一個程式來的,原本的父process,連帶所有child process都無法被正常結束…

參考資料: stackoverflow

用std::string做strtok

由於C++的string type並不支援strtok的功能,所以如果想要將C++的string做切段,有以下幾種方法:

法1: 用istringstream

使用stringstream類別,使用方法就像C++風格的iostream一樣,只是這個stream不是stdin/stdout,也不是fstream,而是將string的內容倒入一個stream (因此不具有fd–待查證)。

將要切割的字串倒入stream以後,再用getline中的Delimiter參數做為切割標準即可
參考程式碼片段如下:

1
2
3
4
5
6
7
8
9
10
vector<string> split(const string& s, char delimiter){
vector<string> tokens;
string token;
istringstream tokenStream(s);
while (getline(tokenStream, token, delimiter)){
tokens.push_back(token);
}
return tokens;
}
// tokens vector裝的是切割完的string

法2: 先把string轉成char*以後再切割

參考資料
如果要將string轉換成char*,可以透過string.c_str()函數

這個方法其實不太推薦,他是把C++風格棄掉,強制使用strtok來處理字串
參考程式碼片段如下:

1
2
3
4
//given string str as a string needed to slice
char *dup = strdup(str.c_str());
token = strtok(dup, " ");
free(dup);

Train跟testing data之間可能會有不同的分佈 -> domain shift

ex. 用黑白圖片訓練數字辨識,但測試資料使用彩色圖片,則命中率會大幅降低

Domain shift的種類

  • 不只是輸入資料的特性不合
  • 可能輸出的資料,其機率分佈不一樣
  • 或是也許在測試資料裡面,雖然圖樣跟訓練資料很像,但是它所代表的意涵卻不一樣

Domain adaptation

  • 可以看作是transfer learning的一種
  • 我們會需要對target domain有一些了解

Case 1:有target domain的labeled資料但資料量很少

  • 用類似BERT的fine-tune方法來微調一下model
  • 但target domain資料量很少,所以很容易overfitting
    • 限制fine-tune前後的參數變化量
         - 降低lr
         - 限制epoch數

Case 2:有一大堆target domain的unlabeled資料

  • 本課的討論重點
  • 在實務上比較有常發生
  • Idea:用一個feature extractor把source跟target domain的不同點刪除,擷取出共同的部分
    • Ex.數字辨識,學習去忽略圖片顏色

Domain Adversarial training

原理

  • 我們會訓練出一個new image classifier model,其中前半部分是feature extractor,後半部則是label predictor

  • 我們會希望feature extractor的輸出(上圖右下角的分佈圖),source跟target domain的分佈看不出差異

  • 由feature extractor跟domain classifier互相對抗,將feature extractor的輸出送到domain classifier,domain classifier要想辦法辨認出這個輸出是來自source還是target domain

  • feature extractor -> Generator & domain classifier -> Discriminator

  • 但這樣對於feature extractor優勢太大,因為只要他都輸出0,就可以讓domain classifier被輕鬆騙過去 -> 讓label Predictor也加入戰局

計算方法

  1. Feature extractor的參數為$\theta_f$
  2. Label Predictor的參數為$\theta_p$
  3. Domain Classifier的參數為$\theta_d$
  4. 輸出圖片預測結果與真實結果的loss(cross entropy)為$L$
  5. Domain Classifier二元分類器的輸出loss為$L_d$

因為我們同時希望Label Predictor分類越正確越好,又同時希望domain classifier能被騙過。則可以得出一個最佳化feature extractor的公式(非正確,勿照抄)
$$
\theta_f^* = min_{\theta_f}\ L-L_d
$$

問題來了,如果我們直接套用這個公式,會導致$L_d$越大越好(也就是讓domain classifier的loss飆高),這可能讓feature extractor變成努力讓domain classifier把target看成source,source看成target,而這也是某種程度上的分隔開兩個domain

如何改善公式,留給大家思考orz

domain adversarial training的效果拔群

Limitation


由上面的公式,我們可以練出上圖兩種類型的model滿足上面的公式,但是可以明顯看出,右邊的分佈會比左邊還好

我們雖然不知道橘色(target domain)的label為何,但我們知道藍色(source)資料的分界線,因此我們要在這樣的前提下,想辦法也讓橘色的資料被該分界線劃清

  • 有很多相關方法
    • 參考文獻:DIRT-T
    • 一種簡單的方向是確保unlabeled data丟入label predictor後輸出的分佈越集中越好

Case 3:雖然Target domain unlabeled data很多,但Source跟Target domain的class集合不同

到目前為止,我們都假設target跟source domain的類別集合是一樣的

如果類別集合不同,則硬要align data可能會反導致兩個無關的class被綁在一起 $\rightarrow$ Universal domain adaptation

Case 4:Target domain unlabeled data也很少

Case 5:我啥都不知道QQ

  • Domain Generalization
    • 訓練資料豐富,包含各種domain(ex. 貓狗分類,除了真貓真狗以外還有素描、卡通畫風)
        - 參考文獻
         - 訓練資料不豐富,但測試資料很豐富(有點像想辦法做data augmentation)
        - 參考文獻