setup_class called once for the class setup_method called for every method one one after teardown_method called for every method setup_method called for every method two teardown_method called for every method setup_method called for every method three three after teardown_method called for every method teardown_class called once for the class
最近想複習基本的資料結構，首先第一個想到還給老師就是 heap 了。所以就從 heap 開始。 這次實作的是 max heap，定義如下圖所示，max heap 為一個完整二元樹 (complete binary tree)，且每個父節點皆大於等於其左右子節點，由於完整二元樹的性質， max heap 資料結構可以很方便的使用陣列來表示。
假設陣列 index i 從 1 開始，heap 用陣列來表示又可以延伸出以下節點間的性質：
有了以上的節點性質，就可以很方便的應用在以下的實作。首先介紹max heap裡面最重要的部分 max heapify，給定一個元素的 index，由 top-down 的方式遞迴檢查該節點及其左右子節點有無符合 max heap 定義，若無則調整之。程式碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13
defmax_heapify(a, i, heap_size): left_i = 2 * i + 1 right_i = 2 * i + 2
if left_i < heap_size and a[i] < a[left_i]: biggest = left_i else: biggest = i if right_i < heap_size and a[biggest] < a[right_i]: biggest = right_i if biggest != i: a[biggest], a[i] = a[i], a[biggest] max_heapify(a, biggest, heap_size)
而 max heapify 設計上是針對該點以及左右子結點，依深度優先搜尋路徑調整成 max heap，如果 max heapify 的起始是根節點，依序要將整顆樹都調整成max heap，是會有其盲點的，因為這樣不會考慮整體的樹皆為 max heap，所以max heapify的起始點要從最小的父節點開始，以 bottom up 的方式由小到大來調整才可以確保整棵樹都符合max heap性質，程式碼如下所示。
1 2 3 4 5
# build max-heap defbuild_max_heap(a, heap_size): for i inrange(len(a)//2-1, -1, -1): max_heapify(a, i, heap_size) print(f'max heap: {a}')
len(a)//2-1 表示從最後位置的父節點開始往前做 max heapify。最後介紹 max heap 應用，由小到大排列的 heap sort，程式碼如下。
if __name__ == '__main__': with server.HTTPServer(('', 8000), RequestHandler) as http_server: print('start simple web server...') http_server.serve_forever()
程式的內容為 client 向 server 發出請求後，會在瀏覽器頁面上印出該 server 的 hostname，如此就可以很方便的觀察之後負載均衡的行爲。
resolvers docker nameserver dns1 127.0.0.11:53 resolve_retries3 timeout resolve 1s timeout retry 1s hold other 10s hold refused 10s hold nx 10s hold timeout 10s hold valid 10s hold obsolete 10s
今天與公司的資深同事討論了爬蟲突破 IP 封鎖的技術，學習了有一個叫做洋蔥網路 (TOR) 的厲害技巧，是除了一般使用付費 proxy IP 外另一種突破 IP 封鎖的方式，以下紀錄我學習的心得。
TOR 的全名為 The Onion Project，發源至美國海軍開發的一個匿名交流網路。用戶端使用這種網路不會直接與要存取的目標電腦連線，而是會在兩者間隨機挑選多個中繼站當節點，形成一條連線路徑。而且每一個中繼結點間都會層層加密，只有目的地節點可以解密看到最終的內容，如此特性有如洋蔥多層的結構一樣複雜所以稱之，示意圖如下圖所示。
而 TOR 這種複雜的隨機多重代理特性，使得其難以追蹤使用者真實的來源IP，因此成為暗網活動最好的平台。python 也剛好有支援發送 TOR 請求的套件，以下為一個簡單的 tor 請求存取程式建立步驟。
首先，參考此篇安裝範例安裝 TOR 相關套件及設定，這裡我使用 docker Ubuntu 的 container 作為安裝環境，首先安裝 TOR。
