Try   HackMD

12/20 第十四堂社課

今日講師：R緯

(Python班)

今日課程流程：

  • 介紹-標準函式庫 (Standard Library)
    • 資料結構
    • 與演算法相關
  • 歡樂題目time (如果有)

標準函式庫 (Standard Library)

python官方

資料結構 (複習)

內建資料結構 (第12堂社課講義)

1. 列表∨串列 (List)








my_list = [1, 2, 3, 4, 5]
# list是可變的，可以隨時添加或刪除元素
my_list.append(6)  # 添加元素到list末尾
my_list.remove(2)  # 刪除元素 2
print(my_list)  # 輸出: [1, 3, 4, 5, 6]
# list支持切片操作
print(my_list[1:3])  # 輸出: [3, 4]

特性：

  • 有序：元素的順序是固定的。
  • 可變：可以隨時修改、添加或刪除元素。
  • 支持重複元素。

2. 元組 (Tuple)







my_tuple = (1, 2, 3, 4, 5)
# 元組是不可變的，無法修改其內容
# my_tuple[0] = 10  # 這會引發錯誤
print(my_tuple)  # 輸出: (1, 2, 3, 4, 5)
# 可以進行切片操作
print(my_tuple[1:3])  # 輸出: (2, 3)

特性：

  • 有序：元素的順序是固定的。
  • 不可變：一旦創建，無法修改。
  • 支持重複元素。

3. 集合 (Set)









my_set = {1, 2, 3, 4, 5}
# 集合不允許重複元素
my_set.add(3)  # 不會添加重複的 3
my_set.add(6)  # 添加新元素 6
print(my_set)  # 輸出: {1, 2, 3, 4, 5, 6}
# 可以進行集合運算
another_set = {4, 5, 6, 7}
print(my_set.intersection(another_set))  # 輸出: {4, 5, 6}

特性：

  • 無序：元素的順序不固定。
  • 可變：可以添加或刪除元素。
  • 不支持重複元素。

4. 字典 (Dictionary)







my_dict = {'name': 'Alice', 'age': 25}
# 字典以鍵值對存儲資料，可以快速查找
print(my_dict['name'])  # 輸出: Alice
my_dict['age'] = 26  # 更新值
my_dict['city'] = 'New York'  # 添加新鍵值對
print(my_dict)  # 輸出: {'name': 'Alice', 'age': 26, 'city': 'New York'}

特性：

  • 可變：可以添加、刪除或更新鍵值對。
  • 鍵(key)必須是唯一的。

5. 字串 (String)

print("我相信大家都會")

特性：

  • 有序：字符的順序固定。
  • 不可變：一旦創建，無法修改。
  • 支持切片和拼接操作。

其他資料結構

6. 數組 (Array)：

  • 通常用 array 模組或 NumPy 庫來處理數值計算。
  • 定義方式（用 array 模組）





from array import array
my_array = array('i', [1, 2, 3, 4, 5])  # 'i' 表示整數型別
# 數組的元素類型是固定的
my_array.append(6)  # 添加元素
print(my_array)  # 輸出: array('i', [1, 2, 3, 4, 5, 6])

特性：

  • 有序：元素的順序是固定的。
  • 可變：可以添加或刪除元素。
  • 所有元素必須是相同類型。

7. 堆疊 (Stack)：

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • 可以用list來實現，後進先出 (LIFO) 原則。







stack = []
# 堆疊遵循後進先出 (LIFO) 原則
stack.append(1)  # 添加元素
stack.append(2)
stack.append(3)
print(stack.pop())  # 輸出: 3 (最後添加的元素)
print(stack)  # 輸出: [1, 2]

特性：

  • 僅能在一端進行插入和刪除操作。
  • 用於回溯演算法、函數調用等場景。

8. 佇列∨隊列 (Queue)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • 可以用 collections.deque 來實現，先進先出 (FIFO) 原則。








