# 2024-03-{19,21} 討論簡記

## 人工智慧風潮背後的生態
> 整理自 [Just how rich are businesses getting in the AI gold rush?](https://www.economist.com/business/2024/03/17/just-how-rich-are-businesses-getting-in-the-ai-gold-rush)，《經濟學人》，2024 年 3 月 17 日

台灣的半導體和電子產業在 AI 硬體領域享有優勢，儘管只是硬體領域的一部分，但對台灣來說，這已是重大的機會。回顧 [Wintel](https://en.wikipedia.org/wiki/Wintel) 在 2000 年代掌控個人電腦產業高達八成的營運利潤，及 Apple 自 2007 年推出 iPhone 後不久就壟斷全球手機製造業的大部分利潤，我們正處於生成式 AI 技術初期成長階段。

AI 產業可以分為四大層次：
* 軟體應用：銷售給企業的 AI 應用程式；
* 模型：AI 模型 (例如 GPT-4) 及其開發工具 (如 Hugging Face)；
* 雲端運算：托管這些模型與應用場景的雲端運算平台 (如 Amazon Web Services, Google Cloud Platform, Microsoft Azure) ；
* 硬體：雲端運算所需的硬體設備，包括運算晶片 (如 NVIDIA, AMD, Intel 等) 、伺服器 (如 Dell 等) 與網路設備 (如 Arista等) 。

> Wired, 2002: "THE NEXT INTEL" [source](https://twitter.com/rodolfor/status/1769443128203780185)

自 ChatGPT 在 2022 年 10 月橫空出世以來，短短一年半約有 100 家公司的市值增加 8 兆美元，這份額外的價值越來越集中在每個層級的少數領先公司。在硬體、模型和軟體應用方面，過去一年半，頂尖三家公司在市值增加的比例中位數提升 14%。雲端運算方面，三巨頭 (指 Amazon, Google 和 Microsoft，以下採簡稱) 的市值合計增加 2.5 兆美元。特別是與 OpenAI 合作的 Microsoft，在雲端服務領域的市值占比由 ChatGPT 推出前的 41% 增長至 46%。

在硬體製造商累積最多財富的同時，獨立模型製造者在市值增長倍率上表現最為強勁。《經濟學人》檢視的 27 家上市硬體公司市值從約 1.5 兆美元增至 5 兆美元，預示著與網際網路技術繁榮期期望相同：先構建基礎設施，然後是軟體的大展拳腳。

NVIDIA 市值增幅中占比約 57%，生產超過 80% 的 AI 晶片，在資料中心 AI 伺服器連接晶片的網路設備幾乎形成壟斷。過去 12 個月，NVIDIA 資料中心業務的營收較上年同期成長 2 倍多，毛利率從 59% 增長至 74%。AMD 和 Intel 也在爭奪這塊財富，推出競爭產品。新創公司如 Groq 和 Cerebras 在超高速 AI 晶片和超大晶片領域同樣如此。雲端服務三巨頭也在設計自己的晶片，以減少對單一供應商的依賴，藉此分攤豐厚的利潤。AMD 執行長蘇姿丰預測，AI 晶片市場的營業額可能從 2023 年的 450 億美元飆升至 2027 年的 4000 億美元，這塊「大餅」難以由 NVIDIA 獨吞。

未來幾年內，NVIDIA 在硬體市場的控制力看似仍然穩固，雲端服務巨頭自行設計的晶片部署仍相對有限。NVIDIA 擁有 CUDA 運算平台及其生態系統，讓客戶根據需求調整晶片，廣受程式開發者採納，使客戶難以轉向不支持 CUDA 的競爭對手。

儘管硬體從絕對值來看贏得最多，但獨立模型製造者的成長倍率最高。《經濟學人》檢視的這類 11 家公司的總市值，過去 16 個月從 290 億美元躍升至約 1380 億美元。
* OpenAI 的估值約為 1000 億美元，遠超 2022 年 10 月的 200 億美元。
* Anthropic 的估值從 2022 年 4 月的 34 億美元飆升至 180 億美元。
* 成立不到一年的法國新創 Mistral，目前估值約為 20 億美元。

模型製造者的真正價值在於他們的智慧財產權及其潛在利潤。這些利潤的實作程度將取決於模型提供者間的競爭有多激烈及持續時間長短。目前的競爭已經非常激烈，這或許可解釋為何這一層在絕對值上的增長較少。
> [OpenAI「七叛徒」另立門戶，新創 Anthropic 真能打敗 ChatGPT？](https://technews.tw/2024/03/16/openai-vs-anthropic/)

雖然 OpenAI 早早取得領先，但其他挑戰者正在迅速追趕，他們能夠同樣免費利用與 ChatGPT 製造者相同的資料 (即網際網路的文字和圖像) 。
* Anthropic 緊隨 GPT-4 後，四個月內發布 Claude 3。
* Facebook 的母公司 Meta 發布 [Llama 2](https://llama.meta.com/)，與 OpenAI 和 Anthropic 的封閉專有模型不同，這是一個開放的強大競爭者，提供非獨家、全球性、不可轉讓、無版稅的有限授權，用於使用、修改和分發 Llama 2 的材料，但基於使用者規模和使用目的則若干限制，例如一個產品的每月活躍使用者若超過 7 億，則該向 Meta 申請特殊授權。
* 2024 年 2 月，員工不到 40 名的 MistrAI 發布[其開放模型](https://docs.mistral.ai/models/)，例如 Mistral 7B 以 Apache 2.0 授權發布，是真正的開放原始碼授權模式，令業界驚嘆之處在於，MistrAI 模型性能可媲美於 GPT-4，而訓練和執行所需的運算能力要少得多。意味著，即使是較小的模型也能夠以低廉的價格提供優異的性能。
* 新創公司 Nixtla 開發針對財務預測的模型 TimeGPT。
* Hippocratic AI 根據醫學院的考試資料訓練模型，提供準確的醫療建議。

Microsoft Research 在 2024 年 3 月發布〈[The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits](https://arxiv.org/pdf/2402.17764.pdf)〉研究，其中每個單一參數都是 balanced ternary (平衡三進位) 的 ${-1, 0, 1}$，在性能上可媲美於全精度的 Transformer LLMs，同時顯著提升效率，為一位元大型語言模型的新時代鋪平道路。
> [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)

模型的趨於豐富直接刺激各式 AI 應用的成長。自 2022 年 10 月以來，軟體應用這一層的 19 家上市軟體公司市值躍升 1.1 兆美元，即增長 35%。其中包括大型軟體供應商將生成式 AI 整合進他們的服務中。
* Zoom 利用 AI 讓使用者對視訊會議進行摘要總結。
* 為企業提供技術、人力資源和其他支持的 ServiceNow 引入聊天機器人來協助解決客戶的資訊科技諮詢問題。
* Photoshop 的開發商 Adobe 有個名為 Firefly App 的應用程式，利用 AI 編輯照片。
* AI 應用匹配網站 [There's An AI For That](https://theresanaiforthat.com/) (TAAFT) 收錄超過 12,000 個應用程式，而 2022 年還不到 1,000 個。
* DeepScribe 幫助轉錄醫生的筆記。
* Harvey AI 協助律師。

激烈的競爭和較低的進入門檻意味著，一些應用可能難以獲得顯著的價值。

生成式 AI 熱潮爆發後，雲端服務三巨頭的總市值躍升 2.5 兆美元。預計到 2024 年底，生成式 AI 將為雲端巨頭增加 200 億美元的銷售額，市值/銷售額增加比率為 120 倍。與此相較，硬體公司的相對比值約為 40，模型製造者約為 30。這意味著投資者相信，從長遠來看，雲端巨頭將成為最大的贏家。

投資者對雲端運算的看好可以用三個因素來解釋：
1. 科技巨頭擁有開發世界領先 AI 系統所需的所有要素：大量資料、大量研究人員、龐大的資料中心和大量閒置資金。
2. AI 服務的買家，如大企業，更願意與成熟的商業合作夥伴交易，而非新貴。
3. 大型科技公司有最大的潛力控制從晶片到應用程式的每一層。

除了設計一些自家晶片外，雲端服務三巨頭還針對模型和應用場景進行投資。

《經濟學人》檢視的 11 家模型製造者中，有 9 家至少獲得三大巨頭中的一家的支持，包括 Microsoft 所支持的 OpenAI 和 MistrAI，以及 Google 和 Amazon 支持的 Anthropic。

OpenAI 的內部創投部門自 2021 年 1 月成立以來，已投資 14 家公司，包括協助律師工作的 Harvey AI 和醫療新創 Ambience Healthcare。據報導，Sam Altman 正尋求投資者為價值 7 兆美元的晶片製造企業提供資金。NVIDIA 也野心勃勃，投資 7 家模型製造者，以提供自家 AI 模型。此外，NVIDIA 還投資 Together AI 和 CoreWeave 等新創公司，這些公司與其大型雲端客戶形成競爭。

延伸閱讀: [Why do Nvidia’s chips dominate the AI market?](https://www.economist.com/the-economist-explains/2024/02/27/why-do-nvidias-chips-dominate-the-ai-market)

---

## 佳句偶得
* 「資訊人的本色就是做什麼，就要像什麼」 —— 洪良茂，成功大學資訊系大學部第一屆畢業生。
* 「紙上得來終覺淺，絕知此事要躬行」，出自《冬夜讀書示子聿》(1199 年)，作者陸游
> 間接經驗是從書本中汲取養分，學習前人的知識的途徑，而直接經驗是親身體認到的知識，是獲取知識更重要的途徑。唯有藉由「躬行」，把書本知識變成實際知識，方可深入理解其中的道理。
* 「大部分的人一輩子洞察力不彰，原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享，時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了」 —— 蔡志浩

---

## idoleat
> [quiz1+2](https://hackmd.io/@idoleat/linux2024-homework2)

評：NVIDIA 考前衝刺

排序是一維資料附加序列位置資訊、擴增為二維，再投影至另一維之展現。

## jouae
> [PR #173: Improve string randomness](https://github.com/sysprog21/lab0-c/pull/173)

在 [lab0-c](https://github.com/sysprog21/lab0-c) 的 `qtest.c` 中有對於隨機字串插入佇列的功能，藉由 `RAND` 關鍵字啟用偽隨機字串生成器。使用方式如 `ih RAND 5` ，執行 `q_insert_head` 對佇列開端插入隨機 $5$ 個字串。

在 `qtest` 中隨機字串生成的函式為 `fill_rand_string` ，對全域變數 `charset` 由 26 個小寫英文字母的組成陣列，隨機挑選介於 `MIN_RANDSTR_LEN` 和 `MAX_RANDSTR_LEN` 個字元，最後組成字串。

static void fill_rand_string(char *buf, size_t buf_size)
{
    size_t len = 0;
    while (len < MIN_RANDSTR_LEN)
        len = rand() % buf_size;

    randombytes((uint8_t *) buf, len);
    for (size_t n = 0; n < len; n++)
        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
    buf[len] = '\0';
}

其中偽隨機數的生成藉由 [randombytes](https://github.com/dsprenkels/randombytes) 實作。

而 `wuyihung` 發現在此採用 `uint8_t` 會有一個問題：
>However, since the number of variations is 256, which is not exact division of 26

`uint8_t` 在 [stdint.h(0p) — Linux manual page](https://man7.org/linux/man-pages/man0/stdint.h.0p.html) 中的敘述如下：
>The typedef name intN_t designates a signed integer type with width N, no padding bits, and a two's-complement representation.

藉由此敘述得知非符號整數，以十進位表示法範圍為： $[0,255]$ 。`buf[n] % (sizeof(charset) - 1)` 從數學角度解釋，此處是對於 $x\equiv i \pmod{26}$ 選定索引的過程。

藉由[除法原理](https://en.wikipedia.org/wiki/Euclidean_division)可以得到 $$
255 = 26 \times 9 + 21.$$

換句話說 0 到 25 數字的倍數在 0 至 255 中，除了 22, 23, 24, 25 倍數之外皆出現 10 次。

**假設 `randombytes` 給定的隨機數是均勻且彼此獨立的**，在此之下 0 到 21 數字倍數出現的頻率為 10， 22, 23, 24, 25 倍數為 9 。假設 0 到 25 對應到小寫英文 a 到 z ，其離散機率分佈表示為 $$
P(X=i) =
\begin{cases}
\dfrac{10}{256}, \text{ for } i=0,1,\dots,21 ,\\
\dfrac{9}{256}, \text{ for } i=22,23,24,25.
\end{cases} $$ 得知隨機生成的字元頻率不均勻。

`wuyihung` 使用 Python 設計一個[測試腳本](https://github.com/wuyihung/lab0-c/blob/master/scripts/test_prng.py)驗證上述理論上的情況。

他藉由重複執行 `ih RAND 30` $150,000/30$ 次後，將串列內所有的字串連接（ concatenate ）成一個字串，並使用 [`ent`](https://www.fourmilab.ch/random/)分析字串的 entropy 。發現理論跟實際有些許誤差（約 $0.0009$ ）。

-    randombytes((uint8_t *) buf, len);
+    uint64_t *randstr_buf_64 = malloc(len * sizeof(uint64_t));
+    randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
    for (size_t n = 0; n < len; n++)
-        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+        buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];

+    free(randstr_buf_64);

他改用 `uint64_t` 來改善隨機字串的生成過程。其想法很簡單，就是藉由把上述 8 bits 改成用 64 bits 表示，在上述分佈的分母由 $2^8$ 改為 $2^{64}$ 從除法原理得知：
$$2^{64} = 709490156681136600 \times 26 + 16$$ 其離散機率分佈表示為
$$
P(X=i) =
\begin{cases}
\dfrac{709490156681136601}{2^{64}}, \text{ for } i=0,1,\dots,16 ,\\
\dfrac{709490156681136600}{2^{64}}, \text{ for } i=17,18,\dots,24,25.
\end{cases} $$
參照他的實驗方式，此處將使用 `uint8_t` 和 `uint64_t` 的結果用 Python 套件 matplotlib 將數據以長條圖（ bar plot ）呈現。

採用 `uint8_t`：
總共 1050988 個字元。從 a 到 z 的頻率：
`[41080, 41161, 40861, 41197, 41150, 40723, 40969, 41191, 41006, 41099, 41278, 41312, 41146, 40890, 41113, 40846, 36915, 36894, 41141, 41231, 41035, 41269, 40993, 40905, 36696, 36887]`

採用 `uint64_t`：
總共 1049822 個字元。從 a 到 z 的頻率：
`[40629, 40651, 40560, 40750, 40237, 40244, 39793, 40428, 40261, 40372, 40540, 40571, 40310, 40795, 40222, 39952, 40452, 40058, 40700, 40048, 40713, 40398, 40332, 40431, 40047, 40328]`

`sizeof()` 在 C99 6.5.3.4 The sizeof operator 描述中也是回傳 `unsigned integer type`
> The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in <stddef.h> (and other headers).

由於 $charset$ 大小固定，以 `26U` `取代 sizeof(charset) - 1`

採用 `uint8_t` 並且使用 `26U` 取代 `sizeof(charset) - 1`取模：

-        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+        buf[n] = charset[buf[n] % 26U];

總共 1050391 個字元。從 a 到 z 的頻率：
`[40987, 41617, 40995, 41252, 41100, 40988, 40903, 41212, 40949, 40610, 40903, 41089, 41100, 40931, 41208, 40949, 40958, 40686, 41270, 41415, 40921, 40946, 37085, 36880, 36761, 36676]`

---

## 164253
#### 問題一 merge sort 最佳最差狀況
merge sort 最佳情況是已經排序好，第 $i$(1-base) 層要做 $\frac n{2^i}$ 次比較
由於左邊會先用完，只需比較 $\frac {2^i}2$ 次即可，共 $\sum_{i=1}^{\log_2n}\frac n{2^i}\times\frac {2^i}2=\frac n2\log_2n$ 次
合併相當於有 $n$ 個葉節點的平衡二元樹，有幾個非葉節點
(將合併過程畫出來可發現其他節點就是合併至一半的狀態)，需要做 $n-1$ 次合併

全部反過來時，比較和合併次數和排序好是相同的

交錯時，總比較次數 $f(n)=\left\{\begin{aligned}&n-1+2f(\frac n2)&\text{if n is even}\\&n-1+f(\frac{n+1}2)+f(\frac{n-1}2)&\text{if n is odd}\\&f(1)=0\end{aligned}\right.$
也就是假設 $n$ 是二的冪，總共要比較 $\sum_{i=1}^{\log_2n}\frac n{2^i}\times(2^i-1)=n\log_2n-(n-1)$
合併一樣是 $n-1$ 次，因此交錯才是真正的最差情況
並且可以發現 top down 的做法保證了陣列長度的平衡
如果是使用 bottom up 且不管最近的兩項長度是多少都合併的話，會造成總比較次數變多

::: success
weihsinyeh 在[作業二](https://hackmd.io/@weihsinyeh/ry2RWmNTT#%E6%8F%90%E5%87%BA%E6%94%B9%E9%80%B2%E6%96%B9%E6%A1%88%E4%B8%A6%E4%BA%88%E4%BB%A5%E5%AF%A6%E4%BD%9C)中指出不須每次都合併
每次尋找連續且小於另一 list 的節點，並一次合併可以節省操作
:::

#### 問題二 如何構造盡可能多不重複的 merge sort 最差狀況
##### 構造法一
將已排序陣列奇數項放一邊偶數項放另一邊
接著對分好的子陣列繼續做一樣的事

##### 構造法二
前兩項放最大和最小，接著兩項次大次小，依此類推，由於每兩項可以交換而不影響
長度 n 的陣列會有 $2^{\frac n2}$ 種排列

##### 構造法三
觀察構造法二合併過程，會發現只要過程中兩個陣列合併時，只要最大最小被放在一起就好
因此構造法二中，最大最小的一對和次大次小一對的相對關係並不重要，同一對在同組即可
總共有 $2^{\frac n2}\times\frac n2!$ 種排列

c++ 可用 `next_permutation` 實作，先生成 $1\sim\frac n2$ 照順序的排列
每次對第 $i$ 個數(定義為 $a[i]$)，輸出 $a[i]$ 和 $n-a[i]+1$
跑過所有排列便是全部的 merge sort 最差狀況

c 可以自己寫一個 `next_permutation` ，實作方式類似 leetcode 第 31 題

過程中需要排序，考慮每次改變的區間可以發現，長度為 $k$ 的區間有 $f(k)$ 個
$f(n)=0,f(n-1)=n-1,f(k)=k(1+\sum_{i=k+1}^nf(i))$
$\left\{\begin{aligned}\frac{f(k+1)}{k+1}-1=f(k+2)+\cdots+f(n) \\ \frac{f(k)}k-1=f(k+1)+\cdots+f(n)\end{aligned}\right.$
$f(k)=f(k+1)\frac{k(k+2)}{k+1}=(n-1)\frac{(n-2)n}{n-1}\frac{(n-3)(n-1)}{n-2}\cdots\frac{k(k+2)}{k+1}=\frac{n!}{(k+1)!}k$

假設長度 $k$ 的區間排序需要 $g(k)$，總共要 $\sum_{i=1}^n\frac{n!}{(i+1)!}i\times g(i)$ ，並且會跑過所有排序狀況
因此包含各種排序的最佳和最差狀況

若用 merge sort ， $g(k)$ 在 $\frac k2\log_2k$ 到 $k\log_2k-k+1$ 之間

用 qsort 的話， $g(k)$ 在 $k\log_2k$ 到 $k^2$ 之間

但每個排列生成後，仍要窮舉 $2^{\frac n2}$ 個較大數和較小數的排列，這步所花的時間遠大於前面
因此採用不同的排序並不是這段程式的瓶頸，

##### 構造法四
構造法三並不是全部的情況， n=8 1,8,2,3,4,7,5,6 就是一個反例
實際上只要合併時比較到最後一項就好，也就是兩個陣列中的最大項和次大項不能在同一邊
對於會被合併在一起的所有子陣列都要滿足，假設兩個長度為 $k$ 的陣列合併有 $f(k)$ 種
$f(k)=\left\{\begin{aligned}&2\binom{k-2}{\frac{k-2}2}f(\frac k2)^2&\text{if k is even}\\&2\binom{k-2}{\frac{k-1}2}f(\frac{k+1}2)f(\frac{k-1}2)&\text{if k is odd}\\&f(0)=f(1)=1\end{aligned}\right.$
假設 $n$ 是二的冪，有 $f(n)=2\frac{(n-2)!}{\frac{n-2}2!\frac{n-2}2!}(\cdots(2\frac{14!}{7!7!}(2\frac{6!}{3!3!}(2\frac{2!}{1!1!}(2\frac{0!}{0!0!}1)^2)^2)^2)\cdots)^2$ 種狀況
$f(n)=2^{n-1}\prod_{i=1}^{\log_2n}(\frac{(2^i-2)!}{(2^{i-1}-1)!(2^{i-1}-1)!})^{2^{\log_2(n)-i}}=2^{n-1}(n-2)!\prod_{i=2}^{\log_2n}(2^{i-1}-1)^{-2(\log_2n-i+1)}$

> 這個式子應該還是錯的
:::success
`jychen0611`

我算出來計算部分是對的

:::

> 計算是對的沒錯，而且 $((2^i-2)!)^2$ 還能跟下一項的 $((2^{(i+1)-1}-1)!)^2$ 相消
> 但是式子的假設本身是錯的
> 把他除以 n! 會發現在 n > 74 的時候超過 1 ，總排列數量也只有 n! 而已
> 不應該加上 $\binom{k-2}{\frac{k-2}2}$ ，因為分組的時候就包含了一部分的排列
> 下面的方法是對的，但是我沒辦法用他列出式子

數學所的朋友給了我一個生成的方法

1. 給定長度 n
2. 把 n 放在根節點
3. k 從 n-1 到 1：
選一個在樹上但高度還沒到底的數字 m
選擇把 m 的左右子節點設為 (k, m) 或 (m, k)
移除原本的 m

葉節點從左到右即為所求排列

程式部分可以用類似稀疏表或陣列線段樹的方式達成，節點從 1 開始
第 i 點的左子節點編號是 2i ，右子節點是 2i+1 ，遞迴嘗試所有可能
終止條件是遇到節點 n
但這樣的方式不好實作，另一種方式是紀錄每個點現在所在的位置，跑過 n 個點
> 注意到，這樣所生成的最差情況是對於 bottom-up merge sort 的
> top-down 會在中間切割，因此超過 $2^k(2^k\le n<2^{k+1})$ 的點不能都放在左邊
> 放的位置會是 $0,\frac n2,\frac n4,\frac {3n}4,\frac n8,\frac{3n}8,\frac{5n}8\frac{7n}8\cdots$
> 但是相對不好實作，先寫 bottom-up 的

為了達成泛型，每次生成一個代表每項順序的陣列後呼叫 `output` ，要傳入輸出函式的實作
傳給 `output` 的 `order` 陣列中，第 x 項代表 `order[x]` 要被放在第 x 個
`x=ans[order[x]]-log2(ans[order[x]])`
所以走訪 $n$ 個點，將第 i 個點放在 `order` 中的第 `ans[i]-highbit(ans[i])` 項
時間複雜度等於 n + 最差狀況的總數(還沒證出來是多少)
空間複雜度 $O(n+\log{n}),\log{n}$ 是因為遞迴呼叫函式

int without_highbit(int n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n >> 1;
}
void recur(int n, int *ans, int *order, int now, (void *ouput)(int *) )
{
    if (now < 0)
        return;
    for (int i = n; i > now; --i) {
        if (ans[n] >= n)
            continue;
        ans[i] = ans[n] <<= 1;
        ++ans[n];
        if (now == 1) {
            for (int j = 1; j <= n; ++j)
                order[without_high(ans[j])) = j;
            output(order);
        }
        else
            recur(n, ans, order, now - 1, output);
        ++ans[i];
        --ans[n];
        if (now == 1) {
            for (int j = 1; j <= n; ++j)
                order[without_high(ans[j])) = j;
            output(order);
        }
        else
            recur(n, ans, order, now - 1, output);
        ans[n] >>= 1;
    }
}
void all_worst_case(int n, (void *ouput)(int *) )
{  // print all case with n length
    int *ans, *order;
    do {
        ans = malloc(n * sizeof(int) * 2);
    } while (!ans);
    do {
        order = malloc(n * sizeof(int));
    } while (!order);
    ans[n] = n;
    recur(n, ans, order, n - 1, output);
    free(ans);
    free(order);
}

::: warning
上述程式碼要改進，每次呼叫給出一個新的 case ，並且併入 lab0 中
:::

---

## jimmy01240397

1. 延續 [jouae](#jouae) 可以直接在 26 個字元後面增加 6 個多的字元，當骰到這幾個字元時要做重抽。
問題：
1. 算 CDF（Cumulative Distribution Function）
2. 會有 Side channel attack 的問題（重抽導致執行時間不固定）
3. 最極端的情況可能會抽無限次 $\frac 6{36}\times\frac 6{36}\times\frac 6{36}\times\frac 6{36}\times\frac 6{36}\times \dots \times\frac 6{36}$
2. 如何確保隨機產生的測試案例涵蓋合併排序的最差或最好狀況
最好的情況，要產生遞減的資料列，如果是整數資料可以用 [Vincent550102](#Vincent550102) 的方法，如果要用字串的情況可以用以下程式。

    char *random_string();
    int random_int();
    char *new_string();

    char *list[5];
    list[0] = random_string();
    for (int i = 1; i < 5; i++) {
        int len = strlen(list[i - 1]) / 4;
        list[i] = new_string();
        ((int*)list[i])[len - 1] = ((int*)list[i - 1])[len - 1] - random_int();
    }

---

## Vincent550102

用以下 Python 程式即可產生嚴格遞增測試資料

:::warning
注意，python 的 random 模組是不安全的
https://docs.python.org/zh-tw/3.8/library/random.html
:::

[x:=x+__import__('random').randint(1,5) for _ in range(5)]

部分排序的測試資料，有 1/5 的機率會反序

[(rdint:=__import__('random').randint(1,15), x:=x+(rdint if rdint>3 else -rdint))[-1] for _ in range(20)]

---

## fennecJ

Ｑ ：我們的測試程式在檢驗 q_sort 時會給多少時間？
1 sec 。 可參見 `harness.c` 中的 `exception_setup()`

Ｑ ： harness 是什麼意思
安全/保護機制。

Ｑ ：目前程式需要確保每次使用 `exception_setup` 後接著使用 `exception_cancel` ，否則可能造成程式由於 TLE 而提前結束，有沒有辦法避免每次使用上都需要確保 `setup` , `cancel` 成對？

初步想法是可以使用一個 MACRO 來確保 `setup` , `cancel` 成對，舉例如下：

#define TLE_guard(code)\
exception_setup();     \
do{                    \
    code;              \
}                      \
while(0);              \
exception_cancel();    \

使用方式如下，即便程式碼出現分支也能使用：

int main()
{
    int a = 5;
	TLE_guard(
    if (a & 1)
        // code block
    else 
        // code block
 );

Ｑ ：解釋同步 / 非同步 / propagation delay 的概念。

### 同步
在數位電路中，同步指的是不同硬體的 output 會跟著同一個參考源（通常是 clk ）同時更新，即確保不同的硬體 **以相同的速度處理資料**
為何需要同步主要見於兩個目的：硬體間的溝通 以及 消除電子元件本身的非理想特性。
先談談硬體間的溝通。我們需要有一個方法確保不同硬體間能協調的交換資料，假設現在有兩個硬體 A, B 。 A 每秒可以生產 3 筆資料，而 B 每秒只能處理一筆資料，若直接將 A 和 B 接在一起，顯然會造成硬體無法順利運作。
我們必須想一個方法同步兩個硬體處理的速度，讓他們依據某個訊號同步更新資料。我們可以設一個週期為 1 秒的 clk ，讓 A, B 都根據 clk 的 posedge 更新資料，使兩硬體能順利運作。

:::info
posedge 指的是訊號從 0 -> 1 的瞬間，如下圖中 clock 的上升箭號。
:::

透過 clk 更新資料還有一個好處，就是電子元件本身並非理想的。若我們希望 A 能順利將資料寫到 B 這個硬體中， A 的 output 訊號必須要滿足兩個條件：
* A 的 output 需要在 clk posedge 到來的一段時間之前達到穩定，這段時間又叫做 setup time, 通常表示為 $t_{setup}$
* A 的 output 需要在 clk posedge 過後維持穩定一段時間，這段時間又叫做 hold time, 常表示為 $t_{hold}$

A 的 output 必須同時滿足 $t_{setup}$/$t_{hold}$ 的條件才能順利將值寫到 B 這個硬體中。

為什麼需要有這兩個時間？這是因為電子元件在充電/放電都是需要時間的，換句話說，要讓電子元件的狀態改變是需要時間的，詳情可見後面關於 Propagation Delay 的敘述。
另外，我們可以透過調整 clk 達成 $t_{setup}$ 的要求，換句話說，若 clk 的週期足夠長，則 A 在第一個 posedge 更新值之後，有更充裕的時間可以達到穩定。

而適當的 clk 還有一個重要的作用：在資料準備好後才更新值，也因此即便電子元件本身具有不理想的特性（需要時間更新狀態），它仍能看起來像是理想的，這也是為何我們可以在示波器上看到近乎垂直的方波。

### 非同步
非同步電路 Asynchronous circuit 又稱 (clockless or self-timed circuit) 。指的是不使用 clk 設計的序向電路。序向電路的嚴格定義是電路任何時刻的穩態輸出不僅取決於當前的輸入，還與前一時刻輸入形成的狀態有關，也就是具有記憶功能的電路設計。

前面提到要同步 A, B 兩種硬體。需要讓運作比較快的 A 去等較慢的 B ，顯然這種作法會犧牲 A 本身的運作速度。而非同步電路的好處就是有機會可以讓電路彼此都以自己最好的速度運作。非同步電路通常會藉由設計 handshake 訊號來和不同硬體溝通，透過 handshake 訊號表達電路以完成運作。
但是非同步電路設計上遠比同步電路困難且容易出錯，且同步電路中快的硬體要等慢的硬體這件事可以透過適當的切 pipeline 的方式解決，因此現在主流的數位電路都是設計為同步電路。

### Propagation Delay （by millaker）
> 引述 Sedra Smith 電子學 Digital Design: Power, Speed, and Area :
> The speed of operation of a digital system (e.g. a computer) is determined by the propagation delay of the logic gates used to construct the system. Since the inverter is the basic logic gate of any digital IC technology, the propagation delay of the inverter is a fundamental parameter in characterizing the speed of a given technology.
> ...
> The propagation delay is the time the inverter takes to respond to a change at its input.

電子系統的電路中有大大小小的電容，而真實世界電容充電與放電都需要時間，可以從電容公式得知:
$$Q = CV$$
$$\Delta Q=C \Delta V$$
電容值 $C$ 由材料、形狀決定，電量改變量 $\Delta Q$ 可以由固定電流得到
$$ I\Delta t = \Delta Q = C \Delta V$$

Propagation Delay 就是為了達到我們需要的電壓所需的 $\Delta t$。下面這張圖上方是一個輸入訊號，下方是非理想 Inverter 的響應圖，可以看到訊號不再是完美的脈衝，而是平滑圓角且需要花費一定時間才能到達 $\frac{V_{DD}}{2}$

所有的基礎邏輯閘像是 NOR, XOR, NAND ... 都有自己的延遲，若今天設計的電路很小，像是半加器、4位元加法器，
可能還可以用手算出整個電路的延遲，但是電路如果複雜到例如 CPU、DSP，我們很難推算何時可以在輸出端取樣到想要的結果，因此才會需要時鐘訊號來同步各電路的運行，保證在時鐘訊號改變時能夠取樣到正確結果。

---

### RRbell1027
比較 Fisher-Yate shuffle 演算法在輸入之序列為陣列和鏈結串列下，時間複雜度是否會增加？

* Fisher-Yate shuffle 演算法將輸入的序列洗牌的過程中，會對序列元素進行檢索和移動。
* 比較陣列與鏈結串列的不同：（$N$ 為序列長度）

| | 陣列 | 鏈結串列 |
|:--------------------:|:--------:|:----------:|
| 儲存方式 | 空間連續 | 空間不連續 |
| 元素檢索的時間複雜度 | O(1) | O(N) |
| 元素移動的時間複雜度 | O(N) | O(1) |

* 當初只考慮到元素檢索，因此誤判 Fisher-Yate shuffle 使用鏈結串列作為輸入序列的資料結構時時間複雜度會上升。實際上相同。

Fisher-Yate shuffle 演算法所有排列機率是否相同？
測試 10000 次，將結果利用 Pearson's chi-squared test 檢驗以下虛無假說：
* $H_0$ : shuffle 結果發生的機率相同
* $H_1$ : 存在至少一個結果機率與其他不同

執行結果：

* chi square sum: 22.480769230769237
* 由於結果有 24 種 ，自由度為 23
* 查卡方表得知，P value 介在 0.9 - 0.1 之間，超過閥值(0.05)
* 因此判斷**結果不拒絕虛無假說**

當初並未看完筆記說明直接做實驗，所以不清楚證明所需的統計運算。

### kkkkk1109

為何使用 t-test 而非其他統計方法

首先，此一論文是為了測試程式是否能夠在常數時間內完成，且不侷限特定平台也可完成。論文中所比較的是兩個不同的類別 `fix` vs `random` ，來比較在不同輸入的情形下，執行多次後，兩者的平均值是否有差異。

常見的檢定方式有 [Z-test](https://en.wikipedia.org/wiki/Z-test)和 [T-test](https://en.wikipedia.org/wiki/Student%27s_t-test)， Z-test 建立在樣本數夠大，且已有母體的變異數，才會使用 Z-test。而在此論文中，母體的變異數是無法取得的，因此無法使用 Z-test。

T-test 主要分為以下:
* One-sample t-test: 是用來檢測母體的平均值是否為預設的特定值
* Two-sample t-tests: 是用來測量兩個群組的平均值是否有差異
* Paired-tests: 是對於同個群組，兩次不同測量的平均值是否有差異

該注意的是 Two-sample t-tests 的使用也有限制，若兩群組的大小、變異數相同，可以使用此 T-test，但在大小和變異數不同的情況下，則使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)。此論文中提到，會對資料進行 Cropping，來去除極端值，因此可以假定兩群組的數量不一定相同，因此使用 Welch's t-test 來進行測量。

### steven523
list sort 與一般 merge sort 的效能差異？

在用 [Perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 比較完兩者效能後，發現 list sort 在 cache-misses 和 branches 次數比較少。

從 cache-misses 方面來說，list sort 除了實作 bottom up 的算法之外，它相較於一般 merge sort 擁有更有效利用 cache 的合併方式，合併時機是當有 $3 \times 2^k$ 個節點時會合併前兩個 $2^k$，使其維持著合併：不合併為 2：1 的比例，這樣更能實作空間局部性 (Spatial locality)。
>空間局部性：當一個記憶體區塊被載入 cache 時，相鄰的區塊也很可能會被載入。

list sort 的合併方式可以使 cache 中現存的資料更容易被使用到，進而減少 cache-misses，降低執行時間 ; 而 merge sort 通常需要額外的記憶體空間來儲存很多個子串列，然後一次合併，這時通常會發生很多 cache-misses，在空間局部性的表現上較差，甚至導致 cache trashing。

從 branches 方面來說，list sort 是使用迭代的算法，它通常較少涉及到函式的重複呼叫，只透過循環來完成任務，這相較於 merge sort 遞迴的算法 branches 次數會更少，因為遞迴的本質是將大問題分解成小問題，但這會重複呼叫同個函式比較多次。

### yenshipotato
q_sort is stable?

Stable : Sorting algorithms maintain the relative order of records with equal keys. （排序演算法會維持相同鍵值節點的相對順序）
而在執行合併的函式 `merge` 裡，在呼叫 `cmp` 時，不區分小於和等於的情況，意即順序在前的節點無論值小於或等於順序在後的節點，皆不會交換位置，依此便可以維持排序的穩定。

qtest

在新的佇列裡插入數個鍵值相同的節點，接著建立另一個佇列依序存放原佇列個節點的位址，經排序後再走訪兩個佇列以比對，若排序後的佇列各節點的位址順序沒有改變，則此排序即是穩定排序。

### ChenFuhuangKye
#### 如何加強 merge sort 的效能
對於效能改進而言， locality of reference 十分重要，它指的是短時間內重複存取相同的記憶體位置， Linux 核心的 `lib/list_sort.c` 使用了對於 cache 更友善的 Bottom-up 方法進行排序，這個過程主要通過不斷的合併來進行，從而提高 cache 被參照的機會，這樣做可以有效提高 merge sort 的效能。

### Wu-Cheng Chiang
以 linenoise 和 lab0-c 內建 web 命令的實作，探討二者事件處理的衝突和解決方法。

### Petakuo
#### quick sort 和 merge sort 相比的 locality

Locality : 首先，必須先了解 cache 儲存指令或資料的特性，由於 cache 的目的在於讓暫存器更快速的抓取內容，且在使用資料後高機率會接著使用該資料附近的資料，因此當 cache 在記憶體中抓取資料時會同時將該位址附近的資料一併抓取，以達到減少記憶體存取的次數，進而加速暫存器的存取速度。而 localiy 則用來描述撰寫的程式碼是否符合 cache 的此一特性，符合則帶表該程式碼的 locality 較好，其中， locality 又分為以下兩種 :
* Temporal locality : 之前被使用過的資料會再度被使用
在以下程式碼中，由於 `i` 不斷的被取出並更新，因此的記憶體位址一直被重複使用，為一種 temporal locality 。
* Spatial locality : 該資料位址附近的資料會被使用
對於陣列 `a` 而言， cache 會有順序的存取記憶體的下一個位址，為一種 spatial locality 。

void KOneArray(int a[], int k){
    for(int i = 0; i < k; i++){
        a[i] = 1;
    }
}

| | Quick sort | Merge sort |
| - | - | - |
| Temporal locality | 對於相同的子問題會利用遞迴進行多次處理，皆是從同樣的記憶體區塊做更新，因此擁有良好的 temporal locality | 對於子序列的合併使用遞迴的方式，會重複使用合併後的資料再次與其他資料合併，同樣擁有良好的 temporal locality |
| Spatial locality | 為一種 in-place algorithm ，不需要額外的資料結構或空間來達到變換資料的效果，並且在尋找要被交換的位置時會依序由頭尾兩端搜尋，因此擁有良好的 spatial locality | 通常需要額外的空間來存儲子序列，並且在合併時也需要暫存的空間來進行操作，因此在 spatial locality 的表現上較差 |

整體來說， Quick sort 的 locality 較 Merge sort 好一些。
> 但 merge sort 的變形亦可做到 in-place (如 Linux 核心的 lib/list_sort.c)，針對 in-place merge sort 討論其 locality

#### 變形後的 merge sort

以 Linux 核心的 lib/list_sort.c 為例，該演算法利用了指標的改變來對鍊結串列的進行排序，並且以 bottom up 的方式來實作 merge sort ，這樣的好處有
* 不需要使用遞迴 : 減少使用額外的 stack 來保存函數的返回地址，可節省記憶體並提高效率。
* 擁有較好的 spatial locality : 排序的過程是按照子序列的順序進行的，因此相鄰的子序列在記憶體中也是相鄰的，有助於加速 cache 的存取。
* 為 in-place 演算法 : 利用了指標的改變進行排序，並且不需要額外的資料結構支援即可在原地達到排序的效果。

| | Quick sort | In-place Merge sort |
| - | - | - |
| Temporal locality | 以遞迴的形式處理子問題，擁有良好的 temporal locality | 雖然捨去使用遞迴，但由於都是對同一鏈結串列進行操作，因此在 cache 中使用的位址相同，擁有良好的 temporal locality |
| Spatial locality | 若是 pivot 的選擇不當，可能會造成分區後的子序列大小差異太大，進而降低 spatial locality | 不論何種情況，皆會以相鄰的子序列進行合併排序，因此 spatial locality 相對穩定 |

整體來說， in-place merge sort 的 locality 相對穩定，而 quick sort 則取決於 pivot 的選擇以及串列的原始排序。

#### 為何要在 Linux 核心探討 inplace

### devarajabc

探討 [min-max heap](https://en.wikipedia.org/wiki/Min-max_heap) 在 linux 核心的應用。

在正式探討其應用之前，我們要先了解 [min-max heap](https://en.wikipedia.org/wiki/Min-max_heap) 的一些特性：
1. 能快速存取和刪除最小和最大元素
2. 為完全二元樹
3. 節點的層級交替地表示最小堆和最大堆層
4. 時間複雜度：

| 操作 | 時間複雜度 |
| :----------------------- | :-------- |
| 插入操作（Insertion） | $O(\log{n})$ |
| 刪除最小值（Delete Min） | $O(\log{n})$ |
| 刪除最大值（Delete Max） | $O(\log{n})$ |
| 搜尋最小值（Find Min） | $O(1)$ |
| 搜尋最大值（Find Max | $O(1)$ |

4. 空間複雜度 : $O(n)$

[min-max heap](https://en.wikipedia.org/wiki/Min-max_heap) 常用以實作 priority queue。

然而這與 linux 核心的關係為何呢？
> 先研讀 [include/linux/min_heap.h](https://github.com/torvalds/linux/blob/master/include/linux/min_heap.h) 的應用案例，接著會發現變形

## yenslife

檢測 q_sort 是否為穩定排序

> [PR #177: Check if sorting implementation is stable](https://github.com/sysprog21/lab0-c/pull/177)

一開始是因為老師在共筆問我要怎麼確保自己的 merge sort 是穩定排序，我就想說對誒好像都沒想過這個問題，於是修改 `qtest.c` 來觀察，結果我的 `q_sort` 還真的不是穩定排序 (wtf!)。Merge sort (top down) 只會在比大小後交換，所以分清楚 `>`, `>=` 就很重要，只可惜我忽略了，覺得只要有遞增或遞減的效果就好。

### 作法 1：在 `element_t` 加入成員來檢測

較直覺的作法是直接在 `element_t` 中加入一個編號成員，insert 同時更新編號，從 0 開始遞增。但這樣會遇到一個問題，遇到 `reverse`, `reverseK` 等會更改節點順序的命令時，節點的相對順序便不可考。

typedef struct {
    char *value;
    struct list_head list;
+   unsigned no;
} element_t;

比較好的作法是，在 `do_sort` 的 `q_sort` 執行之前才為節點編號，最後透過比較編號大小來檢測相同值的節點順序。

為確保所有相同值節點的相對順序都沒有被更動，比較所有相鄰的節點，共 $n-1$ 次比較 (或許可以更少？)

缺點是動到 `queue.h`，但我們不希望如此，希望只修改 `qtest.c`

### 作法 2：用額外的資料結構來檢測

原先的想法是將節點複製到額外的結構體，並為複製的節點加上編號，但越寫越不對勁，這樣還不如直接修改 `element_t` 的結構。

所以我建立了一個指標陣列來紀錄排序前的節點位址，並找出相同值的兩個節點在陣列中的索引編號。如果還是用比較索引大小的方式來實作可能導致 $2*O(n-1)$ 迭代次數，事實上只要看相同值的兩個節點誰先出現即可，比較次數為 $O(n-1)$。

#define MAX_NODES 100000
    struct list_head *nodes[MAX_NODES];

為什麼要設定 `MAX_NODES` 呢？我希望涵蓋所有 `traces/` 裡的測試資料，但發現在 `traces/trace-14-perf.cmd` 有多達 2000000 的節點的佇列要排序，陣列在初始化空間的時候會導致 segmentation fault，所以我就放棄這個測試，轉頭找向第二大的 `traces/trace-15-perf.cmd`，雖然是隨機值而不是重複值的 100000 個節點。

為了讓 100000 這個數字不要這麼像憑感覺冒出來的，我做了個簡單的測試：插入 [node count] 個相同值的節點，排序，觀察花費的時間。

| node count | elapsed time (seconds) |
| ---------- | ---------------------- |
| 1000 | 0.027906238 |
| 10000 | 0.058188249 |
| 100000 | 2.445569385 |
| 150000 | 5.453358783 |
| 200000 | 9.671944194 |
| 300000 | 21.581793918 |
| 400000 | 40.176436261 |
| 500000 | 61.437037665 |

可以發現當相同值的節點數超過 100000 個之後的花費時間有顯著的增長。

當然我覺得這個做法還可以更好，例如先找出相同值的節點，然後將節點依序放入陣列中，但實作上可能會比較複雜。

善用 `git rebase -i`