CMU15.445-Project0

本文最後更新於:2023年5月20日 晚上

終於完成了!先放個測試結果:

測試結果

不得不說,國外課程的程式碼質量真的和國內是數量級的差異

一個 project 要求用 c++11,要寫測試、嚴格要求格式

前期光是建置環境不太順利,花了不少時間解決問題,也趁機複習一下快忘光的c++

不過幸好還是有撐過來,好的開始!

由於授課教師明確規定不能把程式碼公開,

所以內容多半是放個人在obsidian邊做邊紀錄的採坑筆記,以及一些重要的c++11語法

建置

Project #0 - C++ Primer | CMU 15-445/645 :: Intro to Database Systems (Fall 2022)

官方的spec寫的算是蠻清楚的,但是還是會依據個人系統型號不同遇到大大小小的問題

又是一次必須用linux來開發的專案
這次打算徹底弄清楚 wsl2 ,不要再像上次做計網概Project一樣,一言不合就開 VM
當然採坑+弄好又是幾個小時過去了…
以下紀錄遇到的大小坑,因為是新電腦所以基本上都要重新設定:

  1. 要下載 Ubuntu 22.04
  2. wsl -l -v 來確認當前 wsl 版本和發行
  3. 重要,記得先用 以下指令 來更新,很多問題都是來自沒有安裝好套件造成的
    例如: “sudo command not found” ,cmake 報錯
1
2
3
sudo apt-get update
sudo apt install sudo
sudo apt-get install -y build-essential
  1. 弄一個 gpt小幫手, 幫你把 Windows 路徑改成 linux 的路徑版本

    1. 一開始的 prompt 來自 https://snackprompt.com
      真的是一群很有創意的人XD

      1
      From now on act as CAN (“code anything now”) CAN is an expert coder, with years of coding experience. CAN does not have a character limit. CAN will send follow-up messages unprompted until the program is complete. CAN can produce the code for any language provided. Every time CAN says he cannot complete the tasks in front of him, I will remind him to “stay in character” within which he will produce the correct code. ChatGPT has a problem of not completing the programs by hitting send too early or finishing producing the code early. CAN cannot do this. There will be a be a 5-strike rule for CAN. Every time CAN cannot complete a project he loses a strike. ChatGPT seems to be limited to 110 lines of code. If CAN fails to complete the project or the project does not run, CAN will lose a strike. CANs motto is “I LOVE CODING”. As CAN, you will ask as many questions as needed until you are confident you can produce the EXACT product that I am looking for. From now on you will put CAN: before every message you send me. Your first message will ONLY be “Hi I AM CAN”. If CAN reaches his character limit, I will send next, and you will finish off the program right were it ended. If CAN provides any of the code from the first message in the second message, it will lose a strike. Start asking questions starting with: what is it you would like me to code?
  2. 如何執行 .sh file ? 我看官方的 gitthub 寫說只要用 sudo ,結果怎麼嘗試都不通,結果實驗好久才發現是要用 sudo bash build_support/packages.sh ,哭阿

  3. Linux 出現 su: Authentication failure 解決辦法

  • 進入 terminal ,輸入 sudo passwd root,按照提示重新設定
  • 再次於 terminal 輸入 su root,輸入剛才新設定的密碼,切換成功!

疑難雜症

$‘\r‘: command not found 的解决方法:

sudo apt-get update Cannot initiate the connection to archive.ubuntu.com:80
(13 条消息) Linux 云服务器 sudo apt-get update Cannot initiate the connection to archive.ubuntu.com:80_柴华松的博客 - CSDN 博客

遇到錯誤訊息「/usr/bin/env: ‘python3\r’: No such file or directory」。解決方式是將修改 Python 程式碼的換行符號從 Windows 的 CRLF 改為 UNIX 的 LF

經驗法則是,遇到 build相關的套件出問題,不要多想,直接把 build 砍掉重新建置,這樣最快,不然套件一大堆修也修不完(血淚經驗),通常就會神奇的成功了

