Programming

系統設計的核心概念 System Design Key Concepts 可擴展性(Scalability) 延遲與吞吐量(Latency vs Throughput) CAP 定理(CAP Theory) ACID 交易(ACID Transactions)

Shortcodes 介紹 Shortcodes 是內容檔案中的一個簡單片段，Hugo將使用預先定義的範本對其進行呈現。 除了更乾淨的 Markdown 外，Shortcodes 還可以隨時更新新的技術或標準。 Notice shortcodes 將以下程式碼加入到 Hugo 專案底下的 layouts/shortcodes/notice.html {{/* Available notice types: warning, info, note, tip */}} {{- $noticeType := .Get 0 | default "note" -}} {{/* Workaround markdownify inconsistency for single/multiple paragraphs */}} {{- $raw := (markdownify .Inner | chomp) -}} {{- $block := findRE "(?is)^<(?:address|article|aside|blockquote|canvas|dd|div|dl|dt|fieldset|figcaption|figure|footer|form|h(?:1|2|3|4|5|6)|header|hgroup|hr|li|main|nav|noscript|ol|output|p|pre|section|table|tfoot|ul|video)\\b" $raw 1 -}} {{/* Count how many times we've called this shortcode and load the css if it's the first time */}} {{- if not ($....

Introduction to ML 統計學與機器學習差在哪裡? 同: 將資料(data)轉為資訊(info) 異: 有無強烈的人為事先假設 統計學 統計學是在資料分析的基礎上，研究如何測定、收集、整理、歸納和分析反映資料，以便給出正確訊息的科學。 機器學習 機器學習演算法是一類從資料中自動分析獲得規律，並利用規律對未知資料進行預測的演算法。 \(\begin{array}{lll} \text{Item} & \text{Statistics} & \text{Machine Learning}\\\hline \text{特性} & \text{伴隨事前假設，依賴明確規則，以模型定義資料關聯性，重視模型解釋性} & \text{幾乎無視前假設，不依賴明確規則，相信經驗}\\ & \text{事前假設(人)}\rightarrow\text{模型估計(機器)} & \text{特徵萃取(機器)}\rightarrow\text{網路建構(機器)} \\\hline \text{優點} & \text{模型可解釋} & \text{不須事先假設或了解資料關聯性}\\ & \text{推論有強烈理論根據} & \text{可抓取資料的所有(幾乎)複雜特徵}\\ & \text{符合事前假設前提下，可做更多的推論}\\ & \text{符合事前假設前提下，不需大量資料} \\\hline \text{缺點} & \text{所有推論接基於事前假設，常難以驗證假設的正確性} & \text{模型難以解釋(黑盒子)}\\ & \text{難以抓取資料中過於複雜的特徵} & \text{推論無強烈理論根據} \\\hline \text{專家} & \text{統計背景} & \text{資訊背景及統計背景} \\\hline \end{array}\) 結論 統計模型的重點是有合理的事前假設 在有合理假設之情況下，統計模型能發揮效力(即使資料量少) 機器學習的重點是大量有代表性的資料 在有大量有效資料之情況下，機器學習能發揮效力(即使人類對資料間的關聯之了解並不多) 何時使用統計方法? 何時使用機器學習? 資料關聯性清楚，容易給予合適的模型假設時，建議使用統計模型 資料無明確規則(如影像及語音辨識)，且資料量夠多時，建議使用機器學習方法(可以佐以人為提示) 統計與機器學習類似的專有名詞 \(\begin{array}{ll} \text{Statistics} & \text{Machine Learning} \text{response, dependent variable} & \text{label} \\\hline \text{covariate, explanatory variable, independent variable} & \text{feature} \\\hline \text{model} & \text{network} \\\hline \text{parameter, coefficient} & \text{weight} \\\hline \text{fitting} & \text{learning} \\\hline \text{refression, classification} & \text{supervised learning} \\\hline \text{density estimation, cluster} & \text{unsupervised learning} \\\hline \end{array}\)

線段樹 Segment Tree 簡介 線段樹是演算法中常用來維護區間訊息的資料結構。 空間複雜度為 \(O(n)\)，\(n\) 代表區間數。 查詢的時間複雜度為 \(O(\log n+k)\)，\(k\) 代表符合條件的區間數量。 線段樹將每個長度為為 1 的區間劃分為左右兩個區間遞迴求解，把整個線段劃分為一個樹型結構，通過合併左右兩個區間訊息來求得該區間的訊息。 在實現時，我們考慮遞迴建樹，設當前的根節點為 root，如果根節點管轄的區間長度已經是 1，則可以直接根據數組上相應位置的值初始化該節點。否則需將該區間從中點處分割為兩個子區間，分別進入左右子節點遞迴建樹，最後合併兩個子節點的訊息， 建樹 build void build(int s, int t, int p, const vector<int>& arr){ if (s == t){ tree[p] = SegmentItem(arr[s], 1); return; } int m = s + ((t - s) >> 1); build(s, m, p*2, arr); build(m+1, t, p*2+1, arr); // push_up tree[p] = tree[p*2] + tree[(p*2)+1]; } 查詢 query SegmentItem find(int l, int r, int s, int t, int p){ if (l <= s && t <= r){ return tree[p]; } int m = s + ((t - s) >> 1); SegmentItem sum; if (r <= m) return find(l, r, s, m, p*2); if (l > m) return find(l, r, m+1, t, p*2+1); return find(l, r, s, m, p*2) + find(l, r, m+1, t, p*2+1); } zkw 線段樹 來自清華大學張昆瑋(zkw)-《統計的力量》 以非遞迴的方式構建，效率更高，程式更短。 普通的線段樹是從上到下做處理，容易定位根節點，卻不容易定位子節點。 zkw 線段樹是當二叉樹是滿二叉樹時，因為子節點的編號具有以下規律： 葉子節點(left) 全部退化為線段 \([x,x]\) 。 \(n\) 個數據點則取大於等 \(n\)且為 \(2\) 的冪次的兩倍作為數組大小。 \((m=2^a\ge n)\) for (int m = 1; m <= n; m >>= 1) 維護點為 \(n\) 個。索引為\([m,m+n)\)。 子葉數目為 \(m\) 個。索引為\([m,2m)\) 節點數為 \(2m-1\) 個。(數組大小需設 \(2m\) 因為 zkw tree是 1-index的) 樹高 \(H=\log_2(m)+1\) 層。 第 \(h\) 層有 \(2^{h-1}\) 個節點， 該層線段長度為 \(2^{H-h}\)。 若某節點為 \(p\)，父節點為 \(p/2\)，子節點為 \(2p\) 和 \(2p+1\) int parent = p >> 1; int left = p << 1; int right = p << 1 | 1; 若兩節點為 \(p\) 與 \(q\)，且兩節點互為兄弟節點，則 \(p\oplus q=1\) if (left ^ right) // left 與 right 為兄弟節點 else // left 與 right 不為兄弟節點 除根節點外，左節點皆為偶數，右節點皆為奇數 if (i == 1) // i 為根節點 else if (i & 1) // i 為奇數，為右節點 else if (!...

stringstream 需引用 <sstream> , <iostream>, <string>函式庫 配合 str() 將 stringstream 類轉換成 string 類別。 split() vector<string> split(string& str, char del){ stringstream ss(str); string item; vector<string> res; while (getline(ss, item, del)){ if (!item.empty()){ res.push_back(item); } } return res; } concat() string concat(vector<string>& svec, char del){ stringstream ss; for (const auto& s : svec){ ss << s << del; } return ss.str(); } [leetcode 1859. Sorting the Sentence] class Solution { public: string sortSentence(string s) { vector<string> tmp = split(s, ' '); int n = tmp....