Programming

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 ($.Page.Scratch.Get "noticecount") -}} <style type="text/css">.notice{--root-color:#444;--root-background:#eff;--title-color:#fff;--title-background:#7bd;--warning-title:#c33;--warning-content:#fee;--info-title:#fb7;--info-content:#fec;--note-title:#6be;--note-content:#e7f2fa;--tip-title:#5a5;--tip-content:#efe}@media (prefers-color-scheme:dark){.notice{--root-color:#ddd;--root-background:#eff;--title-color:#fff;--title-background:#7bd;--warning-title:#800;--warning-content:#400;--info-title:#a50;--info-content:#420;--note-title:#069;--note-content:#023;--tip-title:#363;--tip-content:#121}}body.dark .notice{--root-color:#ddd;--root-background:#eff;--title-color:#fff;--title-background:#7bd;--warning-title:#800;--warning-content:#400;--info-title:#a50;--info-content:#420;--note-title:#069;--note-content:#023;--tip-title:#363;--tip-content:#121}.notice{padding:18px;line-height:24px;margin-bottom:24px;border-radius:4px;color:var(--root-color);background:var(--root-background)}.notice p:last-child{margin-bottom:0}.notice-title{margin:-18px -18px 12px;padding:4px 18px;border-radius:4px 4px 0 0;font-weight:700;color:var(--title-color);background:var(--title-background)}.notice.warning .notice-title{background:var(--warning-title)}.notice.warning{background:var(--warning-content)}.notice.info .notice-title{background:var(--info-title)}.notice.info{background:var(--info-content)}.notice.note .notice-title{background:var(--note-title)}.notice.note{background:var(--note-content)}.notice.tip .notice-title{background:var(--tip-title)}.notice.tip{background:var(--tip-content)}.icon-notice{display:inline-flex;align-self:center;margin-right:8px}.icon-notice img,.icon-notice svg{height:1em;width:1em;fill:currentColor}.icon-notice img,.icon-notice.baseline svg{top:.125em;position:relative}</style> <div><svg width="0" height="0" display="none" xmlns="http://www.w3.org/2000/svg"><symbol id="tip-notice" viewBox="0 0 512 512" preserveAspectRatio="xMidYMid meet"><path d="M504 256c0 136.967-111.033 248-248 248S8 392.967 8 256 119.033 8 256 8s248 111.033 248 248zM227.314 387.314l184-184c6.248-6.248 6.248-16.379 0-22.627l-22.627-22.627c-6.248-6.249-16.379-6.249-22.628 0L216 308.118l-70.059-70.059c-6.248-6.248-16.379-6.248-22.628 0l-22.627 22.627c-6.248 6.248-6.248 16.379 0 22.627l104 104c6.249 6.249 16.379 6.249 22.628.001z"/></symbol><symbol id="note-notice" viewBox="0 0 512 512" preserveAspectRatio="xMidYMid meet"><path d="M504 256c0 136.997-111.043 248-248 248S8 392.997 8 256C8 119.083 119.043 8 256 8s248 111.083 248 248zm-248 50c-25.405 0-46 20.595-46 46s20.595 46 46 46 46-20.595 46-46-20.595-46-46-46zm-43.673-165.346l7.418 136c.347 6.364 5.609 11.346 11.982 11.346h48.546c6.373 0 11.635-4.982 11.982-11.346l7.418-136c.375-6.874-5.098-12.654-11.982-12.654h-63.383c-6.884 0-12.356 5.78-11.981 12.654z"/></symbol><symbol id="warning-notice" viewBox="0 0 576 512" preserveAspectRatio="xMidYMid meet"><path d="M569.517 440.013C587.975 472.007 564.806 512 527.94 512H48.054c-36.937 0-59.999-40.055-41.577-71.987L246.423 23.985c18.467-32.009 64.72-31.951 83.154 0l239.94 416.028zM288 354c-25.405 0-46 20.595-46 46s20.595 46 46 46 46-20.595 46-46-20.595-46-46-46zm-43.673-165.346l7.418 136c.347 6.364 5.609 11.346 11.982 11.346h48.546c6.373 0 11.635-4.982 11.982-11.346l7.418-136c.375-6.874-5.098-12.654-11.982-12.654h-63.383c-6.884 0-12.356 5.78-11.981 12.654z"/></symbol><symbol id="info-notice" viewBox="0 0 512 512" preserveAspectRatio="xMidYMid meet"><path d="M256 8C119.043 8 8 119.083 8 256c0 136.997 111.043 248 248 248s248-111.003 248-248C504 119.083 392.957 8 256 8zm0 110c23.196 0 42 18.804 42 42s-18.804 42-42 42-42-18.804-42-42 18.804-42 42-42zm56 254c0 6.627-5.373 12-12 12h-88c-6.627 0-12-5.373-12-12v-24c0-6.627 5.373-12 12-12h12v-64h-12c-6.627 0-12-5.373-12-12v-24c0-6.627 5.373-12 12-12h64c6.627 0 12 5.373 12 12v100h12c6.627 0 12 5.373 12 12v24z"/></symbol></svg></div> {{- end -}} {{- $.Page.Scratch.Add "noticecount" 1 -}} <div class="notice {{ $noticeType }}" {{ if len .Params | eq 2 }} id="{{ .Get 1 }}" {{ end }}> <p class="first notice-title"><span class="icon-notice baseline"><svg><use href="#{{- $noticeType -}}-notice"></use></svg></span>{{- i18n $noticeType -}}</p> {{- if or $block (not $raw) }}{{ $raw }}{{ else }}<p>{{ $raw }}</p>{{ end -}} </div> Classes 警告 {{< notice warning >}} 這是警告(warning) {{< /notice >}} ...

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 (!(i & 1)) // i 為偶數，為左節點 結構 線段樹索引堆疊： 轉成二進制： 規律： 一個節點的父節點是該數右移 1，低位捨棄。 一個節點的左子節點是該數左移 1，右子節點是該數左移 1 再加 1。 同一層的節點是依次遞增的，第 \(n\) 層有 \(2^{n-1}\)個節點 最後一層有多少個節點，值域就是多少。 建樹 build 取 m 值有許多版本，有些版本會直接取 \(m=2^{log_2(n+5)+1}\)以節省迭代計算 寫成 int n = 1 << __lg(n+5)+1; 可以有開區間與閉區間兩種做法，差別在於從子葉節點的最左邊 \(m+i\) 開始，或是第二個子葉節點 \(m+1+i\) 開始。 由下而上更新時，開區間與閉區間的終止條件不同： 開區間的終止條件為兩子節點互為兄弟節點 while (i^j^1) // operation 閉區間的終止條件為右節點小於左節點 while (i <= j) // operation class Tree { private: vector<int> arr; int n, m; // n 為維護點數, m 為 zkw-tree 子葉節點數 public: Tree (vector<int>& nums){ n = nums.size(); for (m = 1; m <= n; m <<= 1); // 取大於等於 n 且為 2 的冪次的最小整數 arr.assign(2*m, 0); // 節點數設為 2m 個，其中 0 為空節點 } void build(vector<int> nums){ for (int i = 0; i < n; i++) { arr[i+m] = nums[i]; // 從子葉節點最左邊往右更新節點。 mx[i+m] = nums[i]; mn[i+m] = nums[i]; } for (int i = m-1; i; i--){ // 向上更新父節點。 arr[i] = in(x); } } }; 根據不同需求代換 \(\text{in(x)}\)：取和、最大值、最小平 // 取和 arr[i] = arr[i<<1] + arr[i<<1|1]; // 取最大值 arr[i] = max(arr[i<<1], arr[i<<1|1]); // 取最小值 arr[i] = min(arr[i<<1], arr[i<<1|1]); 更新 update 單點修改(以和為例) 更新時，以差分方式，將所有父節點加上更新點的差值。 void update(int i, int val){ int diff = val - arr[m+i] // 原值 arr[m+i] 與新值 val 的差 for (i += m; i; i >>= 1){ arr[i] += diff; } } 查詢 query 單點查詢(以和為例)：閉區間做法 判斷左邊界是否為右節點，若為右節點則加上後往右邊的父節點移動。 判斷右邊界是否為左節點，若為左節點則加上後往左邊的父節點移動。 int query(int left, int right){ int sum = 0; int i = left+m; // 左閉區間 int j = right+m; // 右閉區間 for (; i <= j; i >>= 1, j >>= 1){ if (i & 1) sum += arr[i++]; if (!(j & 1)) sum += arr[j--]; } return sum; } 備註：開區間作法 (0-index 時會出現 -1 的情形，建議使用閉區間) int query(int left, int right){ int sum = 0; int i = left+m-1; int j = right+m+1; for(; i^j^1; i >>= 1, j >>= 1){ if (~i & 1) sum += arr[i^1]; if (j & 1) sum += arr[j^1]; } return sum; } 區間修改 在非遞迴的情況下，標記下傳是比較困難的，所以作法上改成將標記永久化。 具體而言，與查詢類似，當左端點是左子節點且右端點是右子節點時，我們對它的兄弟節點進行修改並標記，表示這顆子樹中的每個節點都要被修改。但單純這樣還不夠，因上述修改還會波及到這些節點的各級祖先，所以我們需要在途中根據實際修改的區間長度來更新各級祖先的值，這種操作需要一路上推到根節點。 (開區間作法) void update(int left, int right, int diff){ int len = 1, cntl = 0, cntr = 0; // cntl, cntr 是左右邊分別實際修改的區間長度 left += m-1; right += m+1; for (; left^right^1; left >> 1, right >> 1, len << 1){ arr[left] += cntl * diff; arr[right] += cntr * diff; if (~left & 1) { arr[left^1] += diff * len; mark[left^1] += diff; cntl += len; } if (right & 1) { arr[right^1] += diff * len; mark[right^1] += diff; cntr += len; } } for (; left; left >>= 1, right >>= 1){ arr[left] += cntl * diff; arr[right] += cntr * diff; } } 在有區間修改存在時，區間查詢也需要考慮標記的影響。 所以除了加上端點的兄弟節點訊息，沿途中遇到的標記也對答案有貢獻，同樣需要上推到根節點。 int query(int left, int right){ int sum = 0, len = 1, cntl = 0, cntr = 0; left += m - 1; right += m + 1; for (; left^right^1; left >>= 1, right >>= 1, len << 1){ sum += cntl * mark[left] + cntr * mark[right]; if (~left & 1) sum += arr[left^1], cntl += len; if (right & 1) sum += arr[right^1], cntr += len; } for (; left; left >> 1, right >> 1){ sum += cntl * mark[left] + cntr * mark[right]; } return sum; } 區間查詢最大值： void update(int l, int r, int d) { for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) { if (l < N) tree[l] = max(tree[l << 1], tree[l << 1 | 1]) + mark[l], tree[r] = max(tree[r << 1], tree[r << 1 | 1]) + mark[r]; if (~l & 1) tree[l ^ 1] += d, mark[l ^ 1] += d; if (r & 1) tree[r ^ 1] += d, mark[r ^ 1] += d; } for (; l; l >>= 1, r >>= 1) if (l < N) tree[l] = max(tree[l << 1], tree[l << 1 | 1]) + mark[l], tree[r] = max(tree[r << 1], tree[r << 1 | 1]) + mark[r]; }; int query(int l, int r) { int maxl = -INF, maxr = -INF; for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) { maxl += mark[l], maxr += mark[r]; if (~l & 1) cmax(maxl, tree[l ^ 1]); if (r & 1) cmax(maxr, tree[r ^ 1]); } for (; l; l >>= 1, r >>= 1) maxl += mark[l], maxr += mark[r]; return max(maxl, maxr); }; Leetcode. 307 範例 https://leetcode.com/problems/range-sum-query-mutable/ TreeNode 變形 class NumArray { class SegTree { public: int val; int begin, end; SegTree* left, *right; SegTree(int v):val(v) {} SegTree(int v, int b, int e):val(v), begin(b), end(e) {} SegTree(int v, int b, int e, SegTree* l, SegTree* r) :val(v), begin(b), end(e), left(l), right(r) {} }; SegTree* root; SegTree* build(vector<int>& nums, int b, int e){ if (e < b) return NULL; if (b == e) return new SegTree(nums[b], b, b); int mid = b + (e-b)/2; SegTree* left = build(nums, b, mid); SegTree* right = build(nums, mid+1, e); return new SegTree(left->val + right->val, b, e, left, right); } void update(SegTree* node, int index, int val){ if (node->begin == index && node->end == index){ node->val = val; } else { int mid = node->begin + (node->end - node->begin)/2; if (index <= mid){ update(node->left, index, val); } else { update(node->right, index, val); } node->val = node->left->val + node->right->val; } } int query(SegTree* node, int left, int right){ if (node->begin == left && node->end == right){ return node->val; } int mid = node->begin + (node->end - node->begin)/2; if (right <= mid){ return query(node->left, left, right); } else if (left > mid){ return query(node->right, left, right); } return query(node->left, left, mid) + query(node->right, mid+1, right); } public: NumArray(vector<int>& nums) { root = build(nums, 0, nums.size()-1); } void update(int index, int val) { update(root, index, val); } int sumRange(int left, int right) { return query(root, left, right); } }; zkw 線段樹 class NumArray { class SegTree { vector<int> arr; int m, n; public: SegTree(vector<int>& nums) { n = nums.size(); for (m = 1; m < n; m <<= 1); build(nums); } void build(vector<int>& nums) { arr.assign(2*m, 0); for (int i = 0; i < n; ++i) arr[m+i] = nums[i]; for (int i = m-1; i; --i) arr[i] = arr[i<<1] + arr[i<<1|1]; } void update(int index, int val) { int diff = val - arr[m+index]; for (index += m; index; index >>= 1) arr[index] += diff; } int query(int left, int right) { int sum = 0; for (int i = left+m, j = right+m; i <= j; i >>= 1, j >>= 1){ if (i & 1) sum += arr[i++]; if (!(j & 1)) sum += arr[j--]; } return sum; } }; public: SegTree* root; NumArray(vector<int>& nums) { root = new SegTree(nums); } void update(int index, int val) { root->update(index, val); } int sumRange(int left, int right) { return root->query(left, right); } }; BIT(binary indexed tree) class NumArray { public: class Bit { public: vector<int> bit; int n; Bit(vector<int>& nums) { n = nums.size(); bit.assign(n+1, 0); for (int i = 0; i < n; i++){ build(i+1, nums[i]); } } void build(int index, int val) { while (index <= n){ bit[index] += val; index = next(index); } } int next(int index) { return index + (index & -index); } int parent(int index) { return index - (index & -index); } int getSum(int index) { int sum = 0; while (index){ sum += bit[index]; index = parent(index); } return sum; } }; Bit* bit; NumArray(vector<int>& nums) { bit = new Bit(nums); } void update(int index, int val) { int diff = val - sumRange(index, index); bit->build(index+1, diff); } int sumRange(int left, int right) { return bit->getSum(right+1) - bit->getSum(left); } };

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.size(); vector<string> svec(n); for (const string& s : tmp){ int pos = s.back() - '1'; svec[pos] = s.substr(0, s.length()-1); } return concat(svec, ' '); } string concat(vector<string>& svec, char del){ string res; stringstream ss; for (const string& s : svec) ss << del << s; res = ss.str(); return res.substr(1); } vector<string> split(string& str, char del){ vector<string> res; stringstream ss(str); string item; while (getline(ss, item, del)){ if (!item.empty()){ res.push_back(item); } } return res; } };

