Union-Find 併查集

更新紀錄：

2022.03.01 更新網路資料 2 的連結

網路資料：

1. Link 中文維基百科
2. Link Robert Sedgewick 教授的 Algorithm 4th 配套投影片

觀念紀錄：

Union-Find 是一種 data structure 也可以是一種類型的問題。

問題的主要描述是：

• Find(x, y): 回傳 x, y 是否屬於同一個 set
• Union(x, y): 合併 x, y 所屬的 set

之所以會說是一種 data structure 是因為，實務上高效率解決這類問題的作法是一種特定的資料結構。

Python 程式碼:

class UnionFind:
    def __init__(self, n):
        self.id = [i for i in range(n)]
        self.sz = [1 for _ in range(n)]
        
    def root(self, i):
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i];
        return i
    
    def find(self, p, q):
        return self.root(p) == self.root(q)
    
    def unite(self, p, q):
        i = self.root(p)
        j = self.root(q)
        if self.sz[i] <= self.sz[j]:
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]

python defaultdict 的用法

主要目標：

紀錄 defaultdict 的概念跟常見用法。

說明：

帶有預設值的 dictionary ，第一個參數是一個可呼叫的物件，後面接的參數會直接給 dict 當參數使用。

例如：

defaultdict(int, {'a': 10, 'b': 20})

等同於會呼叫的意思：

dict({'a': 10, 'b': 20})

整理最常用的方法： 

1. 要計算所有的東西有多少個： 

d = defaultdict(int) 

d[x] += 1 

2. 要把同一個 key 的東西串在一起： 

d = defaultdict(list) 

d[x].append(y) 

3. 要使用指定的預設值： 

d = defaultdict(lambda :False)

參考資料：

https://docs.python.org/3/library/collections.html#collections.defaultdict

Python 如何產生指定 bit 數量的 mask

程式碼:

def n_mask(n):
    return 2**n-1

使用:

bin(n_mask(45))

輸出:

'0b111111111111111111111111111111111111111111111'

交換 DataFrame 的 column 順序

把最後一欄換到最前面：

# 先拿到 column list
cols = df.columns.to_list()
# 交換 column 順序
cols = cols[-1:] + cols[:-1]
# 套用新的 column 順序
df = df[cols]

要換到其他的位置也可以參考這樣的方式，
核心觀念是先拿到全部的 column 後再調整位置，然後在套用新順序。

7z 常用壓縮/解壓縮指令

壓縮檔案

7z a [輸出名稱] [要壓縮的檔案列表]
輸出名稱如果有指定副檔名 .zip 會用 zip 格式壓縮
如果沒有指定副檔名會自動加上 .7z ，會用 7z 方式壓縮

7z a output text1.text text2.txt

解壓縮檔案

7z x [壓縮檔名稱]
會直接在原地解壓縮檔案。

7z x data.zip

解壓縮檔案 - 指定輸出目錄

7z x [壓縮檔名稱] -o[output_folder]
注意 -o 跟 output_folder 之間不要有空格
解壓縮的資料放到指定的位置

7z x data.zip -ooutput_data

解壓縮檔案 - 指定要解壓縮的檔案(可用 * 選擇)

7z x [壓縮檔名稱] [*.csv] -r
指定想要解壓縮出來的檔案名稱。名稱可以用 wildcard 指定同類型的檔案。
沒有加 -r 的話只會解出第一層檔案，加上 -r 可以解出壓縮檔中每一層的檔案。

7z x data.zip *.csv -r -odata_folder