2024q1 Homework5 (assessment)

contributed by < 164253 >

測驗題改進與問題

第一週測驗 2 改進

改進的不是 Timsort 和 mergesort 本身的實作，而是給出對應的最差情況的方法，用以驗證最差複雜度符合預期。

題目中的程式碼改進待補

第三週測驗 2 的改進方法證明

參照我高中時根據網路資料證明的預處理快速除法，可以提前算出適當的值，雖比起題目中只需移位和加減法操作，多出了一次乘法的成本，但對於任意的常數都可以直接算出對應的值，而不用針對不同情況進行討論。

題目中的程式碼改進待補

第四週測驗 1 改進

延伸問題 2.

觀察測驗題最後給出的規律可以發現，每個位元中 1 的數量乘以 0 的數量，就會是那個位元的漢明權重，且各個位元的答案累計再一起是對的。
此時問題轉變成了如何快速求得所有數字中，某個位元為 1 的數量有多少。觀察後我並沒有想出每次掃過一遍以外更好的想法。
由於題目保證輸入在 32 bits 以內，因此需要

$32n$ 次計算，和

$n$ 次乘法。
答案最大會發生在恰有一半位元是 0 的時候，最終會有

$32\times (\frac{n}{2}{)}^2=8n^2$ ，題目中

$n\le {10}^4$ ，不會超過 signed int 。

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)