什麼是 AI & ML & DL 人工智慧是我們想要達成的目標，而機器學習是想要達成目標的手段，希望機器通過學習的方式，變得跟人一樣聰明。 而深度學習就是機器學習的其中一種方法。 人工智慧(Aritificial Intelligence, AI) → 目標 機器學習(Machine Learning, ML) → 手段 深度學習(Deep Learning, DL) … 在機器學習出現之前 生物的行為取決於兩件事，一個是後天學習的結果，一個是天生的本能。 Hand-crafted rules: 人類為機器設定好的天生本能 僵化，無法超越創造者 需要大量人力，不適合小企業 機器學習 寫程式讓機器可以學習 → 尋找關聯資料的函式 舉例：語音辨識、影像辨識、Alpha Go、對話機器人 框架(Framework) 設定一定量的函數 餵入數據 評估函數的好壞 找出最好的函數 \(\begin{array}{rc} \text{step1}&\boxed{\text{Define a set of function}}\\ &\downarrow\\ \text{step2}&\boxed{\text{Evaluate goodness of function}}\\ &\downarrow\\ \text{step3}&\boxed{\text{Pick the best function}}\end{array}\) 告訴機器 input 和正確的 output 這就叫作 supervised learning。 機器學習相關的技術 任務(Task) 迴歸(Regression) Regression 指的是函數的輸出為 scalar(數值)，如 PM2.5。 分類(Classification) Classification 指的是函數的輸出為 東西的類別。 當分類為 Yes or No，則為 Binary Classificatino，如垃圾郵件。 當分類是多個選項的，則為 Multi-Classification，如新聞分類。 結構性學習(Structured Learning) 讓機器的輸出具有結構性。 如語音辨識，聲音訊號為輸入，句子為輸出。 如影像辨識，圖片是輸入，人名是輸出。 方法(Method) 選不同的 function set 就是選不同的 model。 ...