from collections import deque
queue = deque()
# 佇列遵循先進先出 (FIFO) 原則
queue.append(1)  # 添加元素
queue.append(2)
queue.append(3)
print(queue.popleft())  # 輸出: 1 (最早添加的元素)
print(queue)  # 輸出: deque([2, 3])

特性：

  • 在一端插入元素，在另一端刪除元素。
  • 用於排隊系統、廣度優先搜尋等場景。

9. 優先佇列 (Priority Queue)

  • 可以用 heapq 模組來實現。
  • 例如：import heapq; heap = []; heapq.heappush(heap, (priority, item))







import heapq
heap = []
# 優先佇列根據優先級進行排序
heapq.heappush(heap, (1, 'task1'))  # 優先級 1
heapq.heappush(heap, (3, 'task3'))  # 優先級 3
heapq.heappush(heap, (2, 'task2'))  # 優先級 2
print(heapq.heappop(heap))  # 輸出: (1, 'task1') (優先級最高的任務)

特性：

  • 元素根據優先級進行排序，優先級高的元素會先被處理。
  • 常用於任務調度、事件驅動系統等場景。

演算法 (Algorithm)

1. 容器資料型態 (collections)

Counter

Counter 是 Python 的 collections 模組中的一個類，計算hashable對象的頻率。是一種字典子類，計算元素的出現次數。Counter 對象的key是hashable的元素，值是這些元素出現次數。

  1. 導入:

    ​​​from collections import Counter

  2. 創建 Counter 對象:

    • 可迭代對象：

      

      ​​​​​c = Counter(['a', 'b', 'c', 'a', 'b', 'a'])
​​​​​print(c)  # Output: Counter({'a': 3, 'b': 2, 'c': 1})

    • 字典：

      

      ​​​​​c = Counter({'a': 3, 'b': 2, 'c': 1})
​​​​​print(c)  # Output: Counter({'a': 3, 'b': 2, 'c': 1})

    • 關鍵字參數：

      

      ​​​​​c = Counter(a=3, b=2, c=1)
​​​​​print(c)  # Output: Counter({'a': 3, 'b': 2, 'c': 1})

  3. 訪問元素的計數:

    


    ​​​print(c['a'])  # Output: 3
​​​print(c['b'])  # Output: 2
​​​print(c['d'])  # Output: 0 (如果元素不存在，返回 0)

  4. 更新計數:
    用 .update() 更新計數：

    

    ​​​c.update(['a', 'd', 'd'])
​​​print(c)  # Output: Counter({'a': 4, 'b': 2, 'd': 2, 'c': 1})

  5. 最常見的元素:
    用 .most_common() 獲取最常見的元素及其計數：

    ​​​print(c.most_common(2))  # Output: [('a', 4), ('b', 2)]

    ※如果多個元素計數相同，則順序是根據它們在原始數據中出現順序來決定。

  6. 減少計數:
    用 .subtract() 減少計數：

    

    ​​​c.subtract(['a', 'b'])
​​​print(c)  # Output: Counter({'a': 3, 'b': 1, 'd': 2, 'c': 1})

  7. 數學運算:
    例如加法、減法、交集和聯集：

    






    ​​​c1 = Counter(a=3, b=2)
​​​c2 = Counter(a=1, b=2, c=1)

​​​print(c1 + c2)  # Output: Counter({'a': 4, 'b': 4, 'c': 1})
​​​print(c1 - c2)  # Output: Counter({'a': 2, 'b': 0})
​​​print(c1 & c2)  # Output: Counter({'a': 1, 'b': 2})  # 取最小值
​​​print(c1 | c2)  # Output: Counter({'a': 3, 'b': 2, 'c': 1})  # 取最大值

defaultdict

