ARTS Week 38

從零開始

Algoithm

單詞拆分

概述

給定一個非空字元串 s 和一個包含非空單詞的清單 wordDict，判定s是否可以被空格拆分為一個或多個在字典中出現的單詞。

說明：

拆分時可以重複使用字典中的單詞。 你可以假設字典中沒有重複的單詞。

示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true 
解釋: 傳回 true 因為 "leetcode" 可以被拆分成 "leet code"。
           

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true 
解釋: 傳回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重複使用字典中的單詞。
           

示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
           

分析

這種判斷是否可以組合，都是一種極值判斷，大概的方向是遞歸問題。

那麼接下來還是老三步：

1. 狀态
2. 選擇
3. 函數

狀态

首先這裡的狀态可以從問題入手，其中需要到最後是否滿足，那麼其中每一都可以判斷是否滿足，這樣狀态就變成了，從0-i 中，wordDict 是否滿足？

選擇

1. 特殊情況
   1. 如果均為空，那麼為空的情況，結果肯定為真。
2. 多種選擇
   1. 0-i 判斷
   2. 中間增加一個 j，從0-j，j-i 均滿足，得到轉換 dp[i]=dp[j] && check(s[j…i−1])

函數

1. dp 定義
2. 狀态選擇
3. 傳回結果

code

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 狀态 目前i,j 是否為0
        # 選擇 0-i 中進行切割，0-j,j-i 中可以切割。
        size = len(s)
        dp = [False] * (size + 1)
        dp[0] = True
        # 使用哈希表快速同步
        word_map = {i: True for i in wordDict}
        # 使用dp算法，進行計算
        for i in range(1, size + 1):
            for j in range(i):
                if dp[j] and word_map.get(s[j:i]):
                    dp[i] = True
                    break
        return dp[-1]

           

總結

1. 關于狀态
   1. 動态問題 可以從問題入手，問題的最終判斷即為單個的狀态
2. 關于選擇
   1. 選擇可以通過多層循環完成，從中的狀态進行選擇

Review

FastAPI Documentation

概述

FastAPI is a modern, fast (high-performance), web framework for building APIs with Python 3.6+ based on standard Python

type hints.

The key features are:

• Fast: Very high performance, on par with NodeJS and Go (thanks to Starlette and Pydantic). One of the fastest

  Python frameworks available.

• Fast to code: Increase the speed to develop features by about 200% to 300%. *
• Fewer bugs: Reduce about 40% of human (developer) induced errors. *
• Intuitive: Great editor support. Completion everywhere. Less time debugging.
• Easy: Designed to be easy to use and learn. Less time reading docs.
• Short: Minimize code duplication. Multiple features from each parameter declaration. Fewer bugs.

• Robust: Get production-ready code. With automatic interactive documentation. Standards-based: Based on (and fully

  compatible with) the open standards for APIs: OpenAPI (previously known as Swagger) and JSON Schema.

Tip

我查這麼多資料，會不會把資料庫記憶體打爆？

概述

問題：

我的主機記憶體隻有 100G，現在要對一個 200G 的大表做全表掃描，會不會把資料庫主機的記憶體用光了？

分成兩個次元：

1. 全表掃描對于 Server 層的影響
2. 全表掃描對 InnoDB 的影響

Server 層

示例：

流程

實際上，服務端并不需要儲存一個完整的結果集。取資料和發資料的流程是這樣的：

1. 擷取一行，寫到 net_buffer 中。這塊記憶體的大小是由參數 net_buffer_length 定義的，預設是 16k。
2. 重複擷取行，直到 net_buffer 寫滿，調用網絡接口發出去。
3. 如果發送成功，就清空 net_buffer，然後繼續取下一行，并寫入 net_buffer。
4. 如果發送函數傳回 EAGAIN 或 WSAEWOULDBLOCK，就表示本地網絡棧（socket send buffer）寫滿了，進入等待。直到網絡棧重新可寫，再繼續發送。

Mysql是邊讀邊發，但是如果用戶端接收比較慢，就會導緻事務執行時間變長。狀态一直顯示 “Sending to client”

建議

對于正常的線上業務來說，如果一個查詢的傳回結果不會很多的話，我都建議你使用 mysql_store_result 這個接口，直接把查詢結果儲存到本地記憶體。

“Sending data”

這一狀态顯示資料可能會在連結中等各種狀态

InnoDB

1. WAL機制
2. BP管理
3. LRU 算法以及優化

WAL機制

Write-Ahead Logging，先寫日志，再寫磁盤。

具體來說，當有一條記錄需要更新的時候，InnoDB 引擎就會先把記錄寫到 redo log（粉闆）裡面，并更新記憶體，這個時候更新就算完成了。同時，InnoDB

引擎會在适當的時候，将這個操作記錄更新到磁盤裡面，而這個更新往往是在系統比較空閑的時候做，這就像打烊以後掌櫃做的事。

BP管理

核心因素是命中率

show engine innodb status

LRU算法

最近最久未使用

基本的LRU算法

1. 在圖 6 的狀态 1 裡，連結清單頭部是 P1，表示 P1 是最近剛剛被通路過的資料頁；假設記憶體裡隻能放下這麼多資料頁；
2. 這時候有一個讀請求通路 P3，是以變成狀态 2，P3 被移到最前面；

3. 狀态 3 表示，這次通路的資料頁是不存在于連結清單中的，是以需要在 Buffer Pool 中新申請一個資料頁 Px，加到連結清單頭部。但是由于記憶體已經滿了，不能申請新的記憶體。于是，會清空連結清單末尾 Pm 這個資料頁的記憶體，存入 Px

   的内容，然後放到連結清單頭部。

4. 從效果上看，就是最久沒有被通路的資料頁 Pm，被淘汰了。

那麼，按照這個算法掃描的話，就會把目前的 Buffer Pool 裡的資料全部淘汰掉，存入掃描過程中通路到的資料頁的内容。也就是說 Buffer Pool 裡面主要放的是這個曆史資料表的資料。

對于一個正在做業務服務的庫，這可不妙。你會看到，Buffer Pool 的記憶體命中率急劇下降，磁盤壓力增加，SQL 語句響應變慢。

改進後的一些修改

在 InnoDB 實作上，按照 5:3 的比例把整個 LRU 連結清單分成了 young 區域和 old 區域。圖中 LRU_old 指向的就是 old 區域的第一個位置，是整個連結清單的 5/8 處。也就是說，靠近連結清單頭部的 5/8 是

young 區域，靠近連結清單尾部的 3/8 是 old 區域。改進後的 LRU 算法執行流程變成了下面這樣。

1. 圖 7 中狀态 1，要通路資料頁 P3，由于 P3 在 young 區域，是以和優化前的 LRU 算法一樣，将其移到連結清單頭部，變成狀态 2。
2. 之後要通路一個新的不存在于目前連結清單的資料頁，這時候依然是淘汰掉資料頁 Pm，但是新插入的資料頁 Px，是放在 LRU_old 處。
3. 處于 old 區域的資料頁，每次被通路的時候都要做下面這個判斷：
   1. 若這個資料頁在 LRU 連結清單中存在的時間超過了 1 秒，就把它移動到連結清單頭部；
   2. 如果這個資料頁在 LRU 連結清單中存在的時間短于 1 秒，位置保持不變。1 秒這個時間，是由參數 innodb_old_blocks_time 控制的。其預設值是 1000，機關毫秒。

Share

關于業務邏輯抽象

概述

業務抽象 : 整體可以設計成 底層無狀态抽象，中層業務組建抽象，業務線開發

首先從公司角度出發，對于創業公司/藍海時代，需要快速切入不同場景，能夠實作快速接入。這種模式下需要走廣度優先(DFS)政策。是以需要對自身的産品進行較為抽象的邏輯思考。

以機器人為例：

1. 位置
2. 資訊
3. 動作

這種抽象能夠快速的搭建，底層的邏輯抽象。實作一種最基礎的邏輯抽象，無狀态、無業務的底層抽象。

中層是業務組建抽象：将中層不同業務需要的公共元件，實作可插播方式快速支撐。例如：支付子產品/鑒權子產品/基礎位置子產品/N叉樹子產品 等等。

業務線開發：這裡會有很多定制化開發項目，例如：第三方對接/特殊推送/定制化回調等。