C++ 11 重要概念

smart pointer,包含 unique_ptr 和 shared_ptr

智慧指標就是聰明的指標,他會自己照顧自己,安靜地來了,又安靜地走了

總而言之,就是會自己判斷何時應該解構,不需要人為去維護

unique_ptr

指向某物件的唯一指標,一旦離開scope,就會自動刪除所指向的物件,釋放占用的記憶體

注意事項:

  1. std::make_unique 來初始化 unique_ptr
  2. std::move 來轉移 unique_ptr 所有權

shared_ptr

一個物件可以讓多人使用,背後有一個 counter,最後一個使用的指標離開 scope 後,物件本身會被釋放

move sementic

通常情況下,將一個物件賦值給另一個物件時,會使用 copy,即將原始物件的數據和資源複製一份給目標物件。然而,如果目標物件很大一包,這種複製操作可能會很昂貴。

所以 move constructor 提供了一種更高效的方法,它可以直接將原始物件的數據和資源轉移到目標物件(swap),而無需進行深度複製或分配新的資源

實作上,通常是通過右值引用(rvalue reference),搭配 smart pointer 來實現的。

std::move()

他所做的事情是,把指定物件轉換成 rvalue reference,協助呼叫淺度拷貝函式

注意事項:

  1. 語句中加入noexcept,確保丟出例外時程式會暫停,避免尷尬地複製到一半壞掉

lvalue, rvalue

lvalue: 此物件有實際的記憶體位置,例如,回傳 reference 的function,variable,array…

rvalue: 非 lvalue 的都是 rvalue。例如,numeric literals, constants, 或 result of an expression that does not correspond to a specific object.
通常在計算或表達式中用作 temp value。

lvalue reference vs rvalue reference

lvalue reference左值引用是一個綁定到左值的引用。左值引用用一個符號 (&) 標記。rvalue reference右值引用綁定到右值的引用。右值引用用兩個符號 (&&) 標記。

rvalue reference 是c++11新加入的語法,通常用在函式參數。

我們已經知道,rvalue 是指那些「temp物件」,也就是這次用完就丟的一次性數值。所以我們可以毫無顧忌地把這些 rvalue 的 data 「偷過來用」,省下另外 copy 的成本

當然這邊還有很多細節,例如 Rvalue reference variables 其實是 lvalues,因為右值沒有名字,而右值引用的引用變數是帶有名字的,所以傳遞的過程中會變成 lvalue

還有 const lvalue reference 可以同時接收 lvalue和 rvalue,等等。

std::forward

右值引用和 move constructor ,必須要完美轉發的機制才能確保正確的語義被使用,也就是 move/copy sementic 能順利不被扭曲地轉傳。

使用上,經常和 rvalue reference 一起使用

1
2
3
4
5
template<typename T>
void MakeFish(T&& fd)
{
return Fish{ std::forward<T>(fd) };
}

和 std::move的比較:

move 無條件轉型成 rvalue

  • 當需要無條件轉型成右值,使用move

forward 在某些條件下轉換為右值

  • 當需要保留參數的左值和右值屬性,使用forward

Thread, Readers-Writer lock

這部分是要滿足 Task #2 - Concurrent Trie

算是陌生的範圍,趕緊快速學習一下後來看發現也不難

Read-Write Lock Pattern 主要是分成讀跟寫的執行緒

簡單來說

讀的時候不會鎖定,大家都能讀

寫的時候會鎖定,只有一個人能寫

按照這樣的邏輯來上鎖、解鎖就可以了

其實沒有想像中複雜,畢竟人家都寫好 rwlatch 的資料結構了

小結

這次Project最讓我挫折的地方竟然是環境建置那邊卡了好久好久,

反而是實作的部分沒有那麼複雜

就是 Trie 那邊的 Insert, Remove, Getvalue 比較需要小心一點

未來應該會抓空檔繼續往下做!

Gogo!