defaultdict 也是 Python 的 collections 模組中的一個類。主要特點是能夠自動為不存在的key提供默認值，訪問這些key時就不會 KeyError。

  1. 導入:

    ​​​from collections import defaultdict

  2. 創建 defaultdict 對象:
    創建 defaultdict 需要提供一個工廠函數，用來生成默認值。常見的工廠函數包括 int、list、set 等。

    • 用 int （默認值為 0）：

      

      ​​​​​dd = defaultdict(int)
​​​​​print(dd['a'])  # Output: 0

    • 用 list （默認值為空list）：

      




      ​​​​​dd = defaultdict(list)
​​​​​dd['a'].append(1)
​​​​​dd['a'].append(1)
​​​​​dd['a'].append(2)
​​​​​print(dd)  # Output: defaultdict(<class 'list'>, {'a': [1, 1, 2]})

    • 用 set （默認值為空集合）：

      




      ​​​​​dd = defaultdict(set)
​​​​​dd['a'].add(1)
​​​​​dd['a'].add(1)
​​​​​dd['a'].add(2)
​​​​​print(dd)  # Output: defaultdict(<class 'set'>, {'a': {1, 2}})

  3. 訪問元素:
    訪問一個不存在的key時，defaultdict 會自動創建一個默認值，不會引發 KeyError：

    

    ​​​dd = defaultdict(int)
​​​print(dd['b'])  # Output: 0 (自動創建)

  4. 更新元素:
    可以像普通字典一樣更新 defaultdict 的元素：

    

    ​​​dd['a'] += 1
​​​print(dd)  # Output: defaultdict(<class 'int'>, {'a': 1})

  5. 遍歷 defaultdict:
    可以用 for 循環遍歷 defaultdict ：

    


    ​​​dd = defaultdict(int, {'a': 1, 'b': 2})
​​​for key, value in dd.items():
​​​    print(key, value)

應用

defaultdict 非常有用，特別是在計數、分組的情況下。
例如：計算字母出現的頻率：









from collections import defaultdict
string = "hello world"
dd = defaultdict(int)

for char in string:
    dd[char] += 1

print(dd)

deque

deque 也

2是 Python 的 collections 模組中的一個類，代表雙端 佇列∨隊列 （double-ended queue）。與 列表∨串列（list）相比，deque 在兩端的插入和刪除操作的效率更高。

  1. 導入:

    ​​​from collections import deque

  2. 創建 deque 對象:
    傳遞一個可迭代對象創建 deque：

    

    ​​​d = deque([1, 2, 3])
​​​print(d)  # Output: deque([1, 2, 3])

  3. 添加元素:

    • 在右端添加元素： 
      

      ​​​​​​​d.append(4)
​​​​​​​print(d)  # Output: deque([1, 2, 3, 4])
    • 在左端添加元素： 
      

      ​​​​​​​d.appendleft(0)
​​​​​​​print(d)  # Output: deque([0, 1, 2, 3, 4])

  4. 刪除元素:

    • 從右端刪除元素： 
      

      ​​​​​​​d.pop()
​​​​​​​print(d)  # Output: deque([0, 1, 2, 3])
    • 從左端刪除元素： 
      

      ​​​​​​​d.popleft()
​​​​​​​print(d)  # Output: deque([1, 2, 3])

  5. 訪問元素:
    一樣可以通過索引訪問 deque 中的元素：

    ​​​print(d[0])  # Output: 1

  6. 旋轉 deque:
    deque 提供了 .rotate()，將元素旋轉指定的步數：

    



    ​​​d.rotate(1)  # 向右旋轉
​​​print(d)  # Output: deque([3, 1, 2])
​​​d.rotate(-1)  # 向左旋轉
​​​print(d)  # Output: deque([1, 2, 3])

    語法:

    ​​​​deque.rotate(n)

    • 其中 n 是一個整數，表示旋轉的步數：

      • 如果 n 是正數，表示向右旋轉。
      • 如果 n 是負數，表示向左旋轉。

    • 左、右旋轉

      • 向右旋轉時，deque 最後一個元素會移到第一個位置，其他向後移動。
      • 向左旋轉時，deque 的第一個元素會移到最後一個位置，其他向前移動。

  7. 限制大小:
    deque 可設置最大大小，超過這個大小時，最舊元素會被自動刪除：

    






    ​​​d = deque(maxlen=3)
