Python

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 有可能只是儲存多個相同物件的參考

Python WSGI 及其應用

2018 年 12 月 24 日2019 年 8 月 23 日
Dev, Python

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

2018 年 12 月 7 日2022 年 11 月 30 日
Python

圖論 Graph Theory

G(V, E)

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

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

相鄰矩陣 adjacency matrixes

圖片來源

陣列 edge list representation

class Node:

def __init__(self, name):

self.name = name

self.visited = False

self.neighbors = [] # Nodes

self.predecessor = None # use in shortest path

def __repr__(self):

return 'Node(name={})'.format(self.name)

應用

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

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

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

應用

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

以Python實作，輸出請參考gist

class BFS:

"""

For BFS, use queue; For DFS, use stack or recursion

"""

def __init__(self, start):

self.queue = []

self.start = start

def traversal(self):

self.start.visited = True

self.queue.append(self.start)

while self.queue: # O(V)

node = self.queue.pop(0)

yield node

for n in node.neighbors: # O(E)

if not n.visited:

n.visited = True

self.queue.append(n)

深度優先搜尋 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

class DFS:

"""

For BFS, use queue; For DFS, use stack / recursion(os stack)

"""

def __init__(self, start):

self.start = start

def traversal(self):

interface = self.stack()

interface(self.start)

return self.result

def stack(self):

self.result = []

def interface(node):

self.result.append(node)

node.visited = True

for n in node.neighbors:

if not n.visited:

interface(n)

return interface

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

2018 年 11 月 27 日2021 年 5 月 21 日
2 Comments
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（但這樣寫有大麻煩，請勿這樣用）：

import sys

sys.modules['test'] = lambda: 'Test module caching'

import test # passing

那以上這些動作可不可以自己來呢？可以！步驟大致上長這樣：

除此之外，也可以透過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來取得）

1 2	ModuleSpec(name='fractions', loader=<_frozen_importlib_external.SourceFileLoader object at 0x7fd4d0290c88>, origin='/usr/lib/python3.5/fractions.py')

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

[_frozen_importlib.BuiltinImporter,

_frozen_importlib.FrozenImporter,

_frozen_importlib_external.PathFinder,...]

所以客製化自定義的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中依照先後順序互相覆蓋，舉例來說：

from cmath import *

from math import *

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

def func():

from math import sqrt

sqrt(2)

`name`、`main`

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

if __name__ == '__main__':

# do something if called by command line...

Package

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

Python透過__path__、__file__、__package__這些屬性來找到、封裝及載入你要的程式碼：

套件的入口__init__.py:

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

幾個套件namespaces的封裝方法：

__init__.py
將變數命名為私有（_）
__all__

# pack1

from .mod1 import *

from .mod2 import *

__all__ = (

mod1.__all__ +

mod2.__all__

)

Namespace package

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

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

2018 年 11 月 20 日2019 年 8 月 23 日
Python

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

Closure

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

Decorator

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

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

@counter

def add(a, b):

return a+b

@counter

def mul(a, b):

return a*b

adder = add()

multer = mul()

adder.__name__ == multer.__name__ == 'inner' # True

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

from functools import wraps

def counter(fn):

@warps(fn)

def inner(*args, **kwargs):

# do someting

return inner

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

def auth(func):

# do something

def log(func):

# do something

# check authorization first

@auth

@log

def f():

# do something

Decorator Factory

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

Decorator Class（用於decorator的類別）

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

Class Decorator （用來裝飾類別的decorator）

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

其他範例：
functools.totoal_ordering

def total_ordering(cls):

"""Class decorator that fills in missing ordering methods"""

# Find user-defined comparisons (not those inherited from object).

roots = [op for op in _convert if getattr(cls, op, None) is not getattr(object, op, None)]

if not roots:

raise ValueError('must define at least one ordering operation: < > <= >=')

root = max(roots) # prefer __lt__ to __le__ to __gt__ to __ge__

for opname, opfunc in _convert[root]:

if opname not in roots:

opfunc.__name__ = opname

setattr(cls, opname, opfunc)

return cls

Dispatching pattern

Python 變數範圍 – Variable Scope

2018 年 11 月 20 日2019 年 8 月 23 日
Python

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

a = 10

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

先來理解一下這些概念：

scope(lexical): 簡單來說，就是變數宣告（綁定）的地方
namespace: 命名空間紀錄這些綁定行為，每個scope都會有一份命名空間的字典來提供查找

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。例如：

# module1.py

a = 10

def func():

print(a) # a is global

print(b)

func() # raise NameError

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

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

透過關鍵字global、nonlocal來操作

a = 10

def func1():

a = 0 # a is local

def func2():

global a

a = 0 # a is global

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

def outer_func():

x = 10

def inner_func():

nonlocal x

x = 0 # a is non-local

inner_func()

此外，可以透過函數globals、locals輸出該scope的所有變數：

Python

序列 – Python Sequence

Sequence

Python WSGI 及其應用

tags: `python`, `wsgi`, `gunicorn`, `uwsgi`

Python WSGI及其應用

WSGI是什麼？

PEP3333

基本原理跟目標

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

TOC

圖論 Graph Theory

相鄰矩陣 adjacency matrixes

陣列 edge list representation

應用

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

應用

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

應用

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

Module

import做了什麼事？

這些模組從哪裡來？

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

不同import的方式(variants)

`name`、`main`

Package

Namespace package

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

Closure

Decorator

Decorator Factory

Decorator Class（用於decorator的類別）

Class Decorator （用來裝飾類別的decorator）

Dispatching pattern

Python 變數範圍 – Variable Scope

Scope的類型

Python

序列 – Python Sequence

Sequence

Python WSGI 及其應用

tags: python, wsgi, gunicorn, uwsgi

Python WSGI及其應用

WSGI是什麼？

PEP3333

基本原理跟目標

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

TOC

圖論 Graph Theory

相鄰矩陣 adjacency matrixes

陣列 edge list representation

應用

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

應用

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

應用

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

Module

import做了什麼事？

這些模組從哪裡來？

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

不同import的方式(variants)

__name__、__main__

Package

Namespace package

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

Closure

Decorator

Decorator Factory

Decorator Class（用於decorator的類別）

Class Decorator （用來裝飾類別的decorator）

Dispatching pattern

Python 變數範圍 – Variable Scope

Scope的類型

tags: `python`, `wsgi`, `gunicorn`, `uwsgi`

`name`、`main`