序列 – Python Sequence

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變數範圍 – Variable Scope

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

這裡做了物件賦值(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的所有變數:

發表留言

Python的函式應用 – First-Class Function in Python

首先很快說明一下什麼是First-Class object(一級物件):

  • 可以被當參數傳遞的
  • 可以被回傳的
  • 可以賦值給變數
  • 可以以資料結構儲存

一級函式(First Class Function)

Python的物件型別如: int、float、string、tuple、list都屬於一級物件,function也是其中之一

高階函式(Higher Order Function)

  • 可以接收function當參數,或
  • 回傳的type是function

map, filter

docstring

docstring是程式碼不是註解,用意是替你的方法加上一段說明,根據PEP257的定義,加在function第一行的字串被視為docstring

另外一種加說明的的方式,根據PEP3107所定義的function annotation

Read more “Python的函式應用 – First-Class Function in Python”

發表留言

初始Django專案並客製化設定檔 – Django Setup With Split Settings

Django Setup 專案初始化

假設我們想要建立一個django專案(1.9版本,linux為例),命名為mysite,並且不想要將特定的設定上傳,可以如何做:

clone你的倉庫(myrepo)至本地

建立虛擬環境

可以透過指令或IDE,我習慣會將環境命名為venv,然後放在專案目錄下

安裝django並開始一個專案

初始化django專案

別忘了把你安裝的套件加到mysite/requirements.txt

這時候你的tree應該長這樣

Read more “初始Django專案並客製化設定檔 – Django Setup With Split Settings”

發表留言

Python函式的參數設計 – Python Function Parameters

parameter跟argument的差異

基本上這兩者是一樣的,不過使用在不同的情境下。如果混用了其實是沒關係,可能也沒人會在意

不過值得一提的是以上這個範例的兩個參數在Module ScopeFunction Scope中都是指向同一個記憶體位置


可迭代物件的拆解機制(unpacking)

可迭代的物件都能拆解,很適合用在參數傳遞(主要使用在有序物件上)

超簡單實現swap

傳統的作法

unpacking的作法

使用***(3.5以上適用)

unpacking範例

巢狀的unpacking

Read more “Python函式的參數設計 – Python Function Parameters”

發表留言

以Python實作資料結構 – Data Structure Implements in Python

以Python實作資料結構

tags: data-structure, python

TOC

簡介

什麼是資料結構?為什麼要使用資料結構?

是電腦中儲存、組織資料的方式,可以讓我們有效地儲存資料,並讓所有運算能最有效率地完成

演算法的運行時間是根據資料結構決定的,所以使用適當的資料結構來降低演算法的時間複雜度,如:

  • 最短路徑演算法若無適當的資料結構,運行時間是O(N^2),使用(heap/priority queue)可以大幅降低運行時間至O(N*logN)

抽象資料型態 Abstract Data Types

簡單而言,ADT是針對資料結構的「規範」或「描述」,像是物件導向語言裡面的interface,但不會實作細節

舉例堆疊的ADT描述:

  • push(): 插入元素 item 至堆疊頂端
  • pop(): 移除並回傳堆疊頂端的元素
  • peek(): 看堆疊頂端的資料而不取出
  • size(): 看堆疊的長度

ADT跟資料結構的關係

每個ADT在底層都有相對應的資料結構去實作ADT裡定義過的行為(method)

ADT Data Structures
Stack array, linked list
Queue array, linked list
Priority Queue heap
Dictionary/Hashmap array

時間複雜度 Big O notation

描述演算法的效率(複雜度),舉例來說,A宅想要分享他的D槽給B宅,有以下幾種做法:

  1. 台北騎車到屏東B宅家
  2. 用網路傳輸,不考慮被FBI攔截的情況
1GB 1TB 500TB
騎車運送硬碟 600 min 600 min 600 min
網路傳輸 3 min 3072 min 1536000 min

從上表來看,騎車這個選項雖然聽起來很蠢,但不管硬碟有多大,都能確保10個小時內可以送達—— O(1);至於網路傳輸隨著檔案越大,所需的時間也越長 —— O(N);從這裡就可以看出常數時間(constant time)和線性時間(linear time)的差別對效率的影響有多大了

在表現複雜度函數的時候,有幾個通用的規則:

  • 多個步驟用加法: O(a+b)

  • 省略常數: ~~O(3n)~~ O(n)

  • 不同的input用不同的變數表示: ~~O(N^2)~~ O(a*b)

  • 省略影響不大的變數: ~~O(n+n^2)~~ O(n^2)

陣列 Array

物件或值的集合,每個物件或值可以被陣列的索引(index, key)識別

  • 索引從0開始
  • 因為有索引,我們可以對陣列做隨機存取(Random Access)

優點:

  • 隨機存取不用搜尋就能訪問陣列當中所有值,執行速度快O(1)
  • 不會因為鏈結斷裂而遺失資料
  • 循序存取快

缺點:

  • 重建或插入陣列須要逐一複製裏頭的值,時間複雜度是O(N)
  • 編譯的時候必須事先知道陣列的大小,這讓陣列這個資料結構不夠動態(dynamic)
  • 通常陣列只能存同一種型別
  • 不支援連結串列的共享

Implements

行為 big O
search 搜尋 O(1)
insert 插入第一項 O(N)
append 插入最後一項 O(1)
remove 移除第一項 O(N)
removeLast 移除最後一項 O(1)

以Python實作

random indexing: O(1)

linear search: O(n)

連結串列 Linked List & 雙向連結串列 Double Linked List

  • 節點包含datareferenced object
  • 連結的方式是節點(node)記住其他節點的參考(reference)
  • 最後一個節點的參考是NULL

優點

  • 各節點型態、記憶體大小不用相同
  • 動態佔用的記憶體,不須事先宣告大小
  • 插入、刪除快O(1)

缺點

  • 不支援隨機存取,只能循序存取(sequencial access),時間複雜度為O(N)
  • 須額外空間儲存其他節點的參考
  • 可靠性較差,連結斷裂容易遺失資料
  • 難以向前(backward)訪問,可以用雙向連結串列來處理,不過會多佔用記憶體空間

Implements

行為 big O
search 搜尋 O(N)
insert 插入第一項 O(1)
append 插入最後一項 O(N)
remove 移除第一項 O(1)
removeLast 移除最後一項 O(N)

註:連結串列沒有index,處理插入或移除第N項會需要先循序找到插入/移除位置,因此會需要O(N)的時間

以Python實作

以下的代碼是我實作的範例,有錯誤煩請指正。

主要概念是實作__getitem__來循序存取(indexing),另外Double Linked List支援反向存取,故訪問lst[0]lst[-1]皆可以達成O(1)的時間複雜度

執行結果請參考travishen/gist/linked-list.md

Linked List現實中的應用

  1. 低級別的內存管理(Low Level Memory Management),以C語言為例:
  • malloc()free(): 見Heap Management
  • chart * chart_ptr = (chart*)malloc(30);: 取得30byte的heap memory
  1. 許多Windows的應用程式:工具列視窗切換、PhotoViewer
  2. 區塊鏈技術

image
[圖片來源]

堆疊 Stack

Implements

行為 big O
push 將資料放入堆疊的頂端 O(1)
pop 回傳堆疊頂端資料 O(1)
peek 看堆疊頂端的資料而不取出 O(1)

應用

  • call stack + stack memory
  • 深度優先搜尋演算法(Depth-First-Search)
  • 尤拉迴路(Eulerian Circuit)
  • 瀏覽器回上一頁
  • PhotoShop上一步(undo)

註:任何遞迴(recursion)形式的演算法,都可以用Stack改寫,例如DFS。不過就算我們使用遞迴寫法,程式最終被parsing還是Stack

Stack memory vs Heap memory

可參考Stack vs. Heap

stack memory heap memory
有限的記憶體配置空間 記憶體配置空間較大
存活時間規律可預測的 存活時間不規律不可預測的
CPU自動管理空間(GC) 使用者自主管理空間
區域變數宣告的空間不能更動 物件的值可以變動,如realloc()

另外ptt有針對兩者佔用記憶體大小的討論stack v.s. heap sizes

以Python實作

Using Lists as Stacks

佇列 Queue

  • 佇列是一種抽象資料型態,特性是先進先出(FIFO, first in first out)
  • 在高階程式語言,容易用array、linked list來實作

應用

  • 多個程序的資源共享,例如CPU排程
  • 非同步任務佇列,例如I/O Buffer
  • 廣度優先搜尋演算法(Depth-First-Search)

以Python實作

參考

二元搜尋樹 Binary Search Tree

主要的優點就是時間複雜度能優化至O(logN)

  • 每個節點最多有兩個子節點
  • 子節點有左右之分
  • 左子樹的節點小於根節點、右子樹的節點大於根節點
  • 節點值不重複
Average case Worst case
insert O(logN) O(N)
delete O(logN) O(N)
search O(logN) O(N)

以Python實作insert, remove, search,執行結果請參考gist

BST現實中的應用

  • OS file system
  • 機器學習:決策樹

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

  • 能保證O(logN)的時間複雜度
  • 每次insert, delete都要檢查平衡,非平衡需要額外做rotation
  • 判斷是否平衡:
    • 左子樹高度 - 右子樹高度 > 1: rotate to right
    • 左子樹高度 - 右子樹高度 < -1: rotate to left
    • image
Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

不適合用在排序,時間複雜度為O(N*logN)

  • 插入n個:O(N*logN)
  • in-order迭代:O(N)

繼承上面BST繼續往下實作,有bug請協助指正,執行結果請參考gist

  • 任一節點設定完left或right,更新該節點height
  • 每個insert的call stack檢查檢查節點是否平衡,不平衡則rotate

紅黑樹 Red-Black Tree

  • 相較於AVL樹,紅黑樹犧牲了部分平衡性換取插入/刪除操作時更少的翻轉操作,整體效能較佳(插入、刪除快)
  • 不像AVL樹的節點屬性用height來判斷是否須翻轉,而是用紅色/黑色來判斷
    • 根節點、末端節點(NULL)是黑色
    • 紅色節點的父節點和子節點是黑色
    • 每條路徑上黑色節點的數量相同
    • 每個新節點預設是紅色,若違反以上規則:
    • 翻轉,或
    • 更新節點顏色

image

Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

github上用python實作的範例:Red-Black-Tree

優先權佇列 Priority Queue

  • 相較於Stack或Queue,對資料項目的取出順序是以權重(priority)來決定
  • 常用heap來實作

二元堆積 Binary Heap

  • 是一種二元樹資料結構,通常透過一維陣列(one dimension array)
  • 根據排序行為分成minmax
    • max heap: 父節點的值(value)或權重(key)大於子節點
    • min heap: 父節點的值(value)或權重(key)小於子節點
  • 必須是完全(compelete)二元樹或近似完全二元樹

註:

  • heap資料結構跟heap memory沒有關聯
  • 優勢在於取得最大權重或最小權重項目(root),時間複雜度為O(1)
time complexity
insert O(N) + O(logN) reconsturct times
delete O(N) + O(logN) reconsturct times

應用

  • 堆積排序法(Heap Sort)
  • 普林演算法(Prim’s Algorithm)
  • 戴克斯特拉演算法(Dijkstra’s Algorithm)

堆積排序 Heapsort

  • 是一種比較排序法(Comparision Sort)
  • 主要優勢在於能確保O(NlogN)的時間複雜度
  • 屬於原地演算法(in-place algorithm),缺點是每次排序都須重建heap——增加O(N)時間複雜度
  • 在一維陣列起始位置為0的indexing:

image

操作可參考這篇文章:Comparison Sort: Heap Sort(堆積排序法)

用Python實作Max Binary Heap,請參考gist

python build-in heapq

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

  • 鍵、值的配對(key-value)
  • 相較於樹狀資料結構,劣勢在於排序困難
  • 主要操作:
    • 新增、刪除、修改值
    • 搜尋已知的鍵

image

hash function

  • division method: modulo operator

h(x) = n % m

n: number of keys, m: number of buckets

Collision

當多個key存取同一個bucket(slot),解決collision會導致時間複雜度提高

解法:

  • chaining: 在同一個slot用linked list存放多個關聯
  • open addressing: 分配另一個空的slot
    • linear probing: 線性探測
    • quadratic probing: 二次方探測,如1, 2, 4, 8…
    • rehashing

Second Round皆有詳盡解說:

Dynamic resizing

load factor(佔用率): n / m

  • load factor會影響到存取的效能,因此須要根據使用率動態變更陣列大小;
  • 舉例來說,Java觸發resize的時機點大約是佔用超過75%時、Python則約是66%

應用

  • 資料庫
  • Network Routing
  • Rabin-Karp演算法
  • Hashing廣泛用於資料加密

參考:

  • http://www.globalsoftwaresupport.com/use-prime-numbers-hash-functions/
  • http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#collision

以Python實作,請參考gist

Average case Worst case
insert O(1) O(N)
delete O(1) O(N)
search O(1) O(N)

三元搜尋樹 Ternary Search Tree, TST

  • 相較其他樹狀資料結構而言,佔用記憶體空間較小
  • 只儲存string,不存NULL或其他物件
  • 父節點可以有3個子節點:left(less)middle(equal)right(greater)
  • 可以同時用來當作hashmap使用,也可以做排序
  • 效能上比hashmap更佳,在解析key時是漸進式的(如cat若root沒有c就不用繼續找了)

image

應用

  • autocompelete
  • 拼字檢查
  • 最近鄰居搜尋(Near-neighbor)
  • WWW package routing
  • 最長前綴匹配(perfix matching)
  • Google Search

以Python實作,請參考gist

互斥集 Disjoint sets / union-find data structure

  • 一堆沒有交集的集合,如10個學生分成4組
  • 主要操作: unionfindmakeSet
  • 通常以linked list或tree來實作
  • 訪問disjoint set中的任何節點都回傳同一個root value

set在union過程中會遇到不平衡的問題,有兩種最佳化方法:

  1. union by rank: 讓小的樹接到較大的樹
  2. path compression: 訪問節點時調整樹的結構,直接與root連結

應用

  • Kruskal: 檢查圖中是否有cycle

以Python實作,輸出請參考gist

發表留言

Fluent Python Notes: An array of sequences

私人筆記,有錯誤煩請指正

Fluent Python Github


序列(Sequence)

可分成容器序列、一般序列;或分成可變及不可變。容器序列保存物件的參考,可以是任何型態;一般序列實際儲存項目的值,但只能保存數字、字元或位元組

容器「有些物件裡面有其他物件的參考,這些物件稱為容器」

collections.abc


List Comprehension(listcomp)

如果你不是只想建構串列,就不該使用listcomp,如果listcomp的長度太長,請考慮用for迴圈。Python 2.x 中listcomp中的變數會影響到外部環境的變數

Generator Expression(genexp)

串列以外的序列類型應該使用genexp,可節省記憶體空間(透過for迴圈一次產生一個項目)


Tuple可充分扮演紀錄的角色,原因是他的拆解機制(Unpacking)


slice跟range排除最後一個項目的原因

  • 容易看出或計算長度,range(start, stop)或my_list[start:stop]的長度都是stop – start
  • 區分序列成多個部份而不會重疊,my_list[:x]與my_list[x:]


建構巢狀串列


重要的Python API慣例

當函式或方法就地改變物件時,必須回傳None,來讓呼叫方知道物件本身已被改變,而且沒有創建新的物件,e.g. list.sort、random.shuffle。這樣做有一個缺點,無法層疊這些方法的呼叫式(Fluent Interface 流式接口);反之,會回傳新的物件的例子如sorted、所有str的方法


待補充:bisect、memorview, numpy.ndarray, collections.deque


拿list來裝混合型態的物件並不實用,因為list的某些操作可能會無法使用,請用tuple,因為相較之下這種作法自然很多(tuple每個項目其實都代表是個欄位)


list.sort與sorted的排序演算法是用Timesort,會根據資料的排序狀況來決定用插入排序還是合併排序

發表留言

Fluent Python Notes: Data Model

私人筆記,有錯誤煩請指正

Fluent Python Github


遵循Steve Holden的做法,在唸出Magic Functions的時候用dunder取代underscore, 如__getitem__唸作”dunder-getitem”


善用namedtuple來建構裡面只有一堆屬性,沒有自訂方法的簡單類別,如資料庫的紀錄一般

註:

  1. nametuple是類別工廠,回傳一個tuple的子類別
  2. 呼叫屬性asdict回傳OrderedDict物件(3.6後版本)
  3. 屬性是immutable(tuple),要更改可以re-create或呼叫_replace
  4. 透過__doc__設定docstring
  5. 透過__default__prototype._replace來設定預設值


實作__getitem__讓物件變成可迭代物(iterable)


某個集合可以透過實作__contains__來定義in運算子要如何掃描集合。


關於特殊方法,它們是要讓Python編譯器呼叫的,而不是你(私下呼叫);使用者程式經常呼叫的特殊方法只有__init__,目的是呼叫你自己寫的__init__;如果你要呼叫特殊方法,呼叫相關的內建函式會比較好(例如len、iter、str等),這些函式不僅會呼叫對應的特殊方法,通常還會提供其他服務,也比較快


__repr__回傳的字串必須精確,而且如果可以的話,必須盡可能匹配原始碼,以重新建立被表示的物件;__str__是讓print函式私下使用的,回傳給終端使用者觀看的格式;如果沒有自訂的__str__可用,Python會呼叫__repr__來提供回饋

https://stackoverflow.com/a/2626364/8100647


注意這裡的方法回傳新的Vector實例。為中綴(infix)運算子的預期行為:為了建立新的物件,並不接觸它們的運算元


len不會被當成方法來呼叫,因為它身為Python資料模型的一部分,會受到特殊對待,如同abs。但是拜特殊方法__len__所賜,你的自訂物件也可以使用len,這是一種在內建物件效率與語言一致性之間取得的平衡

發表留言

Numeric in Python

5 types

int

integers are represented using base-2(binary) digits, not base-10(decimal)

10011(base-2) required 5 bits

what’s the range of integer number can be represented using 8 bits?

11111111(base-2) required 8 bits, could represent largest 255

Using 8 bits are able to represent range [-127, 127], since 0 does not require a sign, we can squeeze out an extra number to [-128, 127]

How large an integer can be depends on how many bits are used, some languages(Java, C) provide multiple distinct integer types that use a fixed number of bits. Python doesn’t work that way, the int object uses a variable number of bits, can use 32, 64, 96 bits etc.(increase bits by need)

int arithmetic
  • int +(-, *, **, //, %) int => int
  • int / int => float

integer base change algorithm


Fraction

represent rational number


float

represent real number

CPython float is implemented using the C double type which implements the IEEE double-precision binary float, also called binary64

float uses a fixed number of bytes, in standard, CPython/3.6/64bits using 8 bytes(64 bits)

representation
  • decimal
  • binary

problem: some numbers do not have a finite representation

  • 1/3 can not represent accurate by decimal expansion
  • 1/10 can not represent accurate by binary expansion

Coercing float to integer -> data loss

truncation: math.trunc(), constructor of int() use truncation

floor: math.floor()

ceiling: math.ceil()

round: round()

Banker’s Rounding

Read more “Numeric in Python”

發表留言