基於 Ollama 和 LangChain 的 Naive RAG 實作(搭配 streamlit UI)

在此為確保程式碼的可執行性,使用了免費的模型,若要求性能,可以使用替代方案。 完整程式碼 Basic Moves 1. 載入文件 loader = WebBaseLoader(urls_list) documents = loader.load() 使用 WebBaseLoader 從給定的 URL 列表中載入文件。在這裡可以根據需求替換其它 Loader。 PyPDFLoader 用於 PDF 文件。 TextLoader 用於純文本文件。 2. 分割文件 pythonCopytext_splitter = CharacterTextSplitter.from_tiktoken_encoder(chunk_size=7500, chunk_overlap=100) doc_splits = text_splitter.split_documents(documents) 文件分割是一個關鍵步驟。這裡使用 CharacterTextSplitter 並基於 tiktoken 編碼器進行分割。 參數說明: chunk_size: 定義每個 chunk 的最大 token 數。較大的 chunk 可能包含更多上下文,但可能降低檢索精度。 chunk_overlap: 定義相鄰塊之間的重疊 token 數。增加重疊可以幫助保持上下文連續性,但會增加記憶體需求。 替代方案: RecursiveCharacterTextSplitter: 可以更智能地處理文檔結構。 TokenTextSplitter: 直接基於標記進行分割,可能更準確但速度較慢。 3. 選擇 embedding 模型 pythonCopyembeddings = OllamaEmbeddings(model="mistral") 這裡使用 Ollama 的 Mistral 模型生成嵌入。 替代方案: OpenAI HuggingFace Gemini 4. 創建向量資料庫 pythonCopyvector_store = Chroma.from_documents( documents = doc_splits, embedding = embeddings, collection_name = "rag-chroma", ) 替代方案: FAISS (Meta 的) Milvus Pinecone 5. 建立 Retriever Interface retriever = vector_store.as_retriever() 可以通過設置參數 search_type 與 search_kwargs 來調整檢索行為。 6. 執行 RAG rag_chain = ( {"context": retriever, "question": RunnablePassthrough()} | prompt | llm | StrOutputParser() ) 定義 RAG 鏈。可以通過修改 prompt 或使用不同的 LLM 來優化性能。 7. 查詢 return rag_chain.invoke(question) 調用 RAG 鏈針對輸入的問題返回答案。 Advanced Moves 加入 metadata 並進行篩選: loader = WebBaseLoader(urls_list) loader.requests_kwargs = {'verify':False} docs = loader.load() docs = [Document(page_content=doc.page_content, metadata={"source": doc.metadata['source']}) for doc in docs] # 在檢索時使用 metadata 篩選 retriever = vector_store.as_retriever(search_kwargs={"filter": {"source": "特定URL"}}) 加入 pre/post retrieval 處理: from langchain.retrievers import ContextualCompressionRetriever from langchain.retrievers.document_compressors import LLMChainExtractor compressor = LLMChainExtractor.from_llm(llm) compression_retriever = ContextualCompressionRetriever( base_compressor=compressor, base_retriever=retriever ) 加入 rerank 提升回答的加權: from langchain.retrievers import EnsembleRetriever bm25_retriever = BM25Retriever.from_documents(documents) ensemble_retriever = EnsembleRetriever( retrievers=[retriever, bm25_retriever], weights=[0.5, 0.5] ) 改變 naive RAG 為 graph RAG: from langchain.graphs import NetworkxEntityGraph from langchain.indexes import GraphIndexCreator graph_creator = GraphIndexCreator( graph_type=NetworkxEntityGraph, include_embeddings=True ) graph = graph_creator.from_documents(documents) # 使用 graph RAG retrieved_nodes = graph.get_relevant_nodes(query)

July 30, 2024 · 2 分鐘 · Rain Hu

[Swift] UI Challenge

Challenge 1: Card Style struct ContentView: View { var body: some View { ZStack { Color(.systemMint) .ignoresSafeArea() VStack(alignment: .leading, spacing: 20.0){ Image("eva") .resizable() .aspectRatio(contentMode: .fit) .cornerRadius(15) .padding(.all) HStack { Text("Eva Hsu") .font(.largeTitle) .fontWeight(.semibold) .foregroundColor(.black) .padding() Spacer() VStack { HStack { Image(systemName: "star.fill") Image(systemName: "star.fill") Image(systemName: "star.fill") Image(systemName: "star.fill") Image(systemName: "star.leadinghalf.fill") } .foregroundColor(.orange) .font(.caption) Text("(Reviews 240,152)") } .padding() } Text("The best girl in the world.") .foregroundColor(.primary) .padding(.horizontal) HStack { Spacer() Image(systemName: "binoculars.fill") Image(systemName: "fork.knife") } .foregroundColor(.gray) .font(.caption) .padding() } .background(Rectangle() .foregroundColor(.white) .cornerRadius(15) .shadow(radius: 15)) .padding() } } }m

June 21, 2024 · 1 分鐘 · Rain Hu

[System Design] 系統設計概念與資源 System Design and Resources

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

March 26, 2024 · 1 分鐘 · Ashish Pratap Singh, Rain Hu
Oh! You closed up the window, so you cannot see raining

[Hugo] 使用 Hugo-notice

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 >}} ...

January 19, 2024 · 2 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[ML] 機器學習與統計學

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}\) ...

November 7, 2022 · 1 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[C++] Segment Tree

線段樹 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); } };

October 18, 2022 · 8 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[C++] stringstream 類範例 - split 與 concat

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; } };

October 14, 2022 · 1 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[ML] introduction

什麼是 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。 ...

June 19, 2022 · 1 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[C++] The C++ Standard Template Library(STL) - deque

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等。 當上面的塊被填滿時,指標將創建一個新塊並開始指向一個新的數位塊。這為更多數據創造了空間。在這種情況下,也可以填充指標塊。這會導致一個問題。 這是加倍來救援的時候。在加倍時,指標陣列的大小加倍。這不會複製整個數據,而只會複製指標。這是許多人在討論恆定時間時提出的一般論點。時間在調用的複製構造函數數方面保持不變。 如果數據集非常大,則指標塊幾乎不會執行加倍,因為單個指標可以指向大量數據塊。因此,指標陣列被填充並加倍的可能性非常小。

June 12, 2022 · 1 分鐘 · Rain Hu
Oh! You closed up the window, so you cannot see raining

[C++] Custom Comparator

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; }

June 11, 2022 · 2 分鐘 · Rain Hu