Iterable and Iterator

Iterator & Iterable

  • get next item (__next__)
  • no indexes needed (Don’t need to be Sequence type)
  • consumable

iterable

  • collections that implement iterator

Protocal

Python need to count on certain funcionality: __next____iter__StopIteration

compare to sequence type

iteration can be more general than sequential indexing, we only need:

  • a bucket of items: collection, container
  • a way to get the next item, no need to care about ordering
  • an exception to raise if there is no next item

try to custom an iterator ourselfs:

Why re-create?

Seperate the Collection from the iterator

Iterable object

  • Maintaining the data of the collection is one object
  • Created once
  • implements __iter__, return a new iterator instance

Iterator object

  • Iterating over that data should be another object
  • throw away the iterator but don’t throw away the collection
  • Created every time
  • implements __iter__, return itself
發表留言

序列 – Python Sequence

Sequence

必須足以下條件:

  • 物件的集合
  • countable
  • zero based indexing (__getitem__)
  • 為什麼 index 要從0開始?
    • 0 based: 0 <= n < len(s)
    • 1 based: 1 <= n < len(s) + 1 Upper bound 用小於的原因是計算長度時不須再+1
  • 有序(positional ordering)
    • 舉例來說 list 和 set 都是物件的容器,但 list 可以被排序, set 不行,因此 list 是 Sequence Type 而 set 不是

特性:

  • Homogeneous vs Heterogeneous 同質即序列的物件型態必須是相同的
  • Iterable vs non iterable 可以迭代的容器不一定是序列,如set
  • Mutable vs Immutable Mutable sequence can be modified. 要注意的是在操作新序列的時候更動到原本的序列(in-place),如 reverse()

以 list 為例,這幾個操作皆為原地算法(inplace):

  • l.clear()
  • l.append()
  • l.pop()
  • l.extend()
  • l.insert()
  • l +=
  • l *=
  • l[somesliceobj] = 若是 concat(+)、repetition(*)、slicing 都是關聯至新的物件參考

要注意的是,容器序列(儲存物件參考)的 concat 和 repetition 有可能只是儲存多個相同物件的參考

Read more “序列 – Python Sequence”

發表留言

Python WSGI及其應用

tags: python, wsgi, gunicorn, uwsgi

Python WSGI及其應用

WSGI是什麼?

  • 全名Python Web Server Gateway Interface
  • 基於CGI
  • Python用來描述了伺服器和請求處理程式之間傳輸資料的一種標準(協議)

PEP3333

基本原理跟目標

server、app、framework共用的界面

…proposes a simple and universal interface between web servers and web applications or frameworks: the Python Web Server Gateway Interface (WSGI).

不再重造輪子

…the goal of WSGI is to facilitate easy interconnection of existing servers and applications or frameworks, not to create a new web framework

只會支援python既有的release

…precludes WSGI from requiring anything that is not already available in deployed versions of Python

未來會增加部署的標準

…current version of WSGI does not prescribe any particular mechanism for “deploying” an application for use with a web server or server gateway. At the present time, this is necessarily implementation-defined by the server or gateway

Read more “Python WSGI及其應用” 發表留言

以Python實作演算法 – Algorithms Implements using Python

TOC

圖論 Graph Theory

G(V, E)

  • 由頂點(vertex, node)和連接頂點的邊(Edge)關聯成的圖形
  • 其中關聯分作有方向性(directed)及無方向性(undirected)
  • 須考慮最大流問題(maximum flow)

在程式語言有幾種方式來建構Graphs:

相鄰矩陣 adjacency matrixes

image
圖片來源

陣列 edge list representation

應用

  • 最短路徑演算法 Shortest Path Algorithm: GPS, 高頻交易
  • 生成樹協定 Spanning Tree Protocol, STP
  • 爬蟲

參考:
Flow Networks:Maximum Flow & Ford-Fulkerson Algorithm

廣度優先搜尋 Breadth-first Search, BFS

  • 時間複雜度:O(V+E)(分別遍歷所有節點和各節點的所有鄰居)
  • 空間複雜度:O(V)(Queue中最多可能存放所有節點)
  • 用於有效率的迭代(traversal)
  • 迭代的方式為鄰近的先訪問(level-ordered)
  • 劣勢在於儲存指標記憶體空間,有時用DFS替代
  • 使用FIFO的Queue來實作,Queue為空代表完成迭代

