# 2024q1 Homework5 (assessment) contributed by < `164253` > ## 測驗題改進與問題 ### [第一週測驗 `2` 改進](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ#164253) 改進的不是 Timsort 和 mergesort 本身的實作,而是給出對應的最差情況的方法,用以驗證最差複雜度符合預期。 :::warning 題目中的程式碼改進待補 ::: ### [第三週測驗 `2` 的改進方法證明](https://docs.google.com/document/d/1Fy5ReLWNFXeOs2XzH-33_etsQUf7E9yrQKbtkhu56ZM/edit) 參照我高中時根據網路資料證明的預處理快速除法,可以提前算出適當的值,雖比起題目中只需移位和加減法操作,多出了一次乘法的成本,但對於任意的常數都可以直接算出對應的值,而不用針對不同情況進行討論。 :::warning 題目中的程式碼改進待補 ::: ### 第四週測驗 `1` 改進 #### 延伸問題 2. 觀察測驗題最後給出的規律可以發現,每個位元中 1 的數量乘以 0 的數量,就會是那個位元的漢明權重,且各個位元的答案累計再一起是對的。 此時問題轉變成了如何快速求得所有數字中,某個位元為 1 的數量有多少。觀察後我並沒有想出每次掃過一遍以外更好的想法。 由於題目保證輸入在 32 bits 以內,因此需要 $32n$ 次計算,和 $n$ 次乘法。 答案最大會發生在恰有一半位元是 0 的時候,最終會有 $32\times(\frac{n}{2})^2=8n^2$ ,題目中 $n\leq10^4$ ,不會超過 signed int 。 ```c int totalHammingDistance(int* nums, int len) { int ans = 0; for (int i = 0; i < 32; ++i){ int count = 0; for (int j = 0; j < len; ++j) count += nums[j] >> i & 1; ans += count * (len - count); } return ans; } ``` ## 閱讀〈因為自動飲料機而延畢的那一年〉的啟發 > 在失敗過這麼多次後,我們得到了一個結論:「我們要解決更為具體的問題。」 僅管我做專案的次數不多,但我的經驗中每次規劃專案時,常常都會提出過於理想化,或甚至沒有效益的題目。 > 大多數人一直活在本來就應該這樣嗎的童話世界裡,電視打開就可以看,機車買來就可以騎,手機買來就可以用,一切都理所當然,本來就應該這樣。 平常用各種套件,或是常用的資料結構,我也都覺得他們本來就存在,這次課程中才發現很多的複雜度和漂亮的程式寫法,都是靠大量的實驗跟經驗累積的。 > 然後我發現一個原本以為只有在資工系發生的現象,那就是「資工系的學生不會寫程式,機械系的學生不會做機械」。 見過各類同學和實際看到大學的課程後發現,大部分教學的內容都是對單一領域的介紹,且經常過於理想,沒有從頭開始完整的實作,也容易遇不到整個系統實作的常見問題。 這門課開始前,我也一度以為自己會寫 C 語言、會資料結構、演算法,看過教材中各種未曾設想的情況後,才發現有各類的技巧,第一時間不會想到的最差情況等。 > 硬體的世界和軟體完全不一樣,一個程式設計師遇到問題時,電腦會告訴你哪裡出錯,接著查資料把程式碼改正,重新執行一次就好,發現問題到修正的速度非常快。你遇到的問題很可能世界上某個人已經遇到過,只要把錯誤訊息拿去搜尋,往往就能找到想要的答案。 > 一項產業進步的速度,很大程度取決於做實驗修正問題的速度。 程式設計之所以能快速發展和此有不小的關聯,但正因成本太低,要想能和他人做出區別,就要能給出網路查不到的東西,用省下的時間做更多的實驗,以確保產出的程式有效率又安全,最好還能寫得漂亮。 > 「這些學校上課、教授不會教啊。我以前也是焊得很爛,能動就好。」紘銘說:「後來有次我進實驗室做實驗,實驗室的大學長看不下去,花了一個多小時教我這些技巧。這些基本到不行、看起來不難的東西,動手做之後才會發現很多細節要注意。」 呼應資工系學生不會寫程式,許多經驗法則的東西,是在實作中才能發現的。 > 但我相信這個問題絕對不會沒有人碰過,一定有人解決過,所以你不該卡在這裡,因為這件事卡在這裡是相當不值得的。 許多實務上的問題不是沒人解過,只是不常遇到,而且沒有通用的解法,是因應當下的情境做取捨。 而另一種類似的問題,則是因為專利等理由,所以沒有被公開,或單純是沒有查到相關資訊。 ## 教材心得和提問 ## 想投入的專案 雖然我前幾次的作業進度十分緩慢,但去年仍有許多專案讓我有興趣。 我對網路相關的專案興趣相對小,因為打競賽的關係,還是更傾向資料結構、演算法、編譯器等領域。 ### 改進 Linux 核心的 lib/{list_}sort.c ### 針對 rv32emu 實作 JIT 編譯器 ### 紅黑樹實作改進 --- https://lore.kernel.org/lkml/Zktnt7rjKryTh9-N@arch/T/ sort https://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git (新的 v6.12) linux-6.10-rc3 (沒有重大變革的話,不會接受修改) linux-6.11 merge window (進行中) linux-6.12 (你若提交修改,則會收錄在此) 量化分析 TODO: sort 的 KUnit 改進 TODO: 研究 lib/sort.c 說明近期的改進,(optionally) 尋找更多改進空間 * https://www.facebook.com/groups/system.software2024/posts/1617016709076221/ * https://www.facebook.com/groups/system.software2024/posts/1617008692410356/ TODO: 自行發揮,選擇改進的標的。留意量化 (comparison, memory acess, locality)
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up