​​​d.append(1)
​​​d.append(2)
​​​d.append(3)
​​​print(d)  # Output: deque([1, 2, 3])
​​​d.append(4)  # 超過最大大小，最舊的元素 1 被刪除
​​​print(d)  # Output: deque([2, 3, 4])

namedtuple

namedtuple 是 Python 的 collections 模組中的一個工廠函數，創建有命名字段的元組子類。使得代碼更具可讀性和可維護性。

  1. 導入 namedtuple:

    ​​​from collections import namedtuple

  2. 創建 namedtuple:
    用 namedtuple 函數定義一個新的元組。需要提供類型名稱和字段的名稱（以空格分隔的字符串或list）。

    ​​​Point = namedtuple('Point', 'x y')

  3. 創建實例:
    用定義的 namedtuple 類型來創建實例。

    

    ​​​p = Point(10, 20)
​​​print(p)  # Output: Point(x=10, y=20)

  4. 訪問字段:
    通過字段名稱來訪問 namedtuple 的字段，比用索引更可讀。

    

    ​​​print(p.x)  # Output: 10
​​​print(p.y)  # Output: 20

  5. 支持索引和unpacking:

    




    ​​​print(p[0])  # Output: 10
​​​print(p[1])  # Output: 20

​​​x, y = p  # unpack
​​​print(x, y)  # Output: 10 20

  6. 不可變性:
    namedtuple 和元組一樣是不可變的。

    ​​​# p.x = 30  # 這會引發 AttributeError

2. 堆積佇列演算法 (heap queue algorithm, 簡稱heapq)

heapq 是 Python 的一個內建模組，提供操作堆（heap）數據結構的函數。

  1. heap 基本觀念

    • 堆 是一種特殊樹形數據結構，常用於優先隊列。
    • 最小堆 的特性是每個父節點的值
      ≤       其子節點的值。

    1. 用list表示堆

    • 堆可以用list來表示，並可用 heapq 模組操作。
    • 用 heapq.heapify() 將list轉換為堆，list會被重新排列以滿足最小堆的特性。

    2. 索引計算

    對於節點，索引為 i，找到其父節點和子節點的索引：

    • 父節點的索引：(i - 1) // 2
    • 左子節點的索引：2 * i + 1
    • 右子節點的索引：2 * i + 2

    3. 子節點有效性

    • 當子節點索引
      =      list的最大索引（list的長度
      −1      ）時，之後的索引不會有子節點。

    4. example

    以堆 heap = [1, 1, 2, 3, 5, 9, 4] 為例，索引

    0∼6：

    • 索引 0（值 1）：有左子節點（索引 1）和右子節點（索引 2）。
    • 索引 1（值 1）：有左子節點（索引 3）和右子節點（索引 4）。
    • 索引 2（值 2）：有左子節點（索引 5）和右子節點（索引 6）。
    • 索引 3（值 3）：左子節點（索引 7）和右子節點（索引 8）超出範圍，沒有子節點。
    • 索引 4（值 5）：左子節點（索引 9）和右子節點（索引 10）超出範圍，沒有子節點。
    • 索引 5（值 9）：左子節點（索引 11）和右子節點（索引 12）超出範圍，沒有子節點。
    • 索引 6（值 4）：左子節點（索引 13）和右子節點（索引 14）超出範圍，沒有子節點。

    ※索引2就有子節點是索引6，在他之後的索引都不會有子節點，但機算機依然會確認其之後的索引是否符合最小堆（索引
    3∼6    ）

  2. 導入:

    ​​​import heapq

  3. 創建堆:

    


    ​​​nums = [3, 1, 4, 1, 5, 9, 2]