應用

  • machine learning
  • Edmonds-Karp演算法
  • Cheney演算法

以Python實作,輸出請參考gist

參考:
Graph: Breadth-First Search(BFS,廣度優先搜尋)

深度優先搜尋 Depth-first Search, DFS

  • 時間複雜度:O(V+E)
  • 空間複雜度:O(logV)(訪問至末端節點後LIFO,Stack最多只會同時存在logV個節點,也就是樹的高度)
  • 為了解Maze Problem而生的演算法
  • 效能比BFS稍佳
  • 使用LIFO的Stack來實作

應用

  • 拓撲排序 Topological Order
  • Kosaraju演算法: 推薦系統 Recommand System
  • 判斷Grapth是否有cycle(DAG)
  • Maze

以Python實作,輸出請參考gist

參考:

Read more “以Python實作演算法 – Algorithms Implements using Python”

發表留言

Python模組與套件 – module, package in Python

在開始前,會需要先具備Scope的基本觀念:Python變數範圍 – Scope


Module

module只是物件,來自特定的python資料型別types.ModuleType

import做了什麼事?

Python會直接從系統找尋已經存在的cache,若找不到此模組,才會繼續以下操作:
1. 建構一個ModuleType物件
2. 將此物件動態(in run time)載入記憶體
3. 將此物件的關聯被加到global namespace,可透過globals()訪問
4. 將物件的關聯加到系統cache,可透過sys.modules訪問
5. 編譯及執行該模組的source code

用一個最直接的例子來驗證caching(但這樣寫有大麻煩,請勿這樣用):

那以上這些動作可不可以自己來呢?可以!步驟大致上長這樣:

除此之外,也可以透過importlib.import_module來載入

這些模組從哪裡來?

  • built-in
  • 硬碟上的特定檔案,可透過__file__訪問

模組可以來自一般(.py)、預先編譯(.pyc)、壓縮檔(.zip)等…幾乎是沒什麼限制只要finders能找得到

python怎麼找到特定模組?——finders和loaders

Python:「Finder一號,你知道這個module在哪裡嗎?」
Finder一號: 「拍謝,我不知道ㄟ」
Python:「Finder二號,你知道這個module在哪裡嗎?」
Finder二號:「哦哦哦!我知道!來,我給你一張地圖,上面有說去哪找,也有說> 明找到後要交給Loader五號,他會幫你處理滴。」
Python:「Loader五號大大,請你幫我處理我手中這個module。」
Loader五號:「沒問題!」

上面這個對話裡的地圖,就是ModuleSpec(可以透過importlib.util.find_spec來取得)

透過sys.meta_path可以看到目前所有的Finders

所以客製化自定義的finder跟loader是完全可行的,或是自訂一個importer處理所有操作,可以參考Site-specific configuration hook

不同import的方式(variants)

  • from math import sqrt
    1. 使用cache或載入math(一樣載入整個math module),但math不加到global namespace
    2. sqrt(symbol)加到global namespace且reference至math.sqrt
  • from math import sqrt as r_sqrt
    1. 使用cache或載入math(一樣載入整個math module),但math不加到global namespace
    2. r_sqrt(symbol)加到global namespace且reference至math.sqrt
  • from math import *
    1. 使用cache或載入math(一樣載入整個math module),但math不加到global namespace
    2. 將math定義過所有的symbol和各自的reference加到global namespace

對module來說,以上這些變化,其實都是載入整個module,只差在namespace加的變數不同,所以並沒有部份載入這回事(載入package的行為就會不同,可以做到部份載入)

以上這些變化在效率上差別很小,只差在lookup的次數,如math.sqrt(2)sqrt(2),所以還是依照需求來決定怎麼寫,並非from的寫法就一定比較好

值得注意的是,from import *可能會導致錯誤,因為相同名稱的symbol會在namespace中依照先後順序互相覆蓋,舉例來說:

此外,有時會避免symbol撞名導致覆蓋,會選擇在local scope來載入,這樣做的載入效能會差,lookup次數的效能差別也會更為顯著

__name____main__

__name__變數用來顯示當前模組的名稱;如果該模組是程式入口,呼叫__name__的值時Python會回傳__main__字串,因此我們可以藉此模擬一種情境,來判斷當下的模組是否為程式入口:

