集合論

撰寫高效的 Python 程式碼

Logan Thomas

Scientific Software Technical Trainer, Enthought

集合論

應用於物件集合的數學分支
- 也就是 sets
Python 內建 set 資料型別與方法：
- intersection()：兩個集合的共同元素
- difference()：在其中一個集合但不在另一個集合的元素
- symmetric_difference()：只出現在其中一個集合的元素
- union()：兩個集合任一方包含的所有元素
會員測試很快
- 檢查值是否存在於序列中
- 使用 in 運算子

用迴圈比較物件

list_a = ['Bulbasaur', 'Charmander', 'Squirtle']
list_b = ['Caterpie', 'Pidgey', 'Squirtle']

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 List A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在另一個標示為 List B 的方框中」

用迴圈比較物件

list_a = ['Bulbasaur', 'Charmander', 'Squirtle']
list_b = ['Caterpie', 'Pidgey', 'Squirtle']

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 List A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在標示為 List B 的方框中；兩個方框中的 Squirtle 皆被圈起」

list_a = ['Bulbasaur', 'Charmander', 'Squirtle']
list_b = ['Caterpie', 'Pidgey', 'Squirtle']

in_common = []

for pokemon_a in list_a:
    for pokemon_b in list_b:
        if pokemon_a == pokemon_b:
            in_common.append(pokemon_a)

print(in_common)

['Squirtle']

list_a = ['Bulbasaur', 'Charmander', 'Squirtle']
list_b = ['Caterpie', 'Pidgey', 'Squirtle']

set_a = set(list_a)
print(set_a)

{'Bulbasaur', 'Charmander', 'Squirtle'}

set_b = set(list_b)
print(set_b)

{'Caterpie', 'Pidgey', 'Squirtle'}

set_a.intersection(set_b)

{'Squirtle'}

集合論帶來的效率提升

%%timeit
in_common = []

for pokemon_a in list_a:
    for pokemon_b in list_b:
        if pokemon_a == pokemon_b:
            in_common.append(pokemon_a)

601 ns ± 17.1 ns 每次迴圈（7 次執行的平均值 ± 標準差，每次 1000000 迴圈）

%timeit in_common = set_a.intersection(set_b)

137 ns ± 3.01 ns 每次迴圈（7 次執行的平均值 ± 標準差，每次 10000000 迴圈）

集合方法：difference

set_a = {'Bulbasaur', 'Charmander', 'Squirtle'}
set_b = {'Caterpie', 'Pidgey', 'Squirtle'}

set_a.difference(set_b)

{'Bulbasaur', 'Charmander'}

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 Set A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在標示為 Set B 的方框中；Set A 方框中的 Bulbasaur 與 Charmander 被圈起」

集合方法：difference

set_a = {'Bulbasaur', 'Charmander', 'Squirtle'}
set_b = {'Caterpie', 'Pidgey', 'Squirtle'}

set_b.difference(set_a)

{'Caterpie', 'Pidgey'}

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 Set A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在標示為 Set B 的方框中；Set B 方框中的 Caterpie 與 Pidgey 被圈起」

集合方法：symmetric difference

set_a = {'Bulbasaur', 'Charmander', 'Squirtle'}
set_b = {'Caterpie', 'Pidgey', 'Squirtle'}

set_a.symmetric_difference(set_b)

{'Bulbasaur', 'Caterpie', 'Charmander', 'Pidgey'}

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 Set A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在標示為 Set B 的方框中；Bulbasaur、Charmander、Caterpie、Pidgey 被圈起」

集合方法：union

set_a = {'Bulbasaur', 'Charmander', 'Squirtle'}
set_b = {'Caterpie', 'Pidgey', 'Squirtle'}

set_a.union(set_b)

{'Bulbasaur', 'Caterpie', 'Charmander', 'Pidgey', 'Squirtle'}

「將寶可夢 Bulbasaur、Charmander、Squirtle 圍在標示為 Set A 的方框中；將寶可夢 Caterpie、Pidgey、Squirtle 圍在標示為 Set B 的方框中；所有寶可夢皆被圈起，且 Squirtle 只圈一次」

使用集合進行會員測試

# 三種資料結構中各有相同的 720 個寶可夢
names_list  = ['Abomasnow', 'Abra', 'Absol', ...]
names_tuple = ('Abomasnow', 'Abra', 'Absol', ...)
names_set   = {'Abomasnow', 'Abra', 'Absol', ...}

「將寶可夢 Abomasnow、Abra、Absol 分別圍在三個方框中，方框標示為 List、Tuple、Set」

使用集合進行會員測試

# 三種資料結構中各有相同的 720 個寶可夢
names_list  = ['Abomasnow', 'Abra', 'Absol', ...]
names_tuple = ('Abomasnow', 'Abra', 'Absol', ...)
names_set   = {'Abomasnow', 'Abra', 'Absol', ...}

「將寶可夢 Abomasnow、Abra、Absol 分別圍在三個方框中，方框標示為 List、Tuple、Set；寶可夢 Zubat 以連線指向各方框，表示對每個方框進行會員測試」

names_list  = ['Abomasnow', 'Abra', 'Absol', ...]
names_tuple = ('Abomasnow', 'Abra', 'Absol', ...)
names_set   = {'Abomasnow', 'Abra', 'Absol', ...}

%timeit 'Zubat' in names_list

7.63 µs ± 211 ns 每次迴圈（7 次執行的平均值 ± 標準差，每次 100000 次迴圈）

%timeit 'Zubat' in names_tuple

7.6 µs ± 394 ns 每次迴圈（7 次執行的平均值 ± 標準差，每次 100000 次迴圈）

%timeit 'Zubat' in names_set

37.5 ns ± 1.37 ns 每次迴圈（7 次執行的平均值 ± 標準差，每次 10000000 次迴圈）

用集合找唯一值

# 與每隻寶可夢對應的 720 個主要屬性
primary_types = ['Grass', 'Psychic', 'Dark', 'Bug', ...]

unique_types = []

for prim_type in primary_types:
    if prim_type not in unique_types:
        unique_types.append(prim_type)

print(unique_types)

['Grass', 'Psychic', 'Dark', 'Bug', 'Steel', 'Rock', 'Normal',
 'Water', 'Dragon', 'Electric', 'Poison', 'Fire', 'Fairy', 'Ice',
 'Ground', 'Ghost', 'Fighting', 'Flying']

用集合找唯一值

# 與每隻寶可夢對應的 720 個主要屬性
primary_types = ['Grass', 'Psychic', 'Dark', 'Bug', ...]

unique_types_set = set(primary_types)

print(unique_types_set)

{'Grass', 'Psychic', 'Dark', 'Bug', 'Steel', 'Rock', 'Normal',
 'Water', 'Dragon', 'Electric', 'Poison', 'Fire', 'Fairy', 'Ice',
 'Ground', 'Ghost', 'Fighting', 'Flying'}

一起來練習吧！

撰寫高效的 Python 程式碼