yue-jenny / yue-jenny.github.io Goto Github PK

https://yue-jenny.github.io/2023/02/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E7%AD%86%E8%A8%98%E5%85%AD-rate-limiting/

https://yue-jenny.github.io/data-structure/balance-tree-avl-tree/

平衡樹 平衡樹（Balanced Tree）是一種在資料結構中用於儲存和組織資料的二元樹（Binary Tree），其特點是保持樹的平衡，以確保在插入、刪除和查詢等操作上有較好的效率。
AVL樹 AVL樹是最早提出的自平衡二元搜尋樹。它通過維護每個節點的平衡因子(左子樹高度減去右子樹高度)在每次插入或刪除操作後進行調整，以確保樹保持平衡。
AVL 樹由 Georgy Adelson-Velsky 和 Evgenii Landis 於 1962 年提出的一種自平衡二元搜尋樹。
它的平衡性通過維護每個節點的平衡因子（Balance Factor）來確保，該平衡因子表示左子樹高度減去右子樹高度的差值。
當在AVL樹中進行插入或刪除操作時，可能會破壞樹的平衡。
在這種情況下，需要通過旋轉操作來恢復平衡。旋轉操作分為左旋和右旋兩種：
左旋：當某個節點的右子樹高度過高時，進行左旋操作可以降低右子樹高度，同時提升該節點的左子樹高度。 右旋：當某個節點的左子樹高度過高時，進行右旋操作可以降低左子樹高度，同時提升該節點的右子樹高度。 這些旋轉操作的目的是保持樹的平衡，使得樹的高度始終保持在O(log n)的範圍內。儘管AVL樹提供了較嚴格的平衡性，但相對而言，它需要更多的旋轉操作，因此插入和刪除的成本較高。
以下是 AVL 樹進行平衡的規則 AVL 樹在插入或刪除節點後，可能會失去平衡，也就是某些節點的左子樹和右子樹的高度差超過 1。為了維護 AVL 樹的平衡性，我們需要進行旋轉操作。
左旋轉（Left Rotation）： 條件：當一個節點的右子樹比左子樹高度多 2 層或以上時，我們進行左旋轉操作。 作法：左旋轉可以將該節點的右子樹提升為新的根節點，同時將原根節點降低為新根節點的左子樹。這樣可以保持左子樹和右子樹的高度差不超過 1。 右旋轉（Right Rotation）： 條件：當一個節點的左子樹比右子樹高度多 2 層或以上時，我們進行右旋轉操作。 作法：右旋轉可以將該節點的左子樹提升為新的根節點，同時將原根節點降低為新根節點的右子樹。這樣可以保持左子樹和右子樹的高度差不超過 1。 左右旋轉（Left-Right Rotation）： 條件：當一個節點的左子樹比右子樹高度多，且該節點的左子樹的右子樹比左子樹的左子樹高度多時，我們進行左右旋轉操作。 作法：先對該節點的左子節點進行左旋轉，然後對原節點進行右旋轉。 右左旋轉（Right-Left Rotation）： 條件：當一個節點的右子樹比左子樹高度多，且該節點的右子樹的左子樹比右子樹的右子樹高度多時，我們進行右左旋轉操作。 作法：先對該節點的右子節點進行右旋轉，然後對原節點進行左旋轉。 這些旋轉操作可以調整 AVL 樹的結構，使其保持平衡。在進行插入或刪除操作後，我們需要檢查節點的平衡因子，即左子樹高度減去右子樹高度。
如果平衡因子大於 1，表示左子樹高於右子樹，則需要進行右旋轉或左右旋轉； 如果平衡因子小於 -1，表示右子樹高於左子樹，則需要進行左旋轉或右左旋轉。 通過這些旋轉操作，我們可以保持 AVL 樹的平衡性。
實作 class AVLNode { constructor(value) { this.

https://yue-jenny.github.io/2023/01/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E4%B8%89-mapreduce/

MapReduce 前言 MapReduce 是一個 Google 提出的軟體架構，適用於大規模資料的並列運算
Prerequistites File System 資料的儲存系統 有許多不同型態，例如以垂直結構為主的目錄與資料夾、Object storage 等 Distributed File System 分散式檔案系統，透過一大群機器(cluster)互相合作，對外表現如同一個巨大的 file system，將 data 切成特定大小的 chunks (如 4 MB 或 64 MB)，會透過 central control plane 會決定應該將 chunks 存在哪一個 node，後續應該去哪一個 node 讀取 chunks 主要操作方式是透過網路以定義好的通訊協定進行資料存取 目前現有的產品有 Google File System (GFS)、Hadoop Distributed File System (HDFS) Hadoop 支持 MapReduce 與資料管線的 open-source 框架，最重要的**組件為 Hadoop Distributed File System (HDFS) 各階段簡介 Map 階段 負責 filtering 和 sorting 並且組合出一個 key value pair 結果 Reduce 階段 負責資料整合 以 wordcount 為例，從 Map 傳過來的 key 若一樣，表示同一個字，因此把一樣的 key 做加總，可以得出最後的出總筆數 冪等性(idempotency)特性 意義: 當操作多次，結果應呈現一致 透過 pub/sub messaging system 應當有冪等性，因為 pub/sub 系統本身允許相同訊息被 consumer 接收多次 舉例，增加資料庫某欄位的 integer value，就不是一個具有冪等性的操作，因為保持每次增加的操作後都不會保持跟前一個相同的數值 另一舉例，將欄位值設定為 “DONE”，多次重複此操作，還是會顯示為 “DONE”，因此設定為 “DONE” 是一個冪等性操作 範例 input 要做計算的原始資料，可以是一堆文字清單等 split 把 input 資料做分散處理 以 hadoop 來說，當 MapReduce 工作被輸入的時候，會被切割到各個 cluster 裡面等待做處理 🔔map MapReduce 的 map 階段 每一個節點有自己的一份資料要分析，會把對應切割出來的資料建立 key value 的結果 key 是字本身，value 是 1 代表找到一筆 combine 在 map 的機器進行以下動作 將一樣的 key 先做一次加總，避免傳送多次出去，例如 combine 後的結果可能是 “A” 有 2 筆、“B” 有 1 筆等 shuffle & sort 在進入 reduce 階段之前，會先被做一個排序，因此相關的 key 會放在一起 比如第一批資料的 “A” 有 2 筆、第二批資料的 “A” 有 5 筆…第一批資料的 “B” 有 1 筆、第二批資料的 “B” 有 3 筆 🔔reduce 此階段會做實際的加總，因此每一個 key 的 value 會被加總 output 最後得到的結果 參考資料 👐 system expert wiki MapReduce introduction-to-mapreduce 🍀 最後，若喜歡我的分享，可以幫我拍拍手👏，是對我最大的鼓勵!

https://yue-jenny.github.io/system-design/lfu-cache/

介紹 LFU（Least Frequently Used）快取是一種用於緩存（cache）中數據替換的算法。
它的基本**是，當緩存空間不足時，優先移除那些最少被使用的數據，以便為新的數據騰出空間。
LFU快取跟其他替換算法（如LRU）不同，它不僅考慮數據的訪問頻率，還考慮了每個數據的實際使用次數。每當數據被訪問時，其相應的使用計數器會增加。當緩存空間不足時，LFU快取將選擇使用計數器值最小的數據進行替換。
以下是LFU快取的基本操作流程：
初始化：設定緩存的最大容量和空的緩存數據結構。 存儲數據：當數據要存入緩存時，首先檢查數據是否已存在於緩存中。如果是，則增加相應的使用計數器值；如果不是，則將數據添加到緩存中並將其使用計數器初始化為1。 訪問數據：當數據被訪問時，相應的使用計數器增加1。 替換數據：當緩存空間不足時，找到使用計數器值最小的數據進行替換。如果有多個數據具有相同的最小使用計數器值，則選擇最早被存儲的那個進行替換。 更新緩存：如果緩存中的數據發生變化（新增、訪問或替換），需要相應地更新緩存數據結構。 LFU快取的優點是能有效地保留那些被頻繁訪問的數據，並且在緩存空間不足時優先替換那些較少使用的數據，從而提高緩存的效率。然而，LFU快取也有一些限制，例如計數器可能受到訪問模式的影響，並且需要額外的存儲空間來維護使用計數器。因此，在實際應用中，需要仔細考慮數據訪問模式以及性能和存儲要求等因素，選擇最適合的緩存替換算法。
實作 class Node { constructor(key, value) { this.key = key; this.value = value; this.frequency = 1; this.prev = null; this.next = null; } } class DLinkedList { constructor() { // 建立兩個 node，分別為 head 與 tail this.head = new Node(null, null); this.tail = new Node(null, null); // head 的 next 指標指向 tail this.head.next = this.tail; // tail 的 prev 指標指向 head this.

https://yue-jenny.github.io/2023/01/%E4%BD%BF%E7%94%A8-docker-desktop-%E9%81%8B%E8%A1%8C-argo-cd/

https://yue-jenny.github.io/2023/01/%E5%9C%A8-argo-cd-%E4%B8%AD%E4%BD%BF%E7%94%A8-github-app-credential-%E4%BD%9C%E7%82%BA%E9%A9%97%E8%AD%89%E6%96%B9%E5%BC%8F/

https://yue-jenny.github.io/algo/josephus-problem/

介紹 約瑟夫問題（Josephus Problem）是一個古老的數學問題，其名稱源自於猶太歷史學家弗拉維奧·約瑟夫斯（Flavius Josephus）。這個問題描述了一個關於生存和順序的遊戲。
問題的背景是這樣的：假設有N個人（編號從1到N）站成一個圓圈狀。一開始，從第一個人開始按照順時針方向報數，報到第M個人就將其移出圈子，然後再從下一個人開始重新報數，如此重複，直到只剩下一個人為止。
問題的目標是找到最後生存下來的那個人的編號。即，如果N=7，M=3，那麼經過一輪報數和移除操作後，順序會變成3，6，2，7，5，1，最後剩下的是4號。
約瑟夫問題並不僅限於具體的數字，而是一個普遍的抽象問題，可以用數學方式來解決。解決這個問題的一種經典方法是使用遞迴（recursion）。
基於遞迴的解法如下：
如果只有一個人（N=1），那麼他就是最後的生存者，回傳他的編號。 否則，從第一個人開始報數，並將每個第M個人移除。 移除完畢後，從下一個人開始重新遞迴調用這個過程（N-1個人）。 將遞迴返回的結果（即下一輪的最後生存者編號）調整到當前的編號對應的位置，然後回傳結果。 這樣，通過不斷遞迴和移除操作，最後得到的結果就是約瑟夫問題的解。
需要注意的是，約瑟夫問題的解並不唯一，它取決於初始的N和M的值。這個問題在數學和計算機科學中都有廣泛的應用，包括編程、遊戲理論等領域。
李永樂老師的講解 Youtube 影片
紀錄 先介紹了當k=2時的基本情況，然後討論了更一般的情況。
影片提供了遞推式來解決這個問題，將最後剩下的人表示為f(N, k)，其中N表示最初的人數，k表示每隔多少人殺一個。
他們的編號不同，例如原先的4號現在成了1號，原先的5號現在成了2號，原先的6號現在成了3號。這意味著他們的編號相差3。這個差值3正好對應到每隔幾人殺一個的k值。因此，我們需要將這個差值加上k，這樣新的編號就會與原先的編號相同了。
影片解釋了遞推式的計算過程，並提到如果計算結果大於N，則需要減去N，相當於去取餘數。
最後給予一個範例呈現。
N = 8，總共 8 個人。
K = 3，每隔 3 個人殺一個。
最後生存者是 7 號。
流程圖 若想要清楚流程圖，大力推薦參考資料【Josephus Problem - GeeksforGeeks】
當 N = 5, K = 1 時候的流程圖。最後生存者是 3 號。
實作 // return the position of last man survives function Josephus(n, k) { let i = 1; let ans = 0; while (i <= n) { // update the value of ans ans = (ans + k) % i; // 再進行下一個 i i++; } // 編號從 1 開始 return ans + 1; } // This code is contributed by sarveshc111.

https://yue-jenny.github.io/2023/01/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E5%9B%9B-publish/subscribe-pattern/

Publish/Subscribe Pattern Publish/Subscribe Pattern (Pub/Sub) 簡介 一種包含 publisher、subscriber 與 broker 的訊息模型 publisher - 將訊息傳送至特定 topic(也可能被稱呼為 channels)，不需要擔心誰需要收到這筆消息 subscriber - 訂閱特定 topic 後，將會收到來自此 topic 的訊息 broker - 負責將 topic 的訊息轉發給 subscriber 通常有以下的保證，如「至少傳送一次」、「持久化」、「訊息的順序性」、「訊息可重送多次」 相同訊息可重送多次，但不能影響結果，符合冪等性(idempotent) 有哪些 Pub/Sub 服務? 這邊舉幾個服務
RabbitMQ 最廣泛使用的 message broker，特色是輕量級輕鬆部屬，但也有支援 distributed 以符合 high-scale 與 high-availability 的要求 點我看更多👀 Apache Kafka 最先是由 LinkedIn 創立的一款分散式訊息系統 (distributed messaging system)，由 Scala 和 Java 編寫的 open-source 專案，點我看更多👀 雲端受託管版本的 Kafka - Confluent Cloud (Cloud Native Apache Kafka®)，點我看更多👀 Cloud Pub/Sub Google 創立的雲端 Pub/Sub 服務，可用於串流服務、非同步微服務整合。點我看更多👀 參考資料 👐 system expert wiki - Kafka publisher-subscriber pattern 🍀 最後，若喜歡我的分享，可以幫我拍拍手👏，是對我最大的鼓勵!

https://yue-jenny.github.io/2023/01/mapreduce/

MapReduce 前言 MapReduce 是一個重要的概念，
Prerequistites File System 資料的儲存系統 有許多不同型態，例如以垂直結構為主的目錄與資料夾、Object storage 等 Distributed File System 分散式檔案系統，透過一大群機器(cluster)互相合作，對外表現如同一個巨大的 file system，將 data 切成特定大小的 chunks (如 4 MB 或 64 MB)，會透過 central control plane 會決定應該將 chunks 存在哪一個 node，後續應該去哪一個 node 讀取 chunks 主要操作方式是透過網路以定義好的通訊協定進行資料存取 目前現有的產品有 Google File System (GFS)、Hadoop Distributed File System (HDFS) Hadoop 支持 MapReduce 與資料管線的 open-source 框架，最重要的**組件為 Hadoop Distributed File System (HDFS) 各階段簡介 Map 階段 負責 filtering 和 sorting 並且組合出一個 key value pair 結果 Reduce 階段 負責資料整合 以 wordcount 為例，從 Map 傳過來的 key 若一樣，表示同一個字，因此把一樣的 key 做加總，可以得出最後的出總筆數 冪等性(idempotency)特性 意義: 當操作多次，結果應呈現一致 透過 pub/sub messaging system 應當有冪等性，因為 pub/sub 系統本身允許相同訊息被 consumer 接收多次 舉例，增加資料庫某欄位的 integer value，就不是一個具有冪等性的操作，因為保持每次增加的操作後都不會保持跟前一個相同的數值 另一舉例，將欄位值設定為 “DONE”，多次重複此操作，還是會顯示為 “DONE”，因此設定為 “DONE” 是一個冪等性操作 範例 input 要做計算的原始資料，可以是一堆文字清單等 split 把 input 資料做分散處理 以 hadoop 來說，當 MapReduce 工作被輸入的時候，會被切割到各個 cluster 裡面等待做處理 🔔map MapReduce 的 map 階段 每一個節點有自己的一份資料要分析，會把對應切割出來的資料建立 key value 的結果 key 是字本身，value 是 1 代表找到一筆 combine 在 map 的機器進行以下動作 將一樣的 key 先做一次加總，避免傳送多次出去，例如 combine 後的結果可能是 “A” 有 2 筆、“B” 有 1 筆等 shuffle & sort 在進入 reduce 階段之前，會先被做一個排序，因此相關的 key 會放在一起 比如第一批資料的 “A” 有 2 筆、第二批資料的 “A” 有 5 筆…第一批資料的 “B” 有 1 筆、第二批資料的 “B” 有 3 筆 🔔reduce 此階段會做實際的加總，因此每一個 key 的 value 會被加總 output 最後得到的結果 參考資料 👐 system expert 🍀 最後，若喜歡我的分享，可以幫我拍拍手👏，是對我最大的鼓勵!

https://yue-jenny.github.io/2023/01/github-%E7%9A%84-oauth-app-%E4%BB%8B%E7%B4%B9-%E4%B8%80/

https://yue-jenny.github.io/2022/12/%E5%9C%A8-github-workflow-%E4%B8%AD%E4%BD%BF%E7%94%A8-openid-connect-oidc-%E5%8E%BB%E8%AA%8D%E8%AD%89-aws-%E6%9C%8D%E5%8B%99/

OpenID Connect (OIDC) 介紹 前言 OIDC 全名為 OpenID Connect

https://yue-jenny.github.io/2023/01/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E4%BA%8C-cache/

Cache 快取 前言 快取對於系統層面上相當重要，用的好、用的巧，有助於整體系統的順暢度。
因此目標是了解👉為什麼使用、👉使用策略與👉何時使用。
Prerequistites cache 意思是將一部分的資料儲存起來，需要使用的時候，不需要經過後端或者資料庫再拿一次，優勢是取得資料較快 通常使用的情境是將常用且不經常修改的 response 儲存，不必每次都去跟後端與資料庫請求 cache hit 需要的資料能在快取中找到 🉐 cache miss 需要的資料無法在快取中找到 🈚 content delivery network (CDN) 一種第三方服務，扮演的角色就像快取，為什麼呢 ? 請往下看 越來越多服務的據點散布全球🌏，若 server 只有在幾個國家，其他國家的使用者可能會遇到網頁轉很久等問題⌛，中間網路傳輸耗時太長導致 latency 長，此時若有散布全球的 CDN server，請求就能先傳送到 CDN server 處理，縮短 latency 舉例一些 CDN 廠商，如 Cloudflare 與 Google cloud CDN 3 個使用快取的目的 利用前端快取，減少請求到後端 減少對資料庫的請求，降低資料庫壓力 避免 long compute operation，增加系統速度 快取更新機制 write through cache 同時更新資料庫與快取的資料 write back cache 先更新快取，再以非同步的方式更新資料庫的資料 快取替換機制 Cache eviction policy Least Recently Used (LRU) 依照最近使用時間來排序 思路: 最近使用時間最接近，表示近期內使用到的可能性也越高 優先替換掉最近使用時間距離當下最遠的那組數據 Least Frequently Used (LFU) 依照使用頻率來排序 思路: 使用次數越高⬆️，表示近期內使用到的可能性也越高⬆️ 優先替換掉使用次數最低的那組數據 First in First out (FIFO) 顧名思義，先進先出 思路: 最先進去快取的資料，越早會被淘汰 參考資料 👐 System expert 🍀 最後，若喜歡我的分享，可以幫我拍拍手👏，是對我最大的鼓勵!

https://yue-jenny.github.io/2023/01/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E4%BA%94%E7%AD%86%E8%A8%98-logging-and-monitoring/

https://yue-jenny.github.io/leetcode/289-game-of-life/

題目連結 289 Game of Life
題目說明 這道題目是一個模擬遊戲，稱為康威生命遊戲（Conway’s Game of Life）。遊戲的主要元素是一個由細胞組成的網格，每個細胞可以是活著的（用1表示）或死亡的（用0表示）。
遊戲的規則非常簡單，每個細胞與其周圍的八個鄰居（水平、垂直和對角線方向）進行交互作用，根據以下四條規則來決定下一個時刻的狀態：
如果一個活細胞周圍的活細胞少於兩個，則該細胞會因為人口不足而死亡。 如果一個活細胞周圍有兩個或三個活細胞，則該細胞在下一代中繼續存活。 如果一個活細胞周圍的活細胞超過三個，則該細胞會因為人口過剩而死亡。 如果一個死細胞周圍正好有三個活細胞，則該細胞會因為繁殖而成為活細胞。 下一個時刻的網格狀態是通過同時應用上述規則到當前時刻的每個細胞上來生成的，出生和死亡是同時發生的。題目給定了當前網格的狀態 board，要求返回下一個時刻的狀態。
換句話說，你需要根據上述規則對 board 中的每個細胞進行計算，並根據規則更新其狀態。最終返回更新後的網格狀態。
解題思路 首先解釋一下生命遊戲的規則。生命遊戲在一個二維格子中進行，每一個格子代表一個生命體，這個生命體有兩種狀態：生(1)和死(0)。
每個生命體的生死由其周圍八個格子的生命體狀態決定，規則如下：
如果一個生命體周圍有少於2個生命體，該生命體在下一輪會死亡。 如果一個生命體周圍有2個或3個生命體，該生命體在下一輪會保持當前狀態。 如果一個生命體周圍有超過3個生命體，該生命體在下一輪會死亡。 如果一個死亡的生命體周圍有正好3個生命體，該生命體在下一輪會復活。 程式碼中的gameOfLife方法用來進行一次遊戲的迭代。
它首先遍歷每一個生命體，並對其周圍的生命體進行計數(countLive方法用來計算周圍的生命體數量)。
根據計數的結果，然後決定每一個生命體在下一輪的狀態。
為了避免在計數過程中被即時更新的狀態影響，
這個方法選擇了一種巧妙的方式，使用兩個中間狀態：live(3)代表從死亡狀態變為生存，die(2)代表從生存狀態變為死亡。
這種方式可以讓我們在遍歷並更新狀態時，仍然可以正確計數周圍原來的生命體數量。
在完成狀態更新後，程式碼再次遍歷每一個生命體，將之前設置的中間狀態轉換回最終的生或死狀態。
這樣，我們就完成了生命遊戲的一次迭代。
實作 /** * @param {number[][]} board * @return {void} Do not return anything, modify board in-place instead. */ let die = 2; let live = 3; var gameOfLife = function (board) { let rowslength = board.

https://yue-jenny.github.io/2023/01/cache/

https://yue-jenny.github.io/2023/02/pulling-and-streaming/

https://yue-jenny.github.io/2023/01/%E4%BD%BF%E7%94%A8-docker-desktop-%E9%81%8B%E8%A1%8C-argo-cd-%E4%BB%A5%E5%8F%8A%E5%9C%A8-argo-cd-%E5%85%A7%E5%BB%BA%E7%AB%8B-app-%E5%81%B5%E6%B8%AC-repository-%E7%8B%80%E6%85%8B/

Prerequisites 開始前，需要先確保有以下的先備知識
kubernetes Argo CD 介紹 以 GitOps 模式為宗旨的持續部屬 (continuous delivery) 工具 關於 GitOps 可以參考文章 GitOps Getting Started with Argo CD on Docker Desktop 讓我們一步一步開始吧! 💪
建立 namespace kubectl create namespace argocd 安裝 Argo CD 的 kubernetes resources 需要安裝的 resources 都寫在 install.yaml 內，利用 kubectl apply 指令進行安裝
kubectl apply -n argocd -f https://raw.githubusercontent.com/argoproj/argo-cd/stable/manifests/install.yaml 確認 Argo CD 的 pod 的運行狀態為 running -n 表示指定 namespace 為 argocd，沒設定就是 default namespace
kubectl get pod -n argocd pod 運行狀態

https://yue-jenny.github.io/2023/01/%E5%A6%82%E4%BD%95%E5%9C%A8-hugo-%E4%B8%AD%E5%8A%A0%E5%85%A5%E8%A9%95%E8%AB%96%E7%B3%BB%E7%B5%B1-gitalk/

如何在 Hugo 中加入評論系統 Gitalk 前言 為了在部落格增加互動系統，選擇以 gitalk 作為 comment 系統
實作 建立 Github OAuth App 並取得 client id & client secret (很重要，後續會用到)
作法可參考官方文件 將資訊填入 themes\hugo-theme-stack\config.yaml
clientID: 步驟一取得的 client id clientSecret: 步驟一取得的 client secret gitalk: owner: yue-jenny -> 你的 account name admin: yue-jenny -> 你的 account name repo: yue-jenny.github.io -> 你的 repo name clientID: 123 -> 步驟一取得的 client id clientSecret: 456 -> 步驟一取得的 client secret 上述步驟完成後，需要 admin (通常就是作者) 先 initial comment。

https://yue-jenny.github.io/2023/01/%E5%A6%82%E4%BD%95%E8%A8%AD%E8%A8%88%E8%88%87%E5%AF%A6%E4%BD%9C-monorepo-%E7%9A%84-github-workflow/

https://yue-jenny.github.io/data-structure/classification-of-trees/

樹的分類 樹（Tree）作為一種常見的資料結構，隨著時間的推移，出現了多種不同的樹型結構，每一種都具有特定的優點和應用場景。以下是樹的演進史中一些重要的樹型結構：
二叉樹（Binary Tree） 二叉樹是最簡單且最基本的樹型結構。 每個節點最多有兩個子節點，分別稱為左子節點和右子節點。 二叉樹具有簡單的結構和易於實現的特點，但在某些情況下可能出現不平衡的情況，影響查找效率。 二叉搜索樹（Binary Search Tree） 二叉搜索樹在二叉樹的基礎上進一步定義了鍵的有序性。 對於任意節點，其左子樹中的所有鍵都小於節點的鍵，而右子樹中的所有鍵都大於節點的鍵。 這使得二叉搜索樹能夠快速進行查找、插入和刪除操作。然而，如果插入或刪除操作不當，可能導致樹的不平衡，影響性能。 平衡樹（Balanced Tree） 為了解決二叉搜索樹可能出現的不平衡問題，出現了多種平衡樹結構。
其中最經典的是紅黑樹（Red-Black Tree），它通過在二叉搜索樹的基礎上增加了額外的紅黑色屬性，保持了樹的平衡性。紅黑樹具有良好的平衡性和高效的查找、插入和刪除操作，被廣泛應用於各種應用中。
平衡樹（Balanced Tree）是一種廣泛的樹型資料結構，其中包括了許多種類的樹，如 AVL 樹、紅黑樹、B 樹、B+ 樹、B* 樹、2-3 樹等。
這些樹都有共同的性質：在進行插入或刪除操作時，能維持樹的平衡，也就是說，任意兩個葉節點之間的最長路徑和最短路徑的長度差是有限的。這樣的性質確保了在進行搜尋、插入、刪除等操作時，時間複雜度能維持在對數級別，提高了操作效率。
AVL 樹
AVL樹是最早提出的自平衡二元搜尋樹。它通過維護每個節點的平衡因子（左子樹高度減去右子樹高度）在每次插入或刪除操作後進行調整，以確保樹保持平衡。 紅黑樹（Red-Black Tree）
通過在二叉搜索樹的基礎上增加了額外的紅黑色屬性，保持了樹的平衡性。 B樹（B-Tree, Balanced Sort Tree）
B樹是一種多路平衡搜索樹(查找路徑不止兩個)，特別適合處理大量的數據和磁盤存儲。B樹的特點是每個節點可以有多個子節點，並且可以容納多個鍵。 B樹通過調整節點的大小和節點的分裂合併策略，保持了樹的平衡性，同時提供了高效的插入、刪除和查找操作。 B樹廣泛應用於文件系統和數據庫等場景。 B樹相對平衡二叉樹在節點空間的利用率上進行改進，B樹在每個節點保存更多的數據，減少了樹的高度，從而提升了查找的性能，在數據庫應用中，B樹的每個節點存儲的數據量大約為4K, 這是因為考慮到磁盤數據存儲是採用塊的形式存儲的，每個塊的大小為4K，每次對磁盤進行IO數據讀取時，同一個磁盤塊的數據會被一次性讀取出來，所以每一次磁盤IO都可以讀取到B樹中一個節點的全部數據。 一種特殊的 B 樹：2-3 樹 2-3 樹是一種特殊的 B 樹，其每個節點可以存儲 1 或 2 個值並且具有 2 或 3 個孩子節點，故名為 2-3 樹。 當一個節點的元素數量超過 2 個（即 3 個）時，則進行一次分裂，將中間的元素推送至父節點，並將原節點分裂為兩個節點。 由於 2-3 樹在插入和刪除操作時會進行動態調整，以確保所有葉子節點的深度保持一致，因此 2-3 樹是一種自平衡樹。 B+樹（B+ Tree）

https://yue-jenny.github.io/2023/01/argo-cd-%E6%98%AF%E4%BB%80%E9%BA%BC/

https://yue-jenny.github.io/2022/12/%E5%A6%82%E4%BD%95%E7%94%A8-github-pages-host-%E9%9D%9C%E6%85%8B%E6%AA%94%E6%A1%88/

如何用 github pages host 靜態檔案? 讓我們一步一步開始吧! 💪

https://yue-jenny.github.io/2023/01/security-and-https/

https://yue-jenny.github.io/2022/12/%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8-github-workflow-%E5%AE%8C%E6%88%90-ci/cd/

https://yue-jenny.github.io/page/about/

為什麼想開始寫文章? ☝️ 過一個「有意識地」將學習知識紀錄下來的生活。
✌️ 用撰寫文章來「梳理生活」。
👌 說不定以後這些文章能直接派上用場。😎

https://yue-jenny.github.io/2023/02/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E7%AD%86%E8%A8%98%E5%8D%81-replication-and-sharding/

Replication And Sharding 前言 Replication 目的是建立一個高可用的資料庫架構 可以選擇同步或非同步的方式進行 main 與 replication 資料庫的同步方式 Sharding 目的是為了建立高吞吐量的資料庫架構 達成 sharding 的策略有 hashing strategy 使用不同 table (需要確認資料夠 unitform) 存取 參考資料 👐 system experts 🍀 若喜歡我的分享，可以幫我拍拍手👏，是對我最大的鼓勵

https://yue-jenny.github.io/2023/01/argo-cd-%E6%98%AF%E4%BB%80%E9%BA%BC/

Argo CD 是什麼? 前言 這部分會分享 Argo CD 的中心**、架構與功能。
Argo CD 知識量很龐大，附上其他參考資料給有興趣的人參考
getting started guide user oriented documentation Developer oriented documentation the upgrade guide How it works? 🔩 GitOps pattern Argo CD follows the GitOps pattern of using Git repositories as the source of truth for defining the desired application state.
Argo CD 遵循 GitOps 模式，即以 Git repositories 作為唯一識別 application 狀態的來源 kubernetes controller Argo CD 作為 kubernetes controller，持續偵測運行中的 application，並比較現在狀態與目標狀態
Argo CD 的 kubernetes manifest 可用以下幾種方式建立:

https://yue-jenny.github.io/algo/byzantine-problem/

拜占庭問題 Byzantine Problem 拜占庭問題源自電腦科學，尤其是分散式系統的領域。此問題是命名來自於拜占庭將軍的想像問題，這些將軍被敵人包圍，他們必須達成共識以確定下一步的行動：攻擊或撤退。他們的唯一通訊方式是通過傳遞消息，但問題在於，其中可能有叛徒傳遞假消息，導致非叛徒將軍無法達成共識。
在電腦科學中，這類似於一個分散式系統中的節點必須達成共識，即使有些節點可能故障或行為異常。這種情況可能會導致系統的一部分接受一種結果，而另一部分接受另一種結果，進而無法達成共識。
解決拜占庭問題的一種方法是使用拜占庭容錯（Byzantine Fault Tolerance, BFT）演算法。 BFT演算法旨在處理系統中的故障節點，以達到整個系統的共識。
最知名的BFT演算法是拜占庭將軍問題的原始解答 - 羅馬軍團演算法。
然而，這些算法通常需要多數的正常節點來達到共識，並且在節點數量大時效率降低。
因此，一種比較現代且廣泛使用的方法是使用區塊鏈技術，例如比特幣使用的工作量證明（Proof of Work, PoW）和以太坊等平台使用的權益證明（Proof of Stake, PoS）。這些協議能夠在大規模網路中達成共識，並且對抗拜占庭節點。
工作證明（Proof of Work，PoW） 工作證明（Proof of Work，PoW）是一種在區塊鏈技術中常用的共識機制。它的目的是確保在新增區塊到區塊鏈上時需要進行一定的計算工作，以驗證該區塊的有效性。Proof of Work 最早是由比特幣的白皮書提出，並成為許多其他加密貨幣所採用的共識機制。
在Proof of Work中，節點（或礦工）需要解決一個複雜的數學問題，稱為工作證明。這個問題通常是一個哈希函數的輸入，並要求找到特定的輸出，滿足特定的條件。這個問題的解決過程需要進行大量的計算，而且是具有隨機性的。解決問題的節點被稱為礦工，並且他們需要提供工作證明來證明他們完成了計算工作。
一旦一個節點找到了正確的工作證明，它就可以將該區塊添加到區塊鏈上。其他節點可以輕鬆地驗證這個工作證明的有效性，只需將該證明應用於相同的數學問題上即可驗證其正確性。通過這種方式，工作證明確保了節點必須投入一定的計算資源才能添加新的區塊，從而降低了對惡意行為者的攻擊可能性。
Proof of Work機制的一個重要特點是競爭性。因為節點們需要解決同一個問題，所以他們之間會進行競爭，以便第一個找到正確的工作證明並添加區塊到區塊鏈上。這也就意味著礦工必須擁有更多的計算資源（如計算能力和能源）才能有更高的概率成為下一個添加區塊的節點。
儘管Proof of Work是一個有效且廣泛使用的共識機制，但它也存在一些問題。首先，它需要大量的計算能力和能源消耗，這導致了高昂的運營成本。
其次，Proof of Work機制也可能引發礦工的中心化問題，因為那些擁有更多計算資源的節點有更高的概率獲得獎勵，這使得礦池（多個礦工共同合作挖礦）形成，有可能導致某些節點集中控制了整個區塊鏈網絡。
為了解決這些問題，一些新的共識機制如Proof of Stake（PoS）已經被提出並得到應用。PoS機制通過節點持有的加密貨幣數量來決定他們添加新區塊的權益，從而減少了計算能力和能源的消耗，並有助於達到更高的去中心化程度。
權益證明（Proof-Of-Stake）, PoS Proof of Stake（PoS）是一種區塊鏈共識機制，與Proof of Work（PoW）相對應。在PoS機制中，節點被選為下一個區塊的添加者，並且他們的選擇是基於他們所持有的加密貨幣的數量，而不是計算能力。
在PoS機制中，持有加密貨幣的節點被稱為權益者（stakers）。每個權益者都有機會被選為下一個區塊的添加者，並獲得相應的獎勵。權益者的機會被選中的概率與他們持有的加密貨幣數量成正比，也就是說，持有更多貨幣的節點有更高的概率獲得獎勵。
與PoW不同，PoS機制不需要節點進行大量的計算工作。取而代之的是，節點需要在網絡上鎖定一定數量的加密貨幣作為抵押品。這種抵押品的數量反映了權益者在區塊鏈網絡中的參與程度和利益，並且可以作為選擇下一個區塊添加者的依據。
PoS機制的優勢之一是節能和環保。由於不需要進行大量的計算工作，PoS消耗的能源較少，這對於環境友好型區塊鏈項目尤其重要。此外，PoS機制減少了中心化的風險，因為節點被選中的概率與他們持有的貨幣數量成正比，而不是與計算能力相關。
然而，PoS機制也存在一些挑戰和風險。一個主要的挑戰是所謂的"Nothing at Stake"問題，即節點可以同時參與多個分支，並在分支間進行雙重花費攻擊。這是因為在PoS機制中，選擇分支的成本相對較低，而且沒有額外的計算資源需求。為了解決這個問題，一些PoS區塊鏈項目採取了額外的機制，如罰款或貨幣鎖定期，來防止節點進行惡意行為。
總的來說，PoS機制提供了一種替代PoW的共識機制，並且具有節能、環保和降低中心化風險的潛力。然而，每種共識機制都有其優點和局限性，適用的具體情況取決於項目的目標、需求和環境條件。
更詳細可以參考【區塊鏈 Blockchain – 共識機制之權益證明 Proof-Of-Stake - Samson’s Blog】
Nothing-at-Stake攻擊（無損攻擊） Nothing-at-Stake攻擊（無損攻擊）是一種可能出現在Proof of Stake（PoS）共識機制中的攻擊方式。該攻擊利用了PoS機制的特性，使得節點可以在分叉的區塊鏈上同時參與多個分支，而不需要承擔任何成本或風險。

https://yue-jenny.github.io/data-structure/trie/

介紹 Trie（也稱為字典樹或前綴樹）是一種特殊的資料結構，用於高效地存儲和檢索字符串集合。
該結構的名稱來自於英文單詞「retrieval」的前三個字母。
Trie 使用一種樹狀結構來組織和存儲字符串。
每個節點代表一個字元，從根節點到葉節點的路徑形成一個字符串。
在 Trie 中，共享相同前綴的字符串共用相同的前綴節點，從而實現高效的儲存和檢索。
Trie 的主要優點是： 前綴匹配：Trie 可以非常快速地進行前綴匹配，這使得它在許多字符串檢索的應用中非常有用。例如，你可以使用 Trie 在一個大型字典中快速查詢以特定前綴開始的單詞。 空間效率：儘管 Trie 在存儲字符串集合時可能需要較多的內存，但當字符串共享相同前綴時，Trie 可以有效地壓縮存儲空間，減少重複數據的存儲。 插入和查詢效率：Trie 的插入和查詢操作的時間複雜度都是 O(m)，其中 m 是字符串的平均長度。這使得 Trie 在需要高效的插入和查詢操作的情況下非常有用。 Trie 的基本結構由節點和指向子節點的指針組成。每個節點包含一個字符和一個指向下一級節點的指針數組（通常是一個數組，索引對應於字符集中的字符）。
此外，每個節點還可以包含其他有關字符串的訊息，例如計數器或標記，以滿足特定的應用需求。
基本的插入和查詢操作 Trie 的插入操作非常簡單，只需按照字符串的每個字符在 Trie 中進行遞歸查找。如果遇到缺少的字符，則創建相應的節點。當達到字符串的結尾時，可以在終止節點中標記該字符串的結束。
Trie 的查詢操作也很簡單，只需按照要查詢的字符串的每個字符在 Trie 中進行遞歸查找。如果遇到缺少的字符或到達了 Trie 的結尾，則可以確定該字符串不在 Trie 中。否則，繼續遞歸查找直到字符串的結尾。
除了基本的插入和查詢操作，Trie 還可以進行前綴匹配、模式匹配和字典排序等操作。
總之，Trie 是一種非常有用的資料結構，特別適合處理字符串集合和字典應用。
它提供了高效的插入、查詢和前綴匹配功能，同時具有優秀的空間壓縮性能。
實作 class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let current = this.

https://yue-jenny.github.io/2022/12/%E7%82%BA%E4%BB%80%E9%BA%BC%E6%88%91%E6%B1%BA%E5%AE%9A%E4%BD%BF%E7%94%A8-hugo-%E5%BB%BA%E7%AB%8B%E4%B8%80%E5%80%8B-blog-%E7%B3%BB%E7%B5%B1-%E4%BB%A5%E5%8F%8A%E6%88%91%E8%A9%B2%E5%A6%82%E4%BD%95%E5%BB%BA%E7%AB%8B/

https://yue-jenny.github.io/2023/02/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E7%AD%86%E8%A8%98%E5%85%AB-pulling-and-streaming/

https://yue-jenny.github.io/2023/02/%E7%B3%BB%E7%B5%B1%E8%A8%AD%E8%A8%88%E5%9F%BA%E7%A4%8E%E7%AD%86%E8%A8%98%E4%B9%9D-peer-to-peer-networks/

https://yue-jenny.github.io/data-structure/a-list-of-learning-data-structures/

介紹 當你想要學習資料結構時，以下是一些建議的學習列表：
陣列 (Array): 學習如何使用陣列存儲和訪問資料，以及陣列的基本操作，如插入、刪除和搜尋。
串列 (Linked List): 學習如何使用串列結構來組織和存儲資料，並理解串列的插入、刪除和搜尋操作。
堆疊 (Stack): 學習堆疊的概念和操作，包括推入 (push) 和彈出 (pop) 元素，以及堆疊的應用場景。
佇列 (Queue): 學習佇列的概念和操作，包括入列 (enqueue) 和出列 (dequeue) 元素，以及佇列的應用場景。
樹 (Tree): 學習樹的基本結構、遍歷方法 (如前序、中序和後序遍歷)，以及二元樹、二元搜索樹和平衡樹等特殊類型的樹。
圖 (Graph): 學習圖的基本結構和表示方法，以及圖的遍歷、搜索和最短路徑算法，如深度優先搜索 (DFS) 和廣度優先搜索 (BFS)。
哈希表 (Hash Table): 學習哈希表的原理和實現，理解哈希函數、碰撞解決方法和哈希表的查找和插入操作。
堆積 (Heap): 學習堆積的概念和操作，包括最大堆和最小堆，以及堆排序和優先級佇列的應用。
鏈接 (Hashing): 學習散列的概念和操作，包括散列函數、碰撞解決方法和散列表的查找和插入操作。
圖算法 (Graph Algorithms): 學習常見的圖算法，如最短路徑算法 (如Dijkstra和Bellman-Ford)、最小生成樹算法 (如Prim和Kruskal) 和拓撲排序。
字典樹 (Trie): 學習字典樹的概念和操作，特別適用於字串搜索和自動補全等應用。
平衡樹 (Balanced Tree): 學習平衡樹的概念和實現，如紅黑樹和AVL樹，了解平衡樹的插入、刪除和查找操作。
圖示演算法 (Graphical Algorithms): 學習用於圖示設計和模擬的算法，如迭代深化深度優先搜索 (IDDFS)。
雜湊圖 (Hashgraph): 學習分佈式共識機制的一種形式，可以實現高性能和安全性的分佈式資料結構。
高級資料結構 (Advanced Data Structures): 學習一些高級的資料結構，如B+樹、約瑟夫問題、線段樹、樹狀數組等。

https://yue-jenny.github.io/2023/06/%E4%BA%8C%E5%85%83%E6%A8%B9%E4%BA%8C%E5%8F%89%E6%A8%B9%E7%9A%84%E4%B8%AD%E5%BA%8F%E9%81%8D%E6%AD%B7in-order-traversal/

中序遍歷 中序遍歷（In-order traversal）是一種遍歷二叉樹的方法，其順序為先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。
下面是中序遍歷的詳細過程：
如果當前節點為空，則返回。 對當前節點的左子樹進行中序遍歷，即遞歸調用中序遍歷函數，傳入當前節點的左子節點。 訪問當前節點，可以進行一些操作，例如將節點的值添加到結果列表中。 對當前節點的右子樹進行中序遍歷，即遞歸調用中序遍歷函數，傳入當前節點的右子節點。 以下是一個示例來說明中序遍歷的過程。假設我們有以下的二叉樹：
4
/
2 6
/ \ /
1 3 5 7 按照中序遍歷的順序，我們應該依次訪問節點的值為 1, 2, 3, 4, 5, 6, 7。具體步驟如下：
從根節點開始遍歷，當前節點為 4。遞歸調用中序遍歷函數，傳入左子節點 2。 當前節點為 2，遞歸調用中序遍歷函數，傳入左子節點 1。 當前節點為 1，沒有左子節點，返回到節點 2。將節點 1 的值添加到結果列表中。 返回到節點 4，將節點 2 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 3。 當前節點為 3，沒有左子節點，返回到節點 4。將節點 3 的值添加到結果列表中。 返回到節點 4，將節點 4 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 6。 當前節點為 6，遞歸調用中序遍歷函數，傳入左子節點 5。 當前節點為 5，沒有左子節點，返回到節點 6。將節點 5 的值添加到結果列表中。 返回到節點 6，將節點 6 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 7。 當前節點為 7，沒有左子節點，返回到節點 6。將節點 7 的值添加到結果列表中。 返回到節點 6，返回到節點 4。 返回到根節點 4，遍歷完成。 範例程式碼 以下是一個使用 JavaScript 實現二叉樹中序遍歷的程式碼範例：

https://yue-jenny.github.io/2023/01/kafka-%E7%B0%A1%E4%BB%8B/

https://yue-jenny.github.io/data-structure/segment-tree/

介紹 線段樹（Segment Tree）是一種常見的資料結構，用於解決區間查詢（range query）的問題。
它主要用於處理數列或數組的區間操作，如區間求和、區間最大值、區間最小值等。
線段樹的基本**是將原始的數據按照一定的方式分割成若干個區間，並在每個區間上存儲相應的信息，如區間的總和、最大值、最小值等。這樣，在需要查詢某個區間的統計信息時，可以通過合併相應區間的信息快速計算得到。
一般而言，線段樹是一種二叉樹結構，每個節點表示一個區間，而樹的根節點表示整個數列或數組的區間。
每個節點包含了該區間的統計信息，以及指向左右子節點的指標。
基礎操作 建構線段樹的過程可以使用遞迴或迭代的方式進行。具體而言，建構過程中，將原始數據切分為兩半，然後遞迴構建左子樹和右子樹，最終將左子樹和右子樹的統計信息合併到當前節點。
線段樹的查詢操作也可以使用遞迴或迭代的方式進行。當查詢的區間與節點表示的區間有交集時，需要遞迴查詢左子節點和右子節點。如果查詢的區間完全包含在節點表示的區間中，則可以直接返回該節點的統計信息。
線段樹的修改操作通常也使用遞迴或迭代的方式進行。當需要修改某個位置的值時，需要遞迴更新涉及該位置的所有節點，以維護其統計信息的準確性。
時間複雜度，推薦必看👍 資料來自菜鳥工程師肉豬的部落格，推薦超好懂 👍：
【為什麼Binary Search 二元搜索法的時間複雜度是O(log(n))】
優點 線段樹的優點在於可以在O(logN)的時間複雜度下完成區間操作，其中N表示數列或數組的長度。
它在許多需要頻繁進行區間操作的應用場景中具有重要的應用價值，如區間求和、區間最值查詢、區間更新等。
問題與限制 然而，線段樹也有一些限制和注意事項。首先，它需要較多的內存空間來存儲統計信息，因此在處理大型數據集時可能會面臨內存限制的問題。此外，線段樹的建構過程較為複雜，並且對於動態更新的情況，可能需要進行結構調整，增加了一定的複雜度。
結論 總體而言，線段樹是一種強大的數據結構，可以高效地處理區間操作的問題。在算法競賽和一些需要快速解決區間查詢的應用中，線段樹是一個重要的工具。
以下是使用 JavaScript 實現線段樹的基本範例碼： class SegmentTree { constructor(nums) { this.nums = nums; this.tree = new Array(nums.length * 4); // 建立線段樹陣列 this.buildTree(0, 0, nums.length - 1); } // 建立線段樹 buildTree(node, start, end) { if (start === end) { this.tree[node] = this.nums[start]; } else { const mid = Math.

https://yue-jenny.github.io/2023/06/%E4%BA%8C%E5%85%83%E6%A8%B9%E4%BA%8C%E5%8F%89%E6%A8%B9%E7%9A%84%E5%BE%8C%E5%BA%8F%E9%81%8D%E6%AD%B7postorder-traversal/

主題 後序遍歷（Postorder Traversal）是二叉樹遍歷的一種方式。
其中節點的順序是先訪問左子樹，然後訪問右子樹，最後訪問根節點。
以下是後序遍歷的過程：
檢查當前節點是否為空。如果是空節點，則返回上一層。 從當前節點開始，先遞歸地後序遍歷左子樹。 接著，遞歸地後序遍歷右子樹。 最後，訪問當前節點。 這個遍歷過程可以使用遞歸或堆疊來實現。
以下是一個使用遞歸的後序遍歷的範例： 假設有以下二叉樹：
A
/
B C
/ \
D E F 後序遍歷的結果將是：D, E, B, F, C, A。
過程如下：
從根節點 A 開始： 遞歸地後序遍歷左子樹 B。 遞歸地後序遍歷左子樹 D。 D 為葉子節點，訪問 D。 遞歸地後序遍歷右子樹 E。 E 為葉子節點，訪問 E。 訪問 B。 遞歸地後序遍歷右子樹 C。 遞歸地後序遍歷右子樹 F。 F 為葉子節點，訪問 F。 訪問 C。 訪問 A。 因此，後序遍歷的結果為 D, E, B, F, C, A。
實作 // 定義二元樹節點的結構 class TreeNode { constructor(val, left, right) { this.