Package

套件即是模組,但是此模組是由多個模組或子套件封裝而成,也就是目錄(directory)的概念,套件的名稱為目錄名,套件的屬性__path__為目錄的絕對路徑

Python透過__path____file____package__這些屬性來找到、封裝及載入你要的程式碼:

套件的入口__init__.py:

  • 告訴Python:請把這個目錄當作一個套件
  • 套件的__file__屬性即自身__init__.py的絕對路徑

幾個套件namespaces的封裝方法:

  • __init__.py
  • 將變數命名為私有(_)
  • __all__

Namespace package

與一般的套件相比,Namespace package不透過__init__.py封裝(沒有__file__屬性),其中的子套件可以來自不同的目錄位置

發表留言

Python閉包及裝飾器的應用 – Closure and Decorator in Python

在開始前,會需要先具備Scope的基本觀念:Python變數範圍 – Scope


Closure

在函數執行時,會建立一個local scope,當函數執行完,這個local scope並不會被清除——而且只要你知道怎麼再次訪問,它都會確保你訪問得到其中的變數

Decorator

decorator的概念即是透過closure的特性,將傳入的函式經裝飾後回傳一介面,如以下範例:

經裝飾後回傳都會是同一個介面,這樣會導致debug的困難:

可以用built-in的wraps來處理,wraps是decorator,一樣要把函式傳入

decorator可以堆疊,以下這個範例其實只是做了auth(log(f))這樣的處理

Decorator Factory

至於decorator乍看之下可以傳額外的參數,其實只是再多封裝了一層decorator:

Decorator Class(用於decorator的類別)

此外,我們也能透過callable物件來製作decorator

Class Decorator (用來裝飾類別的decorator)

Python的monkey paching特性(在程式的runtime能隨意更改物件屬性),我們也可以透過decorator來裝飾類別

其他範例:
functools.totoal_ordering

Dispatching pattern

發表留言

Python變數範圍 – Variable Scope

讓我們來討論一下這個簡單的語句:

這裡做了物件賦值(assign)這個行為,也可以說這個變數名稱(variable name)綁定(bound)到某物件上,這個物件可以透過變數(a)來訪問,但要注意…不是在程式碼任何一處都可以!

先來理解一下這些概念:

  • scope(lexical): 簡單來說,就是變數宣告(綁定)的地方

  • namespace: 命名空間紀錄這些綁定行為,每個scope都會有一份命名空間的字典來提供查找

image

Scope的類型

  • global scope
    • 或稱module scope,範圍是單個檔案(*.py)
    • 模組(或app)是層層堆疊起來的,並不會說哪裡才是真正的global環境,要說的話,最接近的可能就是built-in的變數如True、None所宣告的地方吧
  • local scope(in compile time)
    function為範圍,scope伴隨函式被呼叫時建立,變數重新綁定

當在特定的scope下找不到特定的變數,python會往外部的命名空間查找,順序是local>global>built-in。例如:

a在module scope被找到,print最後在built-in scope被找到,但找不到b,導致NameError

對於外部的scope已經存在的變數,在當前的scope再宣告一個同樣的變數名稱,這個動作叫做mask,因為在不同的scope,這樣做並不會影響到外部的變數(某個版本以前的list comprehension會發生這種狀況),除非有意為之

透過關鍵字globalnonlocal來操作

要注意nonlocal向外訪問只能訪問local scope的變數

此外,可以透過函數globalslocals輸出該scope的所有變數:

發表留言

Python的函式應用 – First-Class Function in Python

首先很快說明一下什麼是First-Class object(一級物件):

  • 可以被當參數傳遞的
  • 可以被回傳的
  • 可以賦值給變數
  • 可以以資料結構儲存

一級函式(First Class Function)

Python的物件型別如: int、float、string、tuple、list都屬於一級物件,function也是其中之一

高階函式(Higher Order Function)

  • 可以接收function當參數,或
  • 回傳的type是function

map, filter

docstring

docstring是程式碼不是註解,用意是替你的方法加上一段說明,根據PEP257的定義,加在function第一行的字串被視為docstring

另外一種加說明的的方式,根據PEP3107所定義的function annotation

Read more “Python的函式應用 – First-Class Function in Python”

發表留言

Python函式的參數設計 – Python Function Parameters

