Skip to content

Python

序列 – Python Sequence

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

Read More »序列 – Python Sequence

Python WSGI 及其應用

  • 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

Read More »Python WSGI 及其應用

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

  • Python

TOC

圖論 Graph Theory

G(V, E)

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

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

相鄰矩陣 adjacency matrixes

image
圖片來源

陣列 edge list representation

應用

  • 最短路徑演算法 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

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

Read More »以Python實作演算法 – Algorithms Implements using Python

Python 模組與套件 – module, package in 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(但這樣寫有大麻煩,請勿這樣用):

那以上這些動作可不可以自己來呢?可以!步驟大致上長這樣:

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

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

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

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

__name____main__

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

Package

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

Python透過__path____file____package__這些屬性來找到、封裝及載入你要的程式碼:

套件的入口__init__.py:

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

幾個套件namespaces的封裝方法:

  • __init__.py
  • 將變數命名為私有(_)
  • __all__

Namespace package

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

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

  • Python

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


Closure

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

Decorator

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

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

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

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

Decorator Factory

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

Decorator Class(用於decorator的類別)

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

Class Decorator (用來裝飾類別的decorator)

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

其他範例:
functools.totoal_ordering

Dispatching pattern

Python 變數範圍 – Variable Scope

  • Python

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

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

先來理解一下這些概念:

  • scope(lexical): 簡單來說,就是變數宣告(綁定)的地方

  • namespace: 命名空間紀錄這些綁定行為,每個scope都會有一份命名空間的字典來提供查找

image

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

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

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

透過關鍵字globalnonlocal來操作

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

此外,可以透過函數globalslocals輸出該scope的所有變數: