演算法讀書筆記

CH1

MergeSort: divide-and-conquer經典範例

輸入: 一個沒有規則的數字陣列。
輸出: 排序好的數字陣列
MergeSort是divide-and-conquer方法的展現。recursive divide-and-conquer algorithm是不斷的利用遞迴把問題拆變小,直到問題不能在拆分後再把結果合併回來。對於array把問題變小的方式最直覺就是把array拆兩半,拆到最後再慢慢把array合併回來。

下面是MergeSort的Pseudocode

1
2
3
4
5
6
7
Input: array A of n distinct integers.
Output: array with the same integers, sorted from
smallest to largest.
// ignoring base cases
C := recursively sort first half of A
D := recursively sort second half of A
return Merge (C,D)

這段程式碼有幾點可以注意

  • base cases: 也就是沒辦法再分割,沒辦法再繼續遞迴,返回它自身就是他的回傳值。
  • Pseudocode不包含實作細節,例如如果輸入是奇數個元素的狀況下,我們可以將多出的一個element放入一半被拆分的array。Pseudocode只記錄概念上的運作方式,並不會加入任何和個別程式語言有關的實作細節。

在上面的Pseudocode還有一個Merge函式,下面是關於Merge函式的Pseudocode。想法是將
排序好的C和D array依序再排序成新的排序過的array。

1
2
3
4
5
6
7
8
9
10
11
12
13
Merge
Input: sorted arrays C and D (length n/2 each).
Output: sorted array B (length n).
Simplifying assumption: n is even.
1 i := 1
2 j := 1
3 for k := 1 to n do
4 if C[i] < D[j] then
5 B[k] := C[i] // populate output array
6 i := i + 1 // increment i
7 else // D[j] < C[i]
8 B[k] := D[j]
9 j := j + 1

1.5 MergeSort: The Analysis

計算演算法速度的方式就是計算這個演算法總共需要執行多少次最基礎的計算。也就是計算Running Time

1.5.1 Running Time of Merge

Lemma 1.1 (Running Time of Merge) 對於合併兩個長度為$l/2$的array的,合併最多只會用到6l步(可從前面Merge的Pseudocode推論。)

1.5.2 Running Time of MergeSort

Theorem 1.2 (Running Time of MergeSort) : 對於每個長度$n\geq 1$的array, MergeSort的Merge步驟最多執行$6nlog_2n+6n$個步驟

1.5.3 Proof of Theorem 1.2

從recursion tree 可以看到,每多一個遞迴level,工作被分割的總數就是兩倍,但是工作的array長度是上一個level的一半。因此level-j的subproblems為$2^j$,而level-j地array長度為$n/{2^j}$。根據上一節的結論,對於每個長度$n\geq 1$的array, MergeSort最多執行$6nlog_2n+6n$個步驟。如果我們只看level-j遞迴呼叫以外的工作,就只剩下Merge步驟,因此每個level的運算步驟總共為$6n/2^j$
於是我們可以得到level-j所有的運算步驟總數為$2^j \cdot \frac{6n}{2^j}=6n$
而MergeSort總共會有$log_x^n+1$個level,因此整個MergeSort總共的步驟為$6nlog_2n+6n$

1.6 Guiding Principles for the Analysis of Algorithms

我們在計算演算法速度的時候會有三個原則,以下逐一介紹。因為在有些時候為了簡化計算,我們會做出一些取設,但是為了讓數學分析依然能夠預測演算法的速度,因此我們才用到下面三個原則。

Principle #1: Worst-Case Analysis

在前面推導的結果$6nlog_2n+6n$是不管n是什麼數字這個公式都能夠使用。也就是我們沒有對n做任何的假設。這種分析法稱為Worst-Case Analysis,因為這個演算法最慢的計算時間依然符合這個公式。
除了Worst-Case Analysis之外還有average-case analysis和 analysis of benchmark instances可以使用,但是這兩個使用的時候必須非常清楚所處理的問題的條件。

Principle #2: Big-Picture Analysis

在運行時間界限中,我們不應過於關注小的常數因子或低階項。