parameter跟argument的差異

基本上這兩者是一樣的,不過使用在不同的情境下。如果混用了其實是沒關係,可能也沒人會在意

不過值得一提的是以上這個範例的兩個參數在Module ScopeFunction Scope中都是指向同一個記憶體位置


可迭代物件的拆解機制(unpacking)

可迭代的物件都能拆解,很適合用在參數傳遞(主要使用在有序物件上)

超簡單實現swap

傳統的作法

unpacking的作法

使用***(3.5以上適用)

unpacking範例

巢狀的unpacking

Read more “Python函式的參數設計 – Python Function Parameters”

發表留言

以Python實作資料結構 – Data Structure Implements in Python

以Python實作資料結構

tags: data-structure, python

TOC

簡介

什麼是資料結構?為什麼要使用資料結構?

是電腦中儲存、組織資料的方式,可以讓我們有效地儲存資料,並讓所有運算能最有效率地完成

演算法的運行時間是根據資料結構決定的,所以使用適當的資料結構來降低演算法的時間複雜度,如:

  • 最短路徑演算法若無適當的資料結構,運行時間是O(N^2),使用(heap/priority queue)可以大幅降低運行時間至O(N*logN)

抽象資料型態 Abstract Data Types

簡單而言,ADT是針對資料結構的「規範」或「描述」,像是物件導向語言裡面的interface,但不會實作細節

舉例堆疊的ADT描述:

  • push(): 插入元素 item 至堆疊頂端
  • pop(): 移除並回傳堆疊頂端的元素
  • peek(): 看堆疊頂端的資料而不取出
  • size(): 看堆疊的長度

ADT跟資料結構的關係

每個ADT在底層都有相對應的資料結構去實作ADT裡定義過的行為(method)

ADT Data Structures
Stack array, linked list
Queue array, linked list
Priority Queue heap
Dictionary/Hashmap array

時間複雜度 Big O notation

描述演算法的效率(複雜度),舉例來說,A宅想要分享他的D槽給B宅,有以下幾種做法:

  1. 台北騎車到屏東B宅家
  2. 用網路傳輸,不考慮被FBI攔截的情況
1GB 1TB 500TB
騎車運送硬碟 600 min 600 min 600 min
網路傳輸 3 min 3072 min 1536000 min

從上表來看,騎車這個選項雖然聽起來很蠢,但不管硬碟有多大,都能確保10個小時內可以送達—— O(1);至於網路傳輸隨著檔案越大,所需的時間也越長 —— O(N);從這裡就可以看出常數時間(constant time)和線性時間(linear time)的差別對效率的影響有多大了

在表現複雜度函數的時候,有幾個通用的規則:

  • 多個步驟用加法: O(a+b)

  • 省略常數: ~~O(3n)~~ O(n)

  • 不同的input用不同的變數表示: ~~O(N^2)~~ O(a*b)

  • 省略影響不大的變數: ~~O(n+n^2)~~ O(n^2)

陣列 Array

物件或值的集合,每個物件或值可以被陣列的索引(index, key)識別

  • 索引從0開始
  • 因為有索引,我們可以對陣列做隨機存取(Random Access)

優點:

  • 隨機存取不用搜尋就能訪問陣列當中所有值,執行速度快O(1)
  • 不會因為鏈結斷裂而遺失資料
  • 循序存取快

缺點:

  • 重建或插入陣列須要逐一複製裏頭的值,時間複雜度是O(N)
  • 編譯的時候必須事先知道陣列的大小,這讓陣列這個資料結構不夠動態(dynamic)
  • 通常陣列只能存同一種型別
  • 不支援連結串列的共享

Implements

行為 big O
search 搜尋 O(1)
insert 插入第一項 O(N)
append 插入最後一項 O(1)
remove 移除第一項 O(N)
removeLast 移除最後一項 O(1)

以Python實作

random indexing: O(1)

linear search: O(n)

連結串列 Linked List & 雙向連結串列 Double Linked List

  • 節點包含datareferenced object
  • 連結的方式是節點(node)記住其他節點的參考(reference)
  • 最後一個節點的參考是NULL

優點

  • 各節點型態、記憶體大小不用相同
  • 動態佔用的記憶體,不須事先宣告大小
  • 插入、刪除快O(1)