​​​heapq.heapify(nums)  # 將list轉換為堆
​​​print(nums)  # Output: [1, 1, 2, 3, 5, 9, 4]（最小堆）

  4. 插入元素:
    用 heappush 函數可以將新元素插入堆中，並保持堆的性質。

    

    ​​​heapq.heappush(nums, 0)
​​​print(nums)  # Output: [0, 1, 2, 3, 5, 9, 4, 1]

  5. 刪除最小元素:
    用 heappop 可以刪除並返回堆中的最小元素。

    


    ​​​min_elem = heapq.heappop(nums)
​​​print(min_elem)  # Output: 0
​​​print(nums)      # Output: [1, 1, 2, 3, 5, 9, 4]

  6. 查詢最小元素:
    用 nums[0] 可以訪問堆中最小元素，不會刪除它。

    ​​​print(nums[0])  # Output: 1

  7. 合併多個堆:
    用 heapq.merge 可以合併多個已排序∧可迭代對象，返回一個合併的迭代器。

    



    ​​​sorted1 = [1, 3, 5]
​​​sorted2 = [2, 4, 6]
​​​merged = list(heapq.merge(sorted1, sorted2))
​​​print(merged)  # Output: [1, 2, 3, 4, 5, 6]

  8. 獲取前 N 個最小元素:
    用 heapq.nsmallest 獲取堆中前 N 個最小元素。

    

    ​​​smallest = heapq.nsmallest(3, nums)
​​​print(smallest)  # Output: [1, 1, 2]

  9. 獲取前 N 個最大元素:
    用 heapq.nlargest 獲取堆中前 N 個最大元素。

    

    ​​​largest = heapq.nlargest(3, nums)
​​​print(largest)  # Output: [9, 5, 4]

3. 數組 (array) 與 NumPy:

Python 標準庫中有一個 array 模組，但更常用的是 NumPy 庫，它提供更強大的數組功能。

Python 標準庫中的 array 模組

主要用於存儲同類型的數據。數組的優勢在於它們比list更節省內存。

基本用法





















import array

# 創建一個整數數組
arr = array.array('i', [1, 2, 3, 4, 5])
print(arr)  # Output: array('i', [1, 2, 3, 4, 5])

# 訪問元素
print(arr[0])  # Output: 1

# 修改元素
arr[0] = 10
print(arr)  # Output: array('i', [10, 2, 3, 4, 5])

# 添加元素
arr.append(6)
print(arr)  # Output: array('i', [10, 2, 3, 4, 5, 6])

# 刪除元素
arr.remove(3)
print(arr)  # Output: array('i', [10, 2, 4, 5, 6])
  1. 數組類型碼
    創建數組時，要指定數據類型，通過類型碼來實現。常見的類型碼包括：
    • 'i': 整數 (integer)
    • 'f': 浮點數 (float)
    • 'd': 雙精度浮點數 (double)
    • 'u': Unicode 字符串 (unicode)

NumPy 數組 (補充)

NumPy 是強大的數值計算庫，提供多維數組 ndarray，及許多數學函數操作數組。NumPy 數組比 Python 的內建list和 array 模組更高效，特別是大型數據集。

  1. 安裝 NumPy

    如果尚未安裝 NumPy
    進行安裝：

    ​​​​pip install numpy

基本用法


































import numpy as np

# 創建一維數組
arr1 = np.array([1, 2, 3, 4, 5])
print(arr1)  # Output: [1 2 3 4 5]

# 創建二維數組
arr2 = np.array([[1, 2, 3], [4, 5, 6]])
print(arr2)
# Output:
# [[1 2 3]
#  [4 5 6]]

# 數組的形狀
print(arr2.shape)  # Output: (2, 3) 表示 2 行 3 列

# 訪問元素
print(arr2[0, 1])  # Output: 2