Deque 不同於 stack 與 queues， deques 兩個端點都支援擴展。 基於 doubly linked list，deques 有幾項額外的特徵： 支援隨機存取 插入元素時間 \(O(1)\) 函式 1. push_front() 2. push_back() 3. front() 4. back() 5. begin() 6. end() 7. insert() 8. erase() 9. pop_front() 10. pop_back() 11. empty() 12. clear() 13. random_access() 內部運作原理 上述所有函數和操作都在雙鏈表中以O（1）時間執行，但這些清單不能隨機訪問任何元素。C++中的deque也是如此。這個 O（1） 在 deque 中可以使用圓形陣列來實現。使用循環陣列，可以在O（1）時間內實現從陣列的正面和背面插入和刪除等操作以及元素的隨機訪問。但這帶來了一個問題。當 deque 增長到超出容量時，使用者將需要將數位大小加倍，並將所有數據複製到陣列中。此外，如果數據是某個使用者定義的對象，那麼加倍和複製數據的成本就會變得非常昂貴。 這是一個基本的解決方案。Deque使用一些棘手的實現，當它說O（1）來push_back（）和push_front（）時，它實際上是調用的複製構造函數數量的常數時間。因此，如果數據物件是具有多個成員的某個類物件，則最小化複製構造函數調用的數量將節省時間。此外，複製構造函數調用的次數是恆定的。現在讓我們看看如何實現這一點。 這可以通過使用指向一些固定大小的塊的指標數位來實現，這些塊包含deque數據。下面是一個說明性示例。 這些 Deque 數據被劃分為固定大小的塊。在這裡，我們考慮了將數據劃分為大小為5的固定塊。 塊的填充從指標的兩個 deque 陣列的中間開始，並使用push_front和push_back操作向前和向後擴展。中間塊通常是滿的，當它被填滿時，數據被移動到上部或下部塊。 在上部塊中，元素以相反的順序推送，因為在這種情況下，填充數據的第一個位置將是4，然後是3，2，1，0。但是在中間和下部塊中，數據按正向順序填充，如0，1，2，3，4等。 當上面的塊被填滿時，指標將創建一個新塊並開始指向一個新的數位塊。這為更多數據創造了空間。在這種情況下，也可以填充指標塊。這會導致一個問題。 這是加倍來救援的時候。在加倍時，指標陣列的大小加倍。這不會複製整個數據，而只會複製指標。這是許多人在討論恆定時間時提出的一般論點。時間在調用的複製構造函數數方面保持不變。 如果數據集非常大，則指標塊幾乎不會執行加倍，因為單個指標可以指向大量數據塊。因此，指標陣列被填充並加倍的可能性非常小。