缺點

  • 不支援隨機存取,只能循序存取(sequencial access),時間複雜度為O(N)
  • 須額外空間儲存其他節點的參考
  • 可靠性較差,連結斷裂容易遺失資料
  • 難以向前(backward)訪問,可以用雙向連結串列來處理,不過會多佔用記憶體空間

Implements

行為 big O
search 搜尋 O(N)
insert 插入第一項 O(1)
append 插入最後一項 O(N)
remove 移除第一項 O(1)
removeLast 移除最後一項 O(N)

註:連結串列沒有index,處理插入或移除第N項會需要先循序找到插入/移除位置,因此會需要O(N)的時間

以Python實作

以下的代碼是我實作的範例,有錯誤煩請指正。

主要概念是實作__getitem__來循序存取(indexing),另外Double Linked List支援反向存取,故訪問lst[0]lst[-1]皆可以達成O(1)的時間複雜度

執行結果請參考travishen/gist/linked-list.md

Linked List現實中的應用

  1. 低級別的內存管理(Low Level Memory Management),以C語言為例:
  • malloc()free(): 見Heap Management
  • chart * chart_ptr = (chart*)malloc(30);: 取得30byte的heap memory
  1. 許多Windows的應用程式:工具列視窗切換、PhotoViewer
  2. 區塊鏈技術

image
[圖片來源]

堆疊 Stack

Implements

行為 big O
push 將資料放入堆疊的頂端 O(1)
pop 回傳堆疊頂端資料 O(1)
peek 看堆疊頂端的資料而不取出 O(1)

應用

  • call stack + stack memory
  • 深度優先搜尋演算法(Depth-First-Search)
  • 尤拉迴路(Eulerian Circuit)
  • 瀏覽器回上一頁
  • PhotoShop上一步(undo)

註:任何遞迴(recursion)形式的演算法,都可以用Stack改寫,例如DFS。不過就算我們使用遞迴寫法,程式最終被parsing還是Stack

Stack memory vs Heap memory

可參考Stack vs. Heap

stack memory heap memory
有限的記憶體配置空間 記憶體配置空間較大
存活時間規律可預測的 存活時間不規律不可預測的
CPU自動管理空間(GC) 使用者自主管理空間
區域變數宣告的空間不能更動 物件的值可以變動,如realloc()

另外ptt有針對兩者佔用記憶體大小的討論stack v.s. heap sizes

以Python實作

Using Lists as Stacks

佇列 Queue

  • 佇列是一種抽象資料型態,特性是先進先出(FIFO, first in first out)
  • 在高階程式語言,容易用array、linked list來實作

應用

  • 多個程序的資源共享,例如CPU排程
  • 非同步任務佇列,例如I/O Buffer
  • 廣度優先搜尋演算法(Depth-First-Search)

以Python實作

參考

二元搜尋樹 Binary Search Tree

主要的優點就是時間複雜度能優化至O(logN)

  • 每個節點最多有兩個子節點
  • 子節點有左右之分
  • 左子樹的節點小於根節點、右子樹的節點大於根節點
  • 節點值不重複
Average case Worst case
insert O(logN) O(N)
delete O(logN) O(N)
search O(logN) O(N)

以Python實作insert, remove, search,執行結果請參考gist

BST現實中的應用

  • OS file system
  • 機器學習:決策樹

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

  • 能保證O(logN)的時間複雜度
  • 每次insert, delete都要檢查平衡,非平衡需要額外做rotation
  • 判斷是否平衡:
    • 左子樹高度 - 右子樹高度 > 1: rotate to right
    • 左子樹高度 - 右子樹高度 < -1: rotate to left
    • image
Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

不適合用在排序,時間複雜度為O(N*logN)

  • 插入n個:O(N*logN)
  • in-order迭代:O(N)

繼承上面BST繼續往下實作,有bug請協助指正,執行結果請參考gist

  • 任一節點設定完left或right,更新該節點height
  • 每個insert的call stack檢查檢查節點是否平衡,不平衡則rotate

紅黑樹 Red-Black Tree

  • 相較於AVL樹,紅黑樹犧牲了部分平衡性換取插入/刪除操作時更少的翻轉操作,整體效能較佳(插入、刪除快)
  • 不像AVL樹的節點屬性用height來判斷是否須翻轉,而是用紅色/黑色來判斷
    • 根節點、末端節點(NULL)是黑色
    • 紅色節點的父節點和子節點是黑色
    • 每條路徑上黑色節點的數量相同
    • 每個新節點預設是紅色,若違反以上規則:
    • 翻轉,或
    • 更新節點顏色