參考

Algorithms Illuminated

deepstream-tracker參數調整

Accuracy-Performance Tradeoffs

下面這些參數的調整將會影響到準確度和效能。

Visual Feature Types and Feature Sizes

Visual feature types

  • useColorNames
  • useHog

Feature sizes

  • featureImgSizeLevel
  • searchRegionPaddingScale

Linux使用SOCKS5-proxy上網

簡介

這裡將介紹一個只需要使用SSH連線到一台可以連到對網網路的主機,就可以讓防火牆內的主機上網的方法
圖片說明

注意Docker pull沒辦法用proxychains,解法在後面

利用ssh連接到可以上網的機器

首先本機電腦和遠端電腦都必須有ssh server
首先在本機電腦ssh登入到遠端沒有外網的遠端電腦,然後在遠端電腦使用以下指令連回去本機電腦建立一條SOCKS5 proxy的通道。

1
ssh -D 9050 -q -C -N local_username@192.168.50.1

檢查SOCKS是否開通了

https://superuser.com/questions/303251/how-to-check-if-a-socks5-proxy-works

遠端電腦用以下指令可以檢查開通的port

1
netstat -tlnp

假設我們在9050port開SOCKS proxy,如果有成功開啟SOCKS proxy,應該會看到下面這行

1
tcp        0      0 127.0.0.1:9050          0.0.0.0:*               LISTEN  

安裝Proxychains4

https://blog.csdn.net/leishupei/article/details/120736869
sudo apt-get install proxychains4

在還沒安裝Proxychains4機器上用SOCKS5安裝Proxychains4

1
2
3
 apt -o Acquire::http::Proxy="socks5h://127.0.0.1:9050" -o Acquire::https::Proxy="socks5h://127.0.0.1:9050" update

apt -o Acquire::http::Proxy="socks5h://127.0.0.1:9050" -o Acquire::https::Proxy="socks5h://127.0.0.1:9050" install proxychains4

設定Proxychains4

https://feifei.tw/proxychains4/

sudo nano /etc/proxychains4.conf
proxy_dns 的功能不要關掉

設定檔位置
https://askubuntu.com/a/1477936

手動設定DNS server

export DNS_SERVER=8.8.8.8

https://github.com/rofl0r/proxychains-ng/issues/178#issuecomment-347439800

測試apt指令

proxychains4 sudo apt install zip

docker pull 無法使用proxychains4的解法

1
2
sudo mkdir -p /etc/systemd/system/docker.service.d
sudo nano /etc/systemd/system/docker.service.d/proxy.conf
1
2
3
[Service]
Environment="HTTP_PROXY=socks5://127.0.0.1:9050"
Environment="HTTPS_PROXY=socks5://127.0.0.1:9050"
1
2
sudo systemctl daemon-reload
sudo systemctl restart docker

https://docs.docker.com/engine/daemon/proxy/

https://markvanlent.dev/2022/05/10/pulling-docker-images-via-a-socks5-proxy/

elasticsearch API

search

使用keyword使得搜尋條件必須完全符合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
GET people-2023.04/_search
{ "query":
{
"bool": {
"must": [
{
"range": {
"@timestamp": {
"gt" : "2023-04-08T10:22:28Z",
"lt" : "2023-04-08T10:22:44Z"
}
}
},
{
"match": {
"StreamID.keyword": "eb2baea2-d52c-434c-af44-256c0301f4df"
}
}
]
}
}
}

delete

1
2
3
4
5
6
7
8
9
10
POST poc/_delete_by_query
{
"query":{
"range":{
"@timestamp":{
"gt" : "2018-05-04T23:04:00Z"
}
}
}
}

樹梅派學習Liunx

CH1

  • 樹梅派不適合做real-time的應用
  • 樹梅派不適合作為production的應用,如果要做成production的應用,可以考慮BeagleBone
  • 其他參考資源:
  • 建議購買的配件
    • USB to Serial UART TTL 3.3 V (for Finding Problems)線,可以用於透過USB就可以使用command line控制樹梅派