C++ Custom Comparator sort(iter, iter, comp) Lambda function int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Usual boolean function bool comp(const int& a, const int& b){ return a < b; } int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp()); // 1,2,3,4,5,6,7,8,9 } priority_queue(element, container, comp) Modern C++20 Solution(lambda) We can use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq; for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Modern C++11 Solution(lambda) Before C++20 we need to pass lambda function as argument to set constructor. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Usual function Make comparator as usual boolean function bool comp(int a, int b){ return a < b; } int main(){ vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); // priority_queue<int, vector<int, decltype(comp)*> pq(comp); // in C++20, constructor can be ignored the same as lambda function. for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int>, comp> pq(vec.begin(), vec.end()); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Alternative solution: create struct/class from boolean function bool comp(int a, int b){ return a < b; } #include <type_traits> using Cmp = integral_constant<decltype(&comp), &comp>; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; }

pair 函式庫 #include <utility> 宣告 pair<data_type1, data_type2> Pair_name; 初始化 pair<int, int> p1; // 宣告但不初始化 pair<int, char> p2(1, 'a'); // 不同資料型態的初始化 pair<int, int> p3(1, 10); // 同資料型態的初始化 pair<int, int> p4(p3); // 利用其它 pair 來初始化 pair<int, int> p5 = {1, 2} // 用 assign 的方式初始化 p2 = make_pair(1, 'a'); // 利用 make_pair 函式 成員 .first .second 函式 1. make_pair(v1, v2); 2. pair1.swap(pair2); 3. tie(a,b) 示例 #include <iostream> #include <utility> using namespace std; int main(){ // initialize pair<int,int> p1; pair<int,int> p2(2,4); pair<int,char> p3(3,'c'); pair<int,int> p4(p2); pair<int,int> p5 = {5,10}; // member cout << p2.first << " " << p2.second << endl; // 2 4 cout << p3.first << " " << p3.second << endl; // 3 c cout << p4.first << " " << p4.second << endl; // 2 4 cout << p5.first << " " << p5.second << endl; // 5 10 // function p1 = make_pair(1,2); cout << p1.first << " " << p1.second << endl; // 1 2 // a.swap(b) p1.swap(p2); cout << p1.first << " " << p1.second << endl; // 2 4 cout << p2.first << " " << p2.second << endl; // 1 2 // tie(a,b) = pair int a, b; tie(a, b) = p1; cout << a << " " << b << endl; // 2 4 return 0; }