# 修改元素
arr2[0, 1] = 10
print(arr2)
# Output:
# [[ 1 10  3]
#  [ 4  5  6]]

# 添加元素
arr1 = np.append(arr1, 6)
print(arr1)  # Output: [1 2 3 4 5 6]

# 刪除元素
arr1 = np.delete(arr1, 2)  # 刪除索引 2 的元素
print(arr1)  # Output: [1 2 4 5 6]

NumPy 的功能

NumPy 提供了許多強大的功能，包括：

  1. 數學運算：支持向量化運算，能對整個數組進行操作∧不需要用循環。

    


    ​​​​​​arr = np.array([1, 2, 3])
​​​​​​print(arr + 1)  # Output: [2 3 4]
​​​​​​print(arr * 2)  # Output: [2 4 6]

  2. 統計函數：計算均值、標準差、方差等統計量函數。

    




    ​​​​​​arr = np.array([1, 2, 3, 4, 5])
​​​​​​print(np.mean(arr))  # 計算均值，Output: 3.0
​​​​​​print(np.median(arr))  # 計算中位數，Output: 3.0
​​​​​​print(np.std(arr))   # 計算標準差，Output: 1.4142135623730951
​​​​​​print(np.var(arr))   # 計算方差，Output: 2.0

  3. 數組操作：重塑、轉置、合併和分割等。

    

























    ​​​​​​# 重塑數組
​​​​​​arr = np.array([[1, 2, 3], [4, 5, 6]])
​​​​​​reshaped_arr = arr.reshape(3, 2)  # 變為 3 行 2 列
​​​​​​print(reshaped_arr)
​​​​​​# Output:
​​​​​​# [[1 2]
​​​​​​#  [3 4]
​​​​​​#  [5 6]]

​​​​​​# 轉置數組
​​​​​​transposed_arr = arr.T
​​​​​​print(transposed_arr)
​​​​​​# Output:
​​​​​​# [[1 4]
​​​​​​#  [2 5]
​​​​​​#  [3 6]]

​​​​​​# 合併數組
​​​​​​arr1 = np.array([1, 2, 3])
​​​​​​arr2 = np.array([4, 5, 6])
​​​​​​combined_arr = np.concatenate((arr1, arr2))
​​​​​​print(combined_arr)  # Output: [1 2 3 4 5 6]

​​​​​​# 分割數組
​​​​​​split_arr = np.split(combined_arr, 2)  # 將數組分為 2 部分
​​​​​​print(split_arr)  # Output: [array([1, 2, 3]), array([4, 5, 6])]

  4. bool索引：可以用bool條件來篩選數組中的元素。

    


    ​​​​​​arr = np.array([1, 2, 3, 4, 5])
​​​​​​filtered_arr = arr[arr > 2]  # 篩選大於 2 的元素
​​​​​​print(filtered_arr)  # Output: [3 4 5]

  5. 廣播：NumPy 支持廣播機制，允許不同形狀的數組進行運算。

    






    ​​​​​​arr1 = np.array([[1, 2, 3], [4, 5, 6]])
​​​​​​arr2 = np.array([10, 20, 30])  # 一維數組
​​​​​​result = arr1 + arr2  # 自動擴展 arr2 的形狀
​​​​​​print(result)
​​​​​​# Output:
​​​​​​# [[11 22 33]
​​​​​​#  [14 25 36]]

4. 陣列二分演算法 (Array bisection algorithm, 簡稱bisect)

※此為下週社課內容

5. 排序演算法

有很多種，例如：

  • 冒泡排序 (Bubble Sort)
  • 選擇排序 (Selection Sort)
  • 插入排序 (Insertion Sort)
  • 快速排序 (Quick Sort)
  • 合併排序 (Merge Sort)
  • …

※此為下下週社課內容

Last changed by 
 
ts-boring
0
72
Published on HackMD