image

Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

github上用python實作的範例:Red-Black-Tree

優先權佇列 Priority Queue

  • 相較於Stack或Queue,對資料項目的取出順序是以權重(priority)來決定
  • 常用heap來實作

二元堆積 Binary Heap

  • 是一種二元樹資料結構,通常透過一維陣列(one dimension array)
  • 根據排序行為分成minmax
    • max heap: 父節點的值(value)或權重(key)大於子節點
    • min heap: 父節點的值(value)或權重(key)小於子節點
  • 必須是完全(compelete)二元樹或近似完全二元樹

註:

  • heap資料結構跟heap memory沒有關聯
  • 優勢在於取得最大權重或最小權重項目(root),時間複雜度為O(1)
time complexity
insert O(N) + O(logN) reconsturct times
delete O(N) + O(logN) reconsturct times

應用

  • 堆積排序法(Heap Sort)
  • 普林演算法(Prim’s Algorithm)
  • 戴克斯特拉演算法(Dijkstra’s Algorithm)

堆積排序 Heapsort

  • 是一種比較排序法(Comparision Sort)
  • 主要優勢在於能確保O(NlogN)的時間複雜度
  • 屬於原地演算法(in-place algorithm),缺點是每次排序都須重建heap——增加O(N)時間複雜度
  • 在一維陣列起始位置為0的indexing:

image

操作可參考這篇文章:Comparison Sort: Heap Sort(堆積排序法)

用Python實作Max Binary Heap,請參考gist

python build-in heapq

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

  • 鍵、值的配對(key-value)
  • 相較於樹狀資料結構,劣勢在於排序困難
  • 主要操作:
    • 新增、刪除、修改值
    • 搜尋已知的鍵

image

hash function

  • division method: modulo operator

h(x) = n % m

n: number of keys, m: number of buckets

Collision

當多個key存取同一個bucket(slot),解決collision會導致時間複雜度提高

解法:

  • chaining: 在同一個slot用linked list存放多個關聯
  • open addressing: 分配另一個空的slot
    • linear probing: 線性探測
    • quadratic probing: 二次方探測,如1, 2, 4, 8…
    • rehashing

Second Round皆有詳盡解說:

Dynamic resizing

load factor(佔用率): n / m

  • load factor會影響到存取的效能,因此須要根據使用率動態變更陣列大小;
  • 舉例來說,Java觸發resize的時機點大約是佔用超過75%時、Python則約是66%

應用

  • 資料庫
  • Network Routing
  • Rabin-Karp演算法
  • Hashing廣泛用於資料加密

參考:

  • http://www.globalsoftwaresupport.com/use-prime-numbers-hash-functions/
  • http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#collision

以Python實作,請參考gist

Average case Worst case
insert O(1) O(N)
delete O(1) O(N)
search O(1) O(N)

三元搜尋樹 Ternary Search Tree, TST

  • 相較其他樹狀資料結構而言,佔用記憶體空間較小
  • 只儲存string,不存NULL或其他物件
  • 父節點可以有3個子節點:left(less)middle(equal)right(greater)
  • 可以同時用來當作hashmap使用,也可以做排序
  • 效能上比hashmap更佳,在解析key時是漸進式的(如cat若root沒有c就不用繼續找了)

image

應用

  • autocompelete
  • 拼字檢查
  • 最近鄰居搜尋(Near-neighbor)
  • WWW package routing
  • 最長前綴匹配(perfix matching)
  • Google Search

以Python實作,請參考gist

互斥集 Disjoint sets / union-find data structure

  • 一堆沒有交集的集合,如10個學生分成4組
  • 主要操作: unionfindmakeSet
  • 通常以linked list或tree來實作
  • 訪問disjoint set中的任何節點都回傳同一個root value

set在union過程中會遇到不平衡的問題,有兩種最佳化方法:

  1. union by rank: 讓小的樹接到較大的樹
  2. path compression: 訪問節點時調整樹的結構,直接與root連結

應用

  • Kruskal: 檢查圖中是否有cycle

以Python實作,輸出請參考gist

發表留言