HDLBits HDLBits 是一系列小型電路設計的練習，用於使用 Verilog 硬體描述語言(HDL)進行數位硬體設計。 由教學的題型由淺入深，逐步建立起電路設計的技能。 每個問題都會要求讀者使用 Verilog 設計一個小電路。HDLBits 會對提交的程式碼作判讀。透過一組測試碼來進行向量模擬，並與解答比較，檢查正確性。 Catalog 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 1 Getting Started \(\text{assign one}\) Build a circuit with no inputs and one output. The output should always drive 1 (or logic high). module top_module( output one); assign one = 1'b1; endmodule \(\text{assign zero}\) Build a circuit with no inputs and one output that outputs a constant 0. module top_module( output zero ); assign zero = 1'b0; endmodule

1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 2 Verilog Language 2.1 Basics wire Create a module with one input and ont output that behaves like a wire module top_module( input in, output out); assign out = in; endmodule multi-in-out Create a module with 3 inputs and 4 outputs that behaves like wires that makes these connections: module top_module( input a,b,c, output w,x,y,z ); assign w = a; assign x = b; assign y = b; assign z = c; endmodule not gate Create a module that implements a NOT gate. module top_module( input in, output out ); assign out = ~in; endmodule and gate Create a module that implments an AND gate. module top_module( input a,b, output out ); assign out = a & b; endmodule nor gate Create a module that implements a NOR gate. A NOR gate is an OR gate with its output inverted. A NOR function needs two operators when written in Verilog. module top_module( input a,b, output out ); assign out = ~(a|b); endmodule xnor gate Create a module that implements a XNOR gate. module top_module( input a, b, output out ); assign out = ~(a^b); endmodule wire declaration Implement following circuits. Create two intermediate wires to connect the AND and OR gates together. Note that the wire that feeds the NOT gate is really wire out, so you do not necessarily need to declare a third wire here. Notice how wires are driven by exactly one source (output of a gate), but can feed multiple inputs. module top_module( input a,b,c,d, output out, out_n ); wire w1, w2; assign w1 = a & b; assign w2 = c & d; assign out = w1 | w2; assign out_n = ~out; endmodule 7458 The 7458 is a chip with four AND gates and two OR gates. Create a module with the same functionality as the 7458 chip. It has 10 inputs and 2 outputs. module top_module( input p1a, p1b, p1c, p1d, p1e, p1f, output p1y, intput p2a, p2b, p2c, p2d, output p2y ); wire w1a, w1b; wire w2a, w2b; assign w1a = p1a & p1b & p1c; assign w1b = p1d & p1e & p1f; assign p1y = w1a | w1b; assign w2a = p2a & p2b; assign w2b = p2c & p2d; assign p2y = w2a | w2b; endmodule 2.2 Vectors vector Build a circuit that has one 3-bit input, then outputs the same vector, and also splits it into three separate 1-bit outputs. Connect outputs o0 to the input vector’s position 0, o1 to position 1, etc. In a diagram, a tick mark with a number next to it indicates the width of the vector (or “bus”), rather than drawing a separate line for each bit in the vector. module top_module ( input wire [2:0] vec, output wire [2:0] outv, output wire o2, output wire o1, output wire o0 ); assign outv = vec; assign o0 = vec[0]; assign o1 = vec[1]; assign o2 = vec[2]; endmodule vector select Build a combinational circuit that splits an input half-word (16 bits, [15:0]) into lower [7:0] and upper [15:8] bytes. module top_module ( input [15:0] in, output [7:0] out_hi, output [7:0] out_lo ); assign out_hi = in[15:8]; assign out_lo = in[7:0]; endmodule vector swap A 32-bit vector can be viewed as containing 4 bytes (bits [31:24], [23:16], etc.). Build a circuit that will reverse the byte ordering of the 4-byte word. AaaaaaaaBbbbbbbbCcccccccDddddddd => DdddddddCcccccccBbbbbbbbAaaaaaaa This operation is often used when the endianness of a piece of data needs to be swapped, for example between little-endian x86 systems and the big-endian formats used in many Internet protocols. module top_module ( input [31:0] in, output [31:0] out ); assign out[31:24] = in[ 7: 0]; assign out[23:16] = in[15: 8]; assign out[15: 8] = in[23:16]; assign out[ 7: 0] = in[31:24]; endmodule vector gates uild a circuit that has two 3-bit inputs that computes the bitwise-OR of the two vectors, the logical-OR of the two vectors, and the inverse (NOT) of both vectors. Place the inverse of b in the upper half of out_not (i.e., bits [5:3]), and the inverse of a in the lower half. module top_module ( input [2:0] a, input [2:0] b, output [2:0] out_or_bitwise, output out_or_logical, output [5:0] out_not ); assign out_or_bitwise = a | b; assign out_or_logical = a || b; assign out_not[2:0] = ~a; assign out_not[5:3] = ~b; endmodule gate-prefix vector Build a combinational circuit with four inputs, in[3:0]. There are 3 outputs: out_and: output of a 4-input AND gate. out_or: output of a 4-input OR gate. out_xor: outout of a 4-input XOR gate. module top_module ( input [3:0] in, output out_and, output out_or, output out_xor ); assign out_and = & in; assign out_or = | in; assign out_xor = ^ in; endmodule vector concatenate Given several input vectors, concatenate them together then split them up into several output vectors. There are six 5-bit input vectors: a, b, c, d, e, and f, for module top_module ( input [4:0] a, b, c, d, e, f, output [7:0] w, x, y, z ); assign {w, x, y, z} = {a, b, c, d, e, f, 2'b11}; endmodule vector reverse Given an 8-bit input vector [7:0], reverse its bit ordering. module top_module( input [7:0] in, output [7:0] out ); assign {out[0], out[1], out[2], out[3], out[4], out[5], out[6], out[7]} = in endmodule module top_module( input [7:0] in, output [7:0] out ); always @(*) begin for (int i=0; i<8; i++) out[i] = in[8-i-1]; end endmodule module top_module( input [7:0] in, output [7:0] out ); generate genvar i; for (i=0; i<8; i = i+1) begin: my_block_name assign out[i] = in[8-i-1]; end endgenerate endmodule vector replication Build a circuit that sign-extends an 8-bit number to 32 bits. This requires a concatenation of 24 copies of the sign bit (i.e., replicate bit[7] 24 times) followed by the 8-bit number itself. module top_module ( input [7:0] in, output [31:0] out ); assign out = {{24{in[7]}}, in}; endmodule vector replication2 Given five 1-bit signals (a, b, c, d, and e), compute all 25 pairwise one-bit comparisons in the 25-bit output vector. The output should be 1 if the two bits being compared are equal. module top_module ( input a, b, c, d, e, output [24:0] out ); assign out = ~{{5{a}}, {5{b}}, {5{c}}, {5{d}}, {5{e}}} ^ {5{a,b,c,d,e}}; endmodule 2.3 Modules: Hierarchy By now, you’re familiar with a module, which is a circuit that interacts with its outside through input and output ports. Larger, more complex circuits are built by composing bigger modules out of smaller modules and other pieces (such as assign statements and always blocks) connected together. This forms a hierarchy, as modules can contain instances of other modules. ...