Section 12: Generators as Coroutines (111~118)

名詞:coroutine (連結為 WIKI 解釋)

coroutine → co + routine
→ co: 共同、協作之類意思。例如:cowork, cooperate
→ routine: 一套固定的動作。例如:routine work (重複性的)日常工作
→ routine: 常式(來源:侯捷 - 英中繁簡程式譯詞對照

台灣國家教育研究院 - 雙語詞彙 的翻譯:共常式、共常式相關

網路上常見的翻譯:協程

關於 Process、Thread、Coroutine 的區別,可以參考這篇文章:


111. IMPORTANT NOTE - READ FIRST

老師建議 Section 12 可以不用看(Python 3.8 已棄用,預計在 Python 3.10 刪除)。

然後 Section 13 是用 12 教的方法,實作專案。

有兩個解決方案:

  1. 本週五(因為今天已經週二了)照舊,但下週五直接跳到 Section 14。

  2. 本週五改成分享 Section 14。

小結:可能大家不會每天看 Discord,所以本週我們還是依照原有進度進行。

等週五會後,再做進一步討論。謝謝大家!

補充資料:

老師說,本章所提的 Generators as Coroutines,會用 asyncio 取代。

以下是老師在 YouTube 中,關於 asyncio 的講解:


112. Introduction

幾個多工實作方式的討論。

Concurrency vs Parallelism

並發(Concurrent) vs 並行(Parallel)

  • Concurrent 是好幾個任務互相在搶相同的 CPU,搶到了就是優先執行該任務,所以在一個時間點上只有一個任務在執行。

  • Parallel 則是每個 CPU 各自負責其任務,而且是同時進行的,無所謂切換的問題。

以前的電腦如果是單核的話,只能做到 Concurrent;現在的電腦大多都是多核心的所以才可以達到 Parallel。

資料來源同前

Cooperative vs Preemptive Multitasking

Cooperative Multitasking: completely controlled by developer (coroutine 屬於這種作法)

Preemptive Multitasking: not controlled by developer

  • Cooperative Multitasking 協同式多工

每一個行程 (process) 必須提供其他行程使用處理器 (processor) 的機會,使每一個程式都能被處理器執行來達到多工的作業,作業系統 (OS) 在這種方式下扮演的角色只是輔助管理與分配程式間的處理器使用時間,若是一個程式佔據處理器時間不放,則其他程式包括作業系統都沒有機會來執行,且一個當掉或設計有問題的程式可能會使得整個系統當掉。

  • Preemptive Multitasking 先佔式多工

每個程式的執行時間係由「作業系統」來分配,一個程式的時間使用完之後,系統就會將CPU分配給下一個程式(這種動作稱為context switching),沒有一個程式能獨佔CPU。(補充:以上是網路補充資料。Fred 老師說明:由 OS 或 task scheduler 控制)

參考資料一(提醒:有部分寫反了):

參考資料二:

兩種實作 Coroutines 的方式:

  1. generators

    • uses extended form of yield(yield from) → 本節(Section 12)的主題

    • recent addition: asyncio → 本節不涵蓋此內容(但上面提的 YouTube 有介紹)

  2. native coroutines → 本節不涵蓋此內容


113. Coroutines - Lecture

什麼是 Coroutine?

cooperative routines(functions) → subroutines

以求取平均值的範例說明:cooperative routines(subroutines) vs. coroutine

最大的不同:coroutine 計算平均值的函式,會一直存在(active),並等待新值傳入。相反的,subroutines 則在計算完成後就不再存在。

什麼是 queues and stacks ?

  • A queue is a data structure that supports first-in first-out (FIFO) ddition/removal of items add elements

  • A stack is a data structure that supports last-in first-out (LIFO) addition/removal of items

以 list 為例,看 queues and stacks 的實作。

data structure function result
queue list.insert(0, item) inserts item to front of list
list.pop() removes and returns last element of list
stack list.append(item) appends item to end of list
list.pop() removes and returns last element of list

問題:insert 很沒有效率

But the problem is that inserting elements into a list is actually quite inefficient. Appending to a list, putting out as the last item is very efficient.
Removing the last item from the list is also very efficient.
But adding and removing items from inside a list at the beginning of the list or in the middle of it is not very efficient.

解決:deque(有點像是雙向的 list)

from collections import deque

dq = deque()
dq = deque(iterable)
dq = deque(maxlen=n)

dq.append(item)
dq.appendleft(item)

dq.pop()
dq.popleft()

dq.clear()

len(dq)

timing measurement

functions list deque 差距
append (right) 0.87 0.87 -
pop (right) 0.002 0.0005 x4
insert (left) 20.80 0.84 x25
pop (left) 0.012 0.0005 x24

課外補充:Abstract Data Types(ADT:抽象資料型態、抽象資料型別)

抽象資料型態 (ADT) 是物件 (objects) 的型態 (type) 或類別 (class),其行為由一組值 (values) 和一組操作 (operations) 定義。

ADT 的定義只提到要執行哪些操作,而沒有提到這些操作將如何實作,也沒有指定如何在記憶體中存取資料和使用什麼演算法。

它被稱為「抽象」,正是因為它僅提供基本要素(值和操作)並隱藏細節的過程。

內文介紹了三個 ADT:List, Stack & Queue,詳情請參考原文。

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view.

The process of providing only the essentials and hiding the details is known as abstraction.

資料來源:

List ADT Functions
get() Return an element from the list at any given position.
insert() Insert an element at any position of the list.
remove() Remove the first occurrence of any element from a non-empty list.
removeAt() Remove the element at a specified location from a non-empty list.
replace() Replace an element at any position by another element.
size() Return the number of elements in the list.
isEmpty() Return true if the list is empty, otherwise return false.
isFull() Return true if the list is full, otherwise return false.
Stack ADT Functions
push() Insert an element at one end of the stack called top.
pop() Remove and return the element at the top of the stack, if it is not empty.
peek() Return the element at the top of the stack without removing it, if the stack is not empty.
size() Return the number of elements in the stack.
isEmpty() Return true if the stack is empty, otherwise return false.
isFull() Return true if the stack is full, otherwise return false.
Stack Queue Functions
enqueue() Insert an element at the end of the queue.
dequeue() Remove and return the first element of the queue, if the queue is not empty.
peek() Return the element of the queue without removing it, if the queue is not empty.
size() Return the number of elements in the queue.
isEmpty() Return true if the queue is empty, otherwise return false.
isFull() Return true if the queue is full, otherwise return false.

114. Coroutines - Coding


115. Generator States - Lecture

  • CREATED

  • RUNNING

  • SUSPENDED

  • CLOSED

from inspect import getgeneratorstate

g = gen('abc')
getgeneratorstate(g)
# 'GEN_CREATED'

next(g)
# 'a'
getgeneratorstate(g)
# 'GEN_SUSPENDED'

list(g)
#['b', 'c']

getgeneratorstate(g)
# 'GEN_CLOSED'
def gen(s):
    for c in s:
        print(getgeneratorstate(global_gen))
        yield c

global_gen = gen('abc')
next(global_gen)
# GEN_RUNNING
# 'a'

getgeneratorstate(global_gen)
# 'GEN_